Lights forming a hexagon

Six lights are placed such that they form a regular hexagon. At each turn, we're allowed to do one of the following:

1. Toggle three consecutive lights

2. Toggle three lights that form an equilateral triangle

3. Toggle two diametrically opposite lights

Prove or disprove, for any given starting configuration, we can turn off all the lights through a series of turns as described above.

Solution

Answer: we cannot.

Label the lights as 1,2,3,4,5,6, and denote each move as follows:

$A_i$: toggling lights $i, i+1, i+2$. There are 6 such moves: $A_1, \dots, A_6$.

$B_i$: toggling an equilateral with $i$ as one of its vertices. Obviously we only need to consider $B_1, B_2$.

$C_i$: toggling $i$ and its opposite. Again, we only need to consider $C_1, C_2, C_3$.

$D$: toggling all the lights. Although this is not one of the moves allowed explicitly in the problem statement, it can be achieved by the combination of $A_1+A_4$ (as well as many others), so it is effectively a legal move.

From a set of moves, we're allowed to remove it if it can be achieved by a combination of all the other moves remaining in the set. So from the set of all the moves described above, we can remove $A_4, A_5, A_6$ because they can be achieved by $D + A_1, D+A_2, D+A_3$ respectively.

Likewise, we can remove $B_2 = B_1 + D$ and $C_3 = C_1+C_2+D$. So now we're down to $\{A_1,A_2,A_3,B_1,C_1,C_2,D\}$. Now notice that: $A_2 = C_1 + A_1$, $A_3 = C_1 + C_2 + A_1$ so we remove them as well, leaving us with $\{A_1,B_1,C_1,C_2,D\}$.

Now although the number of possible move sequences is infinite, the number of reachable configurations from an all-off configuration is limited. There are five moves left in our set. We have not yet proved that they're all truly independent (i.e. we can no longer remove any more), but we don't need to. For each move in that set, it only matters whether that move is performed an even or odd number of time. In algebraic lingo, these moves are commutative and self-inverse. So that means there are at most $2^5$ configurations reachable from an all-off configuration, but we have $2^6$ total configurations. Each sequence of moves are its own inverse, so that means there are 32 configurations such that we cant turn off all the lights.

If we're asked to identify such configuration, we note the following: the configuration where only 1 light is on is not reachable from an all-off configuration. If this were possible, then we could apply that same sequence of moves (rotated appropriately) to achieve any desired configuration.

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).

Pencil rolling down the plane

Inspired by IPhO 1998.

A pencil that's made of homogeneous wood is shaped like a regular hexagonal prism, with hexagon side $s$ and mass $M$. The pencil rolls down an inclined plane. Find the moment of inertia.

Assume that the sides are slightly concave so that only the vertices of the hexagons are touching the plane at any given moment.

Solution

First we find the moment of inertia of a equilateral prism about its center. Suppose the triangle side is $s$. By dimensional analysis, we know that the moment inertia $I$ must have the form $I = kMs^2$ for some $k$. Also note that the equilateral triangle is a superposition of 4 smaller triangles.

The moment of inertia from the triangle in the center is $k.M/4.(s/2)^2 = kMs^2 / 16$.

The moment of inertia from each of the outer smaller triangle can be found using parallel axis theorem. From geometry, we know the displacement of the axes is $s / \sqrt{3}$. So: $$I_t = \frac{kMs^2}{16} + \frac{M}{4} . (\frac{s}{2\sqrt{3}})^2 = \frac{Ms^2}{16} (k + \frac{1}{3})$$ Therefore our original moment of inertia should be equal to the superposition of four triangles: $$kMs^2 = \frac{kMs^2}{16} + 3\frac{Ms^2}{16} (k + \frac{1}{3})$$ $$k = \frac{k}{16} + \frac{3k+1}{16}$$ $$k = \frac{1}{12}$$ So the moment of inertia of an equilateral prism about its tip is $$\frac{Ms^2}{12} + M(\frac{s}{\sqrt{3}})^2 = \frac{5Ms^2}{12}$$ Thus the moment of inertia for six of these triangles about their tip (i.e. hexagon about the center) is $6 . 5/12 . M/6 s^2 = 5Ms^2/12$ So the moment of inertia of the hexagon about the edge is $$ \frac{5Ms^2}{12} + Ms^2 = \frac{17}{12}Ms^2$$

Second Solution

Alternatively we can find the moment of inertia of a triangular prism about its tip by dividing it into a series of slabs, where each slab does not touch the rotational axis. Each slab is infinitesimally thin (having thickness of $dx$) where $x$ is the distance from the axis to the slab. The slab would have a dimension of $l \times dx \times s$ where $x = \sqrt{3}s / 2$ so $s = 2x / \sqrt{3}$.

