Product of all numbers

A prime $p$ is called "good" if there is an $m$ such that $p$ divides $m^2 - 2$. For example, 7 and 17 are good primes. Suppose $p$ is a good prime. Consider all numbers in the form of $a\sqrt{2} + b$ where $a,b \in \{0, \dots, p-1\}$ and $(a,b) \neq (0,0)$. The product of all those numbers can be written as $s\sqrt{2} + t$ where $s$ and $t$ are integers. Find their remainders modulo $p$. What if $p$ is not a good prime?

Solution

If $p$ is a good prime then $s \equiv t \equiv 0 \mod p$. If $p$ is not a good prime, then $s \equiv 0, t \equiv -1 \mod p$

Proof:

Define the "~" (equivalency) as follows: two numbers $s \sqrt{2} + t$ and $u\sqrt{2} + v$ are equivalent if $s \equiv u$ and $t \equiv v \mod p$. Then we readily see that the following properties are easy to show:

$X \sim X$ (reflexivity).

$X \sim Y \iff Y \sim X$ (symmetry).

If $X \sim Y$ and $Y \sim Z$ then $X \sim Z$ (transitivity).

Given these three then equivalency divides all numbers in te form $s\sqrt{2}+t$ into equivalency classes. Furthermore we see that:

If $X \sim Y$ and $W \sim Z$ then $X+W \sim Y+Z$ and $XW \sim YZ$. It follows directly from the properties of modular arithmetics.

Now, if $p$ is a good prime, then note that $(\sqrt{2} + m)(\sqrt{2} + p-m) = (2-m^2 + pm) + p\sqrt{2} \sim 0$. Thus the product of all numbers in question is equivalent to zero.

If $p$ is not a good prime, it's a lot more complicated.

First we claim the following: given $X \nsim 0$, then there exists $Y$ such that $XY \sim 1$. We call this $Y$ the inverse of $X$.

Proof: Given a number $a\sqrt{2} + b$, first we define the number $r$ as follows: $r \in (0, \dots, p-1)$ such that $r(b^2-2a^2) \equiv 1 \mod p$.

This $r$ must exist, because $b^2 - 2a^2 \not\equiv 0 \mod p$, for otherwise we have $(ba^{-1})^2 \equiv 2 \mod p$, a contradiction.

Then consider the number $ar\sqrt{2}-br$. The product of this and $a\sqrt{2} + b$ is: $$(ar\sqrt{2}-br)(a\sqrt{2} + b) = (2a^2-b^2)r \sim 1$$

Then we prove the second claim: If $XY \sim 0$ then either $X \sim 0$ or $Y \sim 0$.

Proof:

Let $X = a\sqrt{2}+b, Y = c\sqrt{2}+d$ then $XY = (bc+ad)\sqrt{2}+(2ac+bd) \sim 0$ so we have: $$bc+ad \equiv 0 \mod p$$ $$2ac+bd \equiv 0 \mod p$$ Assuming that both $X,Y$ are not equivalent to zero, either $c \neq 0$ or $d \neq 0$ because otherwise $Y \sim 0$. If $d \neq 0$ then: $$abc \equiv -a^2d \mod p$$ $$2abc \equiv - b^2d \mod p$$ $$\Rightarrow b^2d \equiv 2a^2d \mod p$$ $$(ba^{-1})^2 \equiv 2 \mod p$$ A contradiction. If $c \neq 0$ then we similarly show: $$abd \equiv - b^2c \mod p$$ $$abd \equiv -2a^2c \mod p$$ $$(ba^{-1})^2 \equiv 2 \mod p$$ Also a contradiction. (The assumption that $X \nsim 0$ is needed to take inverse of $a$)

So based on the second claim, we now assert that each number in the problem statement has an inverse, and the inverse is unique. For if $XY \sim XZ \sim 1$ then $X(Y-Z) \sim 0$ so $Y \sim Z$. This means that a lot of pairs among those numbers would multiply 1. The only numbers left are those who are inverses with itself. To find such numbers, note the following:

