There is a heads up coin on every integer of the number line. Lucky is initially standing on the zero
point of the number line facing in the positive direction. Lucky performs the following procedure: he
looks at the coin (or lack thereof) underneath him, and then,
- If the coin is heads up, Lucky flips it to tails up, turns around, and steps forward a distance of
one unit.- If the coin is tails up, Lucky picks up the coin and steps forward a distance of one unit facing the
same direction.- If there is no coin, Lucky places a coin heads up underneath him and steps forward a distance of
one unit facing the same direction.He repeats this procedure until there are 20 coins anywhere that are tails up. How many times has
Lucky performed the procedure when the process stops?
Source: HMMT 2014 Problem 9 (with an official solution)
In the official solution, 4 claims are made:
We keep track of the following quantities: Let $N$ be the sum of $2^k$, where $k$ ranges over all nonnegative integers such that position $−1 − k$ on the number line contains a tails-up coin.
Let $M$ be the sum of $2^k$
, where $k$ ranges over all nonnegative integers such that position $k$ contains a tails-up coin.We also make the following definitions: A "right event" is the event that Lucky crosses from the
negative integers on the number line to the non-negative integers. A "left event" is the event that
Lucky crosses from the non-negative integers on the number line to the negative integers.We now make the following claims:
- Claim (a): Every time a right event or left event occurs, every point on the number line contains a coin.
- Claim (b): Suppose that $n$ is a positive integer. When the $n$th left event occurs, the value of $M$ is equal to
$n$. When the $n$th right event occurs, the value of $N$ is equal to $n$.- Claim (c): For a nonzero integer $n$, denote by $\nu_2(n)$ the largest integer $k$ such that $2^k$ divides $n$. The number
of steps that elapse between the $(n−1)$st right event and the $n$th left event is equal to $2\nu_2(n)+1$.
The number of steps that elapse between the $n$th left event and the $n$th right event is also equal
to $2\nu_2(n)+1$. (If $n − 1 = 0$, then the “$(n − 1)$st right event” refers to the beginning of the
simulation.)- Claim (d): The man stops as soon as the $1023$rd right event occurs. (Note that $1023 = 2^{10} − 1$.)
Below is my attempt of a proof of claims (a)-(d) except (b), which was proved in the official solution. I'd appreciate any simpler solutions and an answer to my question at the end.
We prove claims (a)-(d) except claim (b) below.
Proof of claim (a):
We use induction on the total number of right and left events to prove the following stronger claim: right after each event, there exist some nonnegative integers $l$ and $m$ so that points $0$ to $l-1$ contain tails up coins, points $-m$ to $-1$ contain tails up coins, and points $l$ and $-(m+1)$ contain heads up coins and all other points contain coins.
The claim holds trivially in the base case where no events have occurred.
Suppose the some (possibly zero) events have occurred. Suppose first that a right event just occurred (we consider the starting point to be the end of the 0th right event) and Lucky is currently at point $0$ and facing in the positive direction. Then Lucky picks up the coins at points $0$ to $l-1$, turns over the coin at point $l$, puts heads up coins at points $l-1$ down to $0$ and then moves to point $-1,$ causing a left event to occur, and the claim holds.
If a left event just occurred, then Lucky is at point $-1$. Since Lucky only performed a finite number of moves, only a finite number of tails up coins are on the number line. Lucky then proceeds to pick up all tails up coins from $-1$ down to $-m$ for some nonnegative integer m where m is maximal so that the coins at points $-1$ down to $-m$ are tails up, flips the heads up coin at $-(m+1)$, and places heads up coins at $-m$ to $-1$. Lucky then moves to point $0$ and a right event occurs. At this point, the claim of the inductive hypothesis still holds, since coins at $0$ to $l-1$ are unchanged.
Proof of claim (c):
For convenience, say a point $x$ is tails up if there is a tails up coin at it and define a heads up point similarly. Also say that for a positive integer $n$, bit $k$ in $n$'s binary representation is the bit with value $2^k.$
Note that since right and left events alternate, with a left event occurring first, then the $n$th left event always precedes the $n$th right event and the $(n+1)$th left event follows the $n$th right event (which follows by induction). Thus, by claim (b) and the above observation, after the $(n-1)$th right event, $M=n-1, N=n-1$. In particular, the point $k\ge 0$ is tails up iff $2^k$ has a nonzero coefficient in the binary representation of $n-1$. Now if $k=v_2(n)$, we know that points $0,\cdots, k-1$ are all tails up, since the bits with values $2^0,\cdots, 2^{k-1}$ in the binary representation of $n-1$ must all be $1$'s and bit $k$ is $0$ because otherwise we'd get a contradiction to the maximality of $k$. Hence $k$ steps are taken to pick up the coins at points $0$ to $k-1,$ and k+1 more steps to place heads up coins at $k-1,\cdots, -1$. After this, the $n$th left event occurs. This proves the first part of the claim.
Now to prove the second part, suppose the $n$th left event has just finished, where $n\ge 1.$ Then Lucky is at point $-1$. Let $k=v_2(n).$ Then since $N$ equals $n-1$ at this point, point $-1-k$ is tails up iff bit $k$ in the binary representation of $n-1$ is a $1$. By the definition of $k$, bits $0$ to $k-1$ in the binary representation of $n-1$ are $1$ while bit $k$ is a zero. Hence Lucky picks up the $k$ coins at $-1,-2,\cdots, -k$, flips over the heads up coin at $-k-1$, and puts heads up coins at $-k,\cdots, -1$ and then moves to point $0$. At this point, the $n$th right event occurs and exactly $2k+1$ steps have occurred, as required.
Finally, Proof of claim (d):
We just need to consider the end of a left or right event. (Why?) The man stops precisely when $N$ has $x$ ones and $M$ has $y$ ones in their binary representation, where $x+y = 20$. If the man stopped at the nth left event, then $M=n, N =n-1$. If the man stopped at the nth right event, then $N=n,M=n$. Note that the number of ones in the binary representation of $n-1$ is the number of ones in the binary representation of $n$ plus $v_2(n)-1.$ So we need to find the smallest positive integer $n$ so that $2B(n) + v_2(n)-1 = 20$ or $B(n)=10,$ where $B(n)$ is the number of ones in the binary representation of $n$.
The smallest $n$ with $B(n)=10$ is $1023.$ If $B(n)<10,$ then $v_2(n) = 21 – 2B(n)\ge 3,$ so $n$ is divisible by $8$. If $B(n)\leq 5,$ then $n$ is divisible by $2^{10}$ and thus would be larger than $1023.$ $n$ is at least $2^{v_2(n)} \cdot (2^{B(n)}-1),$ since $n/2^{v_2(n)}$ has $B(n)$ ones in its binary representation. Thus if $B(n)= 6,7,8,9$ then $n$ is at least the minimum of $2^9\cdot 63, 2^7\cdot 127, 2^5\cdot 255, 2^3\cdot 511,$ all of which exceed $1023$. If the man has yet to complete the nth right event, then $N$ is strictly less than $n$ and $M$ is at most $n$ (by the proof of claim (b) in the official solution, in between a left event and the subsequent right event or vice versa, $M$ or $N$ respectively decrease, and only increase by $1$ when Lucky turns over a heads up coin before turning around and placing tails up coins.
But doesn't the man stop just before he completes the $n$th right event?
Best Answer
Your proof for claim (a) and (c) are pretty good. There would have been less repetition of arguments had we proved claim (a), (b), (c) and (d) together.
In order to prove claim (d), it is not necessary to show how we can find/determine when there have been 20 tails-up coins anywhere for the first time. It is enough to prove the following claim.
Claim (d'): There have never been $20$ tails-up coins (at any moment) before the procedure in which the $1023$rd right event occurs. There are $20$ tails-up coins right after the $1023$rd right event.
As in the question, let $B(n)$ denote the number of ones in the binary representation of $n$. Note that $1023=2^{10}-1=(1111111111)_2$ is the smallest natural number $n$ such that $B(n)\ge10$.
It is straightforward to verify the second statement of claim (d'), thanks to claim (b).
Let us prove the first statement.
Along the proof for claim (b), we can show right after the $M$-th left event, the maximum number of tails-up coins at or to the right of $0$ that have ever occurred is the maximum $B(n)$ for all natural number $n\le M$. Symmetrically, right after the $N$-th right event, the maximum number of tails-up coins to the left of $0$ that have ever occurred is the maximum $B(n)$ for all natural number $n\le N$
Suppose Lucky is at the moment at the end of procedure in which the $1023$rd left event occurs, which is also the moment right after the $1023$rd left event.
The coins at or the left of $-1$ have not been changed since the $1022$nd right event. Claim (b) implies the coin at $-1$ is a heads-up coin since $N=1022$ is an even number. Since Lucky is at $-1$ facing left with a heads-up coin underneath, the $1023$rd right event will occur in the very next procedure. Hence, what we want to prove is the same as there have never been $20$ tails-up coins so far.
The most number of tails-up coins that have ever occurred is at most the sum of the following two:
Hence the most number of tails-up coins that have ever occurred is $10+9=19$. We are done.