Suppose the density of the wood is $\rho$. The mass of the slab is then $m=\rho.l.s.dx$. The m.o.i of the slab around the center is $$\frac{m}{12}(dx^2 + s^2) \simeq \frac{ms^2}{12}$$ The m.o.i of the slab around the axis that's $x$ away is then $$\frac{ms^2}{12} + mx^2 = \rho.l.s.dx.(\frac{s^2}{12} +x^2) = \rho.l.\frac{20}{9\sqrt{3}} x^3 dx$$ The triangle is a superposition of these slabs, with $x$ ranging from $0$ to $\frac{\sqrt{3}}{2}S$ $$I = \int_0^\frac{\sqrt{3}S}{2} \rho.l.\frac{20}{9\sqrt{3}} x^3 dx = \rho.l.\frac{20}{9\sqrt{3}} . \frac{9/16 S^4}{4} = \frac{5}{16\sqrt{3}} \rho.l.S^4$$ But then $\rho = M / (l.S^2.\sqrt{3}/4) = 4M / (\sqrt{3}lS^2)$ so: $$I = \frac{5}{16\sqrt{3}} l.S^4 . \frac{4M}{\sqrt{3}lS^2} = \frac{5MS^2}{12}$$ The moment of inertia for the hexagon about the edge follows easily just like in the first solution.

Call applicants to front

Let $n$ be a natural number, and we are given a sequence $a_1, a_2, \dots, a_{2n}$ whose elements are integers from 1 to $n$ inclusive, such that each element in $(1, \dots, n)$ appears at least once.

Now, suppose there are $n$ job applicants $J_1, \dots, J_n$ waiting on a line, in any order. We call them in for interviews using $a_i$ as our "call list." More formally, for $i = 1, \dots, 2n$, we call $J_{a_i}$ one by one.

If a particular job applicant $J_x$ is called for an interview, he has to pay a fee of $y-1$ where $y$ is his position in the line. For example, if he was the second person when called, he pays a fee of 1. If he was the front person, he doesn't pay. After the interview, he returns to the front of the line, and the interviewer proceeds with the next one on the call list.

For a given call list and initial ordering of applicants, we define income as the total fees paid by the applicants. For a given call list, its potential income is the sum of all income over all possible initial ordering of applicants. Now, to make things more interesting, before the interview day, the call list itself was shuffled, such that any $(2n)!$ permutation is equally likely to appear.

If you are tasked with putting together a call list, knowing that it will eventually be shuffled, how should you structure it so that the expected potential income is maximized?

Searching on a chess board

Alice fills each cell of an $n \times n$ chess board with real numbers, such that there is exactly one zero somewhere on that board. The rest of the cells could be filled with positive or negative numbers, so that all numbers are distinct. Furthermore, she filled it such that each row is sorted from left to right and each column is sorted from top to bottom.

Now she asks Bob to find the location of the zero via a guessing game. Bob is told about the sortedness of the board and that all numbers are distinct, but he doesn't know the numbers themselves. He is allowed to make a series of guesses (of locations), and after each guess, he would be told the number on that cell. The game ends when Bob discovers the zero.

Show that Bob can devise a strategy that guarantees discovery after $2n-1$ guesses.

Show that there is no strategy that guarantees discovery with less than $2n-1$ guesses.

Solution to First Problem

Let cell $(i,j)$ refers to the cell on the $i$-th row and $j$-th column, with $i,j \geq 1$ (usual matrix notation, NOT the usual computer science notation). Bob can follow the following algorithm:

First start by guessing $(n,1)$. If that number is positive, go up 1 cell, and if it's negative, go right one cell.

In order to show that this strategy works, we have to prove three things: termination, correctness, and running time.

Proof of termination and running time

If $(i,j)$ represents the cell of our last guess, let $S = i-j$. Note that in the beginning, $S = n-1$. And for each move, whether that's 1 up or 1 right, $S$ decreases by one. Also that the minimum number of $S$ is attained when $i$ is minimum and $j$ is maximum, namely on cell $(1,n)$, which means $S = 1-n$. That means that after $(n-1)-(1-n)+1 = 2n-1$ moves we are guaranteed to terminate.

Proof of correctness

Let $A$ be the event that we guessed the column (but not necessarily the row) of the zero correctly, and $B$ denotes the event that we guessed the row of the zero correctly. It's easy to see that after $A$ or $B$ is reached, we are guaranteed to reach the zero. For example, once $A$ happens, our guess will keep moving up until it reaches the zero, and vice versa.