$$X^2 = 2ab\sqrt{2} + (2a^2+b^2) \sim 1$$ $$\iff ab \equiv 0, 2a^2+b^2 \equiv 1 \mod p$$ If $a \equiv 0$ then $b^2 \equiv 1$, so $p$ divides $b^2-1 = (b+1)(b-1)$. The only possible $b$ are $1, p-1$, and these numbers are in the problem statement.

If $b \equiv 0$ then $2a^2 \equiv 1$ which means $2 \equiv (a^{-1})^2 \mod p$, a contradiction.

So the only numbers who don't "cancel out" with other numbers are 1 and -1, and they're included in the final product. Thus the product of all those numbers is $\sim -1$.

Prisoners With Hats Again

This is a generalization of the latest logic problem in MIT's Technology Review, November/December 2014 There are $n$ prisoners, $a_1, a_2, \dots, a_n$ where each prisoner is a perfect logician. Also, $a_n$ is blind but the other ones can see.

Initially they're all blindfolded. There are $n$ white hats and $n-1$ black hats, and out of those $2n-1$ hats, $n$ hats are randomly selected, and the rest hidden. Each prisoner is then given one of those $n$ hats to wear. At the same time, all the blindfolds are taken off.

Then the prisoners said the following things, in this order:
$a_1$ said: "I don't know my hat color."
$a_2$ said: "I don't know my hat color."
$a_3$ said: "I don't know my hat color."
...
$a_{n-1}$ said: "I don't know my hat color."
$a_n$ said: "I know my hat color."

What is $a_n$'s hat color?

Solution

If $a_1$ saw all black hats, then he would know that his hat is white, because there are at most $n-1$ black hats in the room. Because he doesn't know his hat color, then at least one of $a_2,\dots,a_n$ is white.

Likewise, if $a_2$ saw all black hats among $a_3, \dots, a_n$, given the information that at least one of $a_2, \dots, a_n$ is white, he would know that his hat is white. Because $a_2$ doesn't know his hat color, then at least one of $a_3, \dots, a_n$ is white.

We can continue this line of reasoning via induction. The hypothesis is that at least one of $a_k, \dots, a_n$ is white. If $a_{n-1}$ saw that $a_n$ has black, he would know that he has white. Because $a_{n-1}$ doesn't know his hat color, that means $a_n$ has white.

Projectile fired

A projectile fired from the ground passes over two points $A$ and $B$ that are horizontally $d$ apart. Point $A$ is $2h$ high from the ground whereas point $B$ is horizontally $3h$ high from the ground. What's the minimum speed of projection?

Inverse distances to points

Let $P$ and $Q$ be two distinct points on a plane. For any given point $X \neq P,Q$, define two functions $f(X)$ and $g(X)$ as follows: $$f(X) = \frac{1}{PX} + \frac{2}{QX}$$ $$g(X) = \frac{2}{PX} + \frac{1}{QX}$$ Now for any positive number $t$, let $S(t)$ be the set of all points $Y$ such that $f(Y) \leq tg(Y)$.

Prove that $S(t)$ is bounded

Prove that $S(t)$ is convex. That is, if $A,B$ are in $S(t)$ then $AB$ is in $S(t)$.

Identify all points $X$ on $S(t)$ such that $PX+QX$ is minimum.

Prove that the area of $S(t)$ is a convex function of $t$.

Powered distances

Let $p$ and $q$ be two infinitely long non-parallel lines on a plane. For any point $X$, let $d_p(X), d_q(X)$ denote distances from $X$ to $p$ and $q$ respectively. For any positive number $r$, let $S(r)$ be the set of all points $Y$ such that $d_p(Y)^{2015} + d_q(Y)^{2015} \leq r$.

Prove that $S(r)$ is bounded.

