Pages

Bookmark and Share

Wednesday, May 2, 2018

Marking number game

Let $n > 2$ be an even number. On the board, there are numbers $1, 2, \dots, n$, and initially the number 1 is marked, and no other numbers are marked. Alice and Bob are playing a game, with Alice moving first. On each turn, they may choose a number $k$ that is currently unmarked, and mark it, provided: $k+1$ was previously marked, OR $k$ is even and $k/2$ was previously marked. The player who gets to mark the number $n$ wins the game.

Determine all $n$ such that Alice has a winning strategy.

Solution

As soon as one player marks $n/2$, then he/she loses, because the opponent can mark $n$ directly after that. Also, the number $n$ can be marked ONLY after $n/2$ is marked (by virtue of $n/2$ being marked, since there is no number $n+1$ on the board). Therefore, the crux of the game is to avoid the number $n/2$ at all costs.

Suppose $n = 2m$. Define the numbers in set $\{ 2,3,\dots, n-1 \}$ to be "accessible" if it can be marked without ever marking $m$. Obviously $m$ is not accessible. Let $A$ be the set of accessible numbers. For example, for $n=12$ the accessible numbers are: $A = \{ 2, 3, 4, 7, 8 \}$. Note that 6 is not accessible by definition. 5 is not accessible because in order to mark 5, we'd have to go through 6. 11 is not accessible because it can't be reached without marking 12, which has to go through 6. 10 is also not accessible because it can only be reached through 11 or 5, both of which are not accessible. Therefore 9 is also not accessible.

Now, as long as there's an unmarked number in $A$, then the current player can always choose a legal move to play. Not all unmarked numbers in $A$ will be eligible to be marked, but by the construction of $A$, we can reach that number through other numbers that have been marked (and therefore also in $A$), so as long as there exists an unmarked number in $A$, there is a legal move to be played.

As soon as all numbers in $A$ are marked, then the next person has to mark $m$, and the other player can win immediately. In the case of $n=12$ above, 10 will not ever be marked because as soon as 6 is marked, the next person marks 12. Therefore the winner of the game (assuming both sides play optimally) depends on the parity of $|A|$. Alice has a winning strategy if and only if $|A|$ is odd.

Generally all the numbers from $\{2, 3, \dots, 2m-2 \}$ are accessible, with a handful of exception. $m$ is by definition inaccessible, and $2m-1$ is also inaccessible. So we want to list all the numbers that are not accessible. We divide into two cases.

If $m$ is odd:

Consider the sequence: $1,2,4,3,6,5,8,7, \dots, 2k, 2k-1, 2k+2, 2k+1, \dots, 2m-2, 2m-3$. That is a legal sequence to mark numbers. Therefore, almost all numbers in the set $\{2, 3, \dots, 2m-2 \}$ are accessible except $m$, because we can simply go through the sequence, and only skipping $m$. No further interruption to the sequence will occur because the highest number in the sequence is $2m-2 < 2m$ so it's not affected by the fact that $m$ was never marked. Thus, $A = \{2, \dots, 2m-2 \} - \{ m \}$, and $|A| = 2m-4$. This means Alice does not have a winning strategy because Bob has a winning strategy.

If $m$ is even:

Same as before, we go through the sequence, but skipping $m$. This has several ramifications. First, because $m$ is even, then $m-1$ is not accessible. Thus, there are two numbers that are also "deleted" from that sequence later on: $2m-2, 2m-3$. The rest of the sequence is not affected, because $m+2, m+4,m+6,\dots, 2m-4$ can still be marked. Thus: $|A| = 2m-3 - 4 = 2m-7$. This means Alice has a winning strategy.

This reasoning breaks down when $m=2$ because then $2m-2 = 2$ so there was no other choice and Bob wins. But this is the only corner case. Therefore, Alice has a winning strategy if and only if $n > 4$ and $n$ is divisible by 4.

No comments:

Post a Comment