Now to show that $A$ or $B$ is ever reached, suppose the zero is at a location $(i_0, j_0)$. That means $A$ happens after $(i_0-1)$ right moves, and $B$ happens after $(n-j_0)$ up moves. Every move is either a right move or an up move, so after many enough moves, either $A$ or $B$ will happen.

Solution to Second Problem

Define the "major" diagonal to be cells $(i,j)$ such that $i+j = n+1$. That is, bottom left to top right. Define the "minor" diagonal to be cells $(i,j)$ such that $i+j = n$. That is, cells above (or to the left of) major diagonal. Now suppose Alice populates the board in the following way: populate everything above the minor diagonal with numbers less than -1, and populate everything below major diagonal with numbers > 1, all while still satisfying the sortedness criteria.

As for the diagonals themselves, note that if the major diagonal is populated with numbers between 0 and 1, and the minor diagonal populated with numbers between -1 and 0, and if the zero is anywhere on the two diagonals, the sortedness criteria is still satisfied. Between cells in the major diagonals themselves (say $(n,1)$ versus $(n-1,2)$) there is no constraint, and likewise there is no constraint between cells in the minor diagonals.

Now suppose Alice never decides on the content of the major and minor diagonals until Bob asks for the content of those cells. In other words, even Alice herself doesn't know where the zero will be. As Bob executes his strategy, if he asks for a cell on the major diagonal, Alice just generates a random number between zero and one. If he asks for a cell on the minor diagonal, she generates a random number between -1 and zero. Note that at any given point, even if Bob knows the content of all the other non-diagonal cells, these numbers are still consistent with the sortedness of the board.

Alice reveals zero only after all the other diagonal cells are exhausted. In other words, Alice only reveals zero if that is the last diagonal cell (major or minor) that Bob hasn't asked. Because there are $2n-1$ diagonal cells, any strategy that Bob has can never guarantee discovery with less than $2n-1$ guesses.

Betting on cards

A deck consisting of $n$ red cards and $n$ black cards are shuffled. The cards are then flipped one at a time. Before each flip, you are allowed to make a bet on the color of the next card. If you guessed right, you win an amount equals to your bet. If you guessed wrong, you lose your bet. You don't have to bet on every flip, in fact you don't have to bet at all if you so wish. The bets can be any amount of real number, and you start with one dollar.

You decide to employ the following strategy. Suppose that, by counting already-flipped cards, you deduce that there are $R$ red cards and $B$ black cards left in the deck. If $R > B$, you guess red while betting $\frac{R-B}{R+B}$ of your total money. Similarly if $R < B$ you guess black while betting $\frac{B-R}{B+R}$ of your total money. If $R=B$ you don't bet that turn. Show that this strategy guarantees a final amount of: $$\frac{2^{2n}n!n!}{(2n)!}$$ Note: this final amount is much bigger than people think. That sum equals to: $$\left(1 + \frac{1}{2n-1} \right) \left(1 + \frac{1}{2n-3} \right) \dots \left(1 + \frac{1}{3} \right) \left(1 + \frac{1}{1} \right)$$ which is already greater than 2, and only increases as $n$ increases. This is an extension to the obvious strategy to wait until the last card before we bet the one dollar that we start with, to which we'd be guaranteed a final amount of two.

First Solution

First we claim the following: if at any point there are $R$ red cards and $B$ black cards left in the deck, and your current total is $x$, employing the above strategy will give you a final amount of: $$\frac{2^{R+B}R!B!}{(R+B)!} x$$ That claim is easily verified if either $R+B=1$ because then we would know exactly what's left in the deck. Now we prove the claim by induction on $R+B$. Clearly if $R=B$ then we don't bet that flip, and we reduced it to the case $R+B-1$. But if $R \neq B$, and WLOG we may assume that $R > B$. We bet $\frac{R-B}{W+B}$ that the next card will be red.

Case 1: the next card is red. That means our current total becomes $(1 + \frac{R-B}{R+B})x = \frac{2R}{R+B}x$. But the deck now contains $R-1$ red and $B$ black, so by our induction hypothesis, our final amount will be: $$\frac{2^{R+B-1}(R-1)!B!}{(R+B-1)!} \frac{2R}{R+B}x =\frac{2^{R+B}R!B!}{(R+B)!} x $$