Prove that $S(r)$ is convex. That is, if $A$ and $B$ are in $S(r)$ then $AB$ is in $S(r)$.

Identify all points in $S$ such that $d_p(X)^{2014} + d_q(X)^{2014}$ is maximum.

Prove that the area of $S(r)$ is a convex function of $r$.

Ball hitting an inclined plane

A ball with mass $m$ and radius $R$ is rolling without slip with velocity $v$ on a horizontal plane. It then hits an inclined plane with angle $\theta$, after which it continues rolling without slip upwards along the plane. How far does the ball travel along the plane before it stops?

Also determine the maximum speed $v$ such that the ball does not lose contact with the plane (rebound).

Solution

At the point of contact, there is a change of pivot point. Suppose that the speed after the impact is $v'$ then the angular speed is $v'/R$. Immediately before impact, the ball's center of mass travels horizontally, while immediately after, it travels parallel to the plane. Thus there is an impulse. Suppose we denote $F_x, F_y$ to be the horizontal and vertical component of the impulse respectively. The direction of $F_y$ is upwards, while $F_x$ is against the initial motion of the ball. The impulse occurs at the first point of contact with the inclined plane, because this is where the normal force from the plane acts on the ball. The impulse from the gravity is negligible because we assume instantaneous / momentary contact time.