Case 2: the next card is black and we lost our bet. That means our current total is now $(1 - \frac{R-B}{R+B})x = \frac{2B}{R+B}x$ and the deck contains $R$ red and $B-1$ black, so our final amount is: $$\frac{2^{R+B-1}R!(B-1)!}{(R+B-1)!} \frac{2B}{R+B}x =\frac{2^{R+B}R!B!}{(R+B)!} x $$ And the claim is proven. Now it's straightforward to apply that if $R=B=n$, we have: $$\frac{2^{2n}n!n!}{(2n)!} = \frac{(2n)(2n-2)\dots (4)(2)}{(2n-1)(2n-3) \dots (3) (1)}$$ $$= \left(1 + \frac{1}{2n-1} \right) \left(1 + \frac{1}{2n-3} \right) \dots \left(1 + \frac{1}{3} \right) \left(1 + \frac{1}{1} \right)$$

Expected number of draws

In an urn there are $n$ balls each with weight $w_i$, drawn one at a time without replacement. At any point of drawing, the probability of a ball being drawn is proportional to its weight. What's the expected number of draws before we draw ball 1?

Random walk sequences

Let $n$ be a natural number. Suppose $a_1, a_2, \dots$ are sequences of +1s and -1s. Also define $s_k = a_1 + a_2 + \dots + a_k$, and define $s_0 = 0$. Such sequence is called "complete" if for each $i \in {0, \dots, n-1}$ there exists $k$ such that $s_k \equiv i \mod n$.
What is the largest number $S$ such that the following statement is true: For every complete sequence, there exists $j,k \geq 0$ such that $|s_j - s_k| = S$.

Answer:

$n-1$

We can construct $a_i$ as follows: $n-1$ +1s, followed by $n-1$ -1s, and followed by $n-1$ +1s again, alternatingly. It's easy to see that this sequence is complete. Moreover, the sum of any contiguous block ranges from $-(n-1)$ to $(n-1)$. So clearly for this particular sequence, $S \leq n-1$ fulfills the statement, and $S > n-1$ is not satisfied by this sequence.

Now we have to prove that for $S=n-1$ and any given complete sequence, the problem statement is fulfilled.

First Solution

The sequence is infinite, but suppose we can truncate it to the smallest sequence so that it's still complete. In other words, suppose the sequence $a_1, \dots, a_N$ is complete but $a_1, \dots, a_{N-1}$ is not. Let $s_N = x$. Because $N$ is the smallest index such that it's still complete, that means $s_i \equiv x \mod n$ does not happen before $N$. Consider $a_N$. It can be either +1 or -1. Suppose it's +1 (the case of -1 is similar). So that means $s_{N-1} = x-1$.

Let $p$ be the an index such that $s_p \equiv x+1 \mod n$. We know $p$ exists because the sequence is still complete. Also that $p < N-1$. That means $s_{N-1} - s_p \equiv (x-1) - (x+1) \equiv -2 \mod n$. But from $i = p$ to $i = N-1$ we can't have $s_i = x$, so that means $s_{N-1} - s_p = tn - 2$ for some $ t > 0$. This means that $s_N - s_p = tn-1$.

But if $t > 1$, then we must have some $r$ such that $p < r < N$ and $s_N - s_r = n, s_r - s_p = (t-1)n-1$. But this yields a contradiction, because then $s_r \equiv s_N \equiv x \mod n$ and thus $a_1, \dot, a_r$ is complete, violating our condition that $N$ is the smallest complete sequence. Thus we must have that $t=1$ and consequently $s_N - s_p = n-1$

Second Solution

Suppose that there is no contiguous block whose sum is $\pm(n-1)$. Each contiguous block must have sum of at most $(n-2)$ and at least $-(n-2)$. Now, if there is $k$ such that $s_k = n-1$ then we are done, because it would imply a contiguous block from $0$ to $k$ with sum $n-1$. So let $x$ be the maximum value of $s_i$, where $x \leq n-2$. Likewise, let $y$ be the minimum value of $s_i$ where $y \geq -(n-2)$.

Because the sequence is complete, then we must have that $x-y \geq n-1$, otherwise some values won't be "reached" by $s_i$ at all. But this means that there is a contiguous block from the maximum to the minimum or vice versa, and their sum is $\pm(n-1)$

Flea on a regular polygon

We are given a regular $N$-gon. A flea originally sits on one vertex. At each turn, the flea decides to either jump to the left or to the right to the next (closest) vertex. The flea continues this movement until it has visited all vertices. Let $a_i$ be a sequence that records the flea's movement. If at $i$-th turn $(i \geq 1)$ the flea moves to the left then $a_i = -1$, and if it moves to the right then $a_i = 1$. We are told that this sequence is finite (i.e. the flea does visit all vertices and therefore stops). Show that there exists $j,k$ such that: $$| \sum_{i=j}^k a_i | = N-1$$

Four positive numbers

Let $a_1,a_2,a_3,a_4$ be four positive numbers and let: $$S_1 = a_1 + a_2 + a_3 + a_4$$ $$S_2 = \sum_{i \neq j} a_ia_j$$ $$S_3 = a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4 + a_2a_3a_4$$ $$S_4 = a_1a_2a_3a_4$$ Given that $$| \frac{S_1-S_3}{1-S_2+S_4} | < 1$$ show that there are two distinct $a_i,a_j$ such that : $$|a_i-a_j| < (\sqrt{2}-1)(1+a_ia_j)$$

Solution 1

If any two $a_i$ are the same then we are done. WLOG, we may now assume that $a_1 < a_2 < a_3 < a_4$. Suppose that for each two $a_i > a_j$ we always have: $$a_i - a_j > (\sqrt{2}-1)(1+a_ia_j)$$ Consider $a_3$ and $a_4$: $$(a_4 - a_3) > (\sqrt{2}-1)(1+a_4a_3)$$ $$(a_4 - a_3)(\sqrt{2}+1) > (1+a_4a_3)$$ $$a_4(\sqrt{2}+1 - a_3) > 1+a_3(\sqrt{2}+1)$$ Because the RHS is positive, in order for the LHS to be positive, we must have $a_3 < \sqrt{2} + 1$. Thus now we have $a_1 < a_2 < a_3 < \sqrt{2}+1$. Next, note that the function $f(x) = \frac{x + \sqrt{2} - 1}{1 - (\sqrt{2}-1)x}$ defined for $0 < x < \sqrt{2}+1$ is definite positive and strictly increasing. The assumption $$a_i - a_j > (\sqrt{2}-1)(1+a_ia_j)$$ for $j=1,2,3$ becomes: $$a_i(1 - (\sqrt{2}-1)a_j) > a_j + \sqrt{2}-1$$ And because $(1 - (\sqrt{2}-1)a_j) > 0 \iff a_j < \sqrt{2}+1$ we can divide both sides to obtain: $$a_i > \frac{a_i + \sqrt{2}-1}{1 - (\sqrt{2}-1)a_j} =f(a_j)$$ So now we have: $$a_4 > f(a_3), a_3 > f(a_2), a_2 > f(a_1)$$ We note that $f(0) = \sqrt{2}-1,f(\sqrt{2}-1) = 1, f(1) = \sqrt{2}+1$. Furthermore, because $f$ is strictly increasing, $$a_2 > f(a_1) > f(0) = \sqrt{2}-1$$ $$a_3 > f(a_2) > 1$$ $$a_4 > f(a_3) > \sqrt{2}+1$$ Also, if $a_2 \geq 1$ then we'd have $a_3 > f(a_2) > f(1) = \sqrt{2}+1$ a contradiction, so we must have $a_2 < 1$. By the same token, if $a_1 \geq \sqrt{2}-1$ we'd have $a_2 > f(a_1) > f(\sqrt{2}-1) = 1$ a contradiction, so we must have $a_1 < \sqrt{2} -1 $. Now we've established that: $$0 < a_1 < \sqrt{2} - 1 < a_2 < 1 < a_3 < \sqrt{2} + 1 < a_4$$ From there it's clear that $a_1a_3 < 1$ and $a_2a_4 > 1$. Next, we assert the following: $$a_1 + a_3 + a_1a_3 > 1$$ which is very easy to see from the bounds above. Also because $a_4 > 0$ and $a_2 < 1$, $$\frac{1}{a_2a_4} + \frac{1}{a_2} + \frac{1}{a_4} > 1$$ $$1 + a_2 + a_4 > a_2a_4$$ Therefore: $$(1-a_1a_3)(1-a_2a_4) > (a_1+a_3)(a_2+a_4)$$

Infimum of abc

Find the largest number $M$ such that for any given distinct number $a,b,c$ such that $0 < a,b,c < 1$ we always have: $$\frac{(a+b)(b+c)(c+a)}{|(a-b)(b-c)(c-a)|} > M$$

Solution

Clearly $M=1$ satisfies the condition. Now we prove that we can get the LHS arbitrarily close to 1.

Let $a$ be an arbitrary number < 1, $b = a/(1+x)$ and $c=a/(1+x+yx)$ for some really large numbers $x,y$. The LHS now becomes: $$\frac{(2+x)(2+(y+1)x)(2+(y+2)x)}{y(y+1)x^3}$$ $$=(\frac{2}{x}+1)(\frac{2}{x(y+1)} + 1)(\frac{2}{xy} + \frac{2}{y} + 1)$$ We can set $x,y$ large enough that the expression is as close as needed to 1.