Change in vertical linear momentum: $$I_y = mv'\sin \theta$$ Change in horizontal linear momentum: $$I_x = m(v - v'\cos \theta)$$ Change in angular momentum. Remember that $I_y$ goes against the new rotational motion while $I_x$ helps it. $$I_x R \cos \theta - I_y R \sin \theta = \frac{2}{5}mR^2 (\frac{v'}{R} - \frac{v}{R})$$ We have three equations and three unknowns: $I_x, I_y, v'$. Solving for $v'$: $$I_x \cos \theta - I_y \sin \theta = \frac{2}{5}m(v'-v)$$ $$(v - v'\cos \theta) \cos \theta - v' \sin^2 \theta = \frac{2}{5}(v'-v)$$ $$v' = \frac{2+5\cos\theta}{7} v$$ Sanity check, if $\theta = 0$ then $v' = v$, and if $v'$ decreases with $\theta$.

From here we can use the law of conservation of energy, since post-collision there's no energy lost to friction. $$mgh = \frac{1}{2}mv'^2 + \frac{1}{2} \frac{2}{5}mR^2 \frac{v'^2}{R^2}$$ $$gh = \frac{7}{10} (\frac{2+5\cos\theta}{7} v)^2 = \frac{10(2+5\cos \theta)^2}{7} v^2$$ $$h = \sqrt{\frac{10}{7g}} (2+5\cos \theta)v$$ The distance traveled along the plane is $d = h / \sin \theta$ $$d = \sqrt{\frac{10}{7g}} (2+5\cos \theta) \frac{v}{\sin \theta}$$ The instant after the impact, the ball rotates around the new point of contact. The combination of weight and normal force supplies the necessary centripetal force. We express everything in the direction perpendicular to the plane: $$mg \cos \theta - N = \frac{mv'^2}{R}$$ $$N = m(g \cos \theta - \frac{v'^2}{R}$$ For $N \geq 0$ we must have that: $$g \cos \theta \geq \frac{(2+5\cos\theta)^2}{49R} v^2$$ $$v \leq \frac{7 \sqrt{gR\cos \theta}}{2+5\cos\theta}$$

Alternative Solution

At the point of contact, there is a change of pivot point. Suppose that the speed after the impact is $v'$ then the angular speed is $v'/R$. Immediately before impact, the ball's center of mass travels horizontally, while immediately after, it travels parallel to the plane. Let $X$ be the new pivot point. We consider the angular momentum about $X$ before and after the impact. The force exerted by plane on the ball is at $X$ so there's no torque around $X$, thus these two angular momenta must be equal.

Note that the m.o.i of a ball rotating around it's edge is $\frac{2}{5}mR^2 + mR^2 = \frac{7}{5}mR^2$.

The angular momentum before the impact depends on two things: the angular momentum of the center of mass (c.o.m) and the angular momentum of the ball around the c.o.m. The c.o.m was traveling horizontally, forming angle $\pi/2 - \theta$ with the radius vector. The $r \times v$ term is $vR \cos \theta$, thus the angular momentum of the c.o.m is $mvR \cos \theta$.

The angular momentum of the ball around the c.o.m is $\frac{2}{5}mR^2 v/R = \frac{2}{5}mvR$. These two momenta have the same direction so we can simply add them: $$ L= mvR (\cos \theta + \frac{2}{5})$$ Now the angular momentum after the impact is a simple rotation on the edge with the new speed: $$ L' = \frac{7}{5}mR^2 \frac{v'}{R} = mv'R \frac{7}{5} $$ So we have: $$ (\cos \theta + \frac{2}{5}) v = \frac{7}{5} v'$$ $$v' = \frac{2+5\cos\theta}{7} v$$ The rest is same as the first solution.

Rotating projected ball

Inspired by a problem from brilliant.org A solid spherical ball with radius $R$ is projected from a rough ground with a velocity $v$ at angle $\theta$ with the horizontal, traveling to the right. At the same time it is given an angular velocity of $\omega$ clockwise such that the axis of rotation is perpendicular to the plane of projection.

At some point, the ball bounced on the ground, with coefficient of restitution $\frac{1}{2}$ and coefficient of friction is enough so that the ball did not slip while touching the ground. Find the initial angle such that the horizontal distance traveled by the ball to the point of second bounce be maximized.

Solution

The initial velocity components are $v_x = v\cos\theta,v_y = v \sin \theta$. When the ball first touches the ground again, it will do so after a $t = 2v_y/g$ time, covering a distance of $d_1=tv_x = 2v_xv_y/g$.

At that point, the new velocity will have components $v'_x,v'_y$ respectively. We will calculate each component separately.

The vertical velocity is affected by the coeff. of restitution. Since the ground is assumed to be stationary (mass of the ball << mass of the Earth), then $v'_y = v_y / 2$

The horizontal velocity is affected by the friction. At the point of contact, the ball tends to go to the left, so the friction tends to go to the right. Suppose that the impulse caused by friction is $I$, then we have the following:

Linearly, the friction helps the linear motion: $$I = M(v'_x - v_x)$$ Rotationally, the torque caused by the friction slows down the angular motion: $$IR = \frac{2}{5}MR^2 (\omega - \frac{v'_x}{R})$$ (the last term is because we're assuming that the ball doesn't slip when it touches the ground). Solving for $v'_x$ we have: $$MR(v'_x - v_x) = \frac{2}{5}MR^2 (\omega - \frac{v'_x}{R})$$ $$v'_x - v_x = \frac{2}{5}R (\omega - \frac{v'_x}{R})$$ $$v'_x - v_x = \frac{2}{5}R\omega - \frac{2v'_x}{5}$$ $$v'_x = \frac{5}{7}( v_x+\frac{2}{5}R\omega ) = \frac{5v_x+2R\omega}{7}$$ Similar to the distance to the first bounce, the distance between first and second bounce is $$d_2 = 2v'_x v'_y/g = \frac{v_y(5v_x+2R\omega)}{7g}$$ Total distance is therefore: $$d_1+d_2 = \frac{2v_xv_y}{g} + \frac{v_y(5v_x+2R\omega)}{7g} = \frac{19v_xv_y + 2Rv_y\omega}{7g}$$ $$ = \frac{v}{7g}(19v\sin\theta\cos\theta + 2R\sin\theta\omega)$$ Now we wish to find $\theta$ that maximizes: $$19v\sin\theta\cos\theta + 2R\omega\sin\theta$$ which can be done in various ways (calculus, double-angle formula etc).