Multi-Player Coin Game

We sort the $n$ coins into $8$ groups - Groups $1, 2,.. 8$ - where Group $j$ consist of all the coins that has position $j \pmod{8}$ .

The aim of the game is to make all of the first $n-7$ coins tails, while heads/tails in the last $7$ coins do not matter. If $n \equiv k \pmod{8}$ , where $k = 0,1,2..7$ , then the 8th last coin would be in Group $k+1$ . The last $7$ coins would not be in Group $k+1$ , and thus we can conclude that all coins in Group $k+1$ must be tails. Note that each player will flip $8$ consectutive coins in his/her turn, and therefore, the number of heads in each group will either increase or decrease by $1$ after each player's turn. We know look specifically at Group $k+1$ . If it originally has an odd number of heads, after two players' turn, it'll still always be odd (and never even). This means that the second player can never win, since the number of heads in Group $k+1$ will never be $0$ . We could then say that with enough moves, the first player will eventually win. Conversely, if Group $k+1$ originally has an even number of coins, the first player will never have a winning strategy.

We now count which cases will cause Group $k+1$ to have an odd number of coins. Every $16$ coins will produce an even number of coins in Group $k+1$ , and we can remove $16$ coins by $16$ starting from the beginning. The leftover coins would be coins from Group $1$ to Group $k+1$ , followed by the last $7$ coins. So to have an odd number of coins, we must have $n \equiv (k+1)+7 \equiv k+8 \pmod{16}$ , where $k = 0,1,2...7$ .

This means that if $n \equiv 8, 9,...,15 \pmod{16}$ , the first player will have a winning strategy for the game. So we have 8 winning games for every 16 consecutive games. $1031 = 64 \times 16 + 7$ , and the last 7 cases $n = 1129, 1130, ... 1135 \equiv 9, 10, ...,15 \pmod{16}$ are winning games for the first player as well. Therefore, we have $64 \times 8 + 7 = 519$ games where the first player has a winning strategy.

Before we determine which player has a winning strategy for a game with $n$ coins, we first prove that, given any particular $n$ , one of the players will always have a valid move (and will thus never lose).

Sort the $n$ coins into $8$ groups $A_0, A_1, ... , A_7$ , such that the coin at position $k$ (from the left) is in $A_{k'}$ , where $k \equiv k' \pmod{8}$ and $k'$ is an integer between $0$ and $7$ inclusive. For a game with $n$ coins, the first $n-7$ coins from the left have at least $7$ coins to the right of it, so it is possible to form a row of $8$ coins using any of the first $n-7$ coins as the leftmost coin. Thus, if at least one of the first $n-7$ coins shows heads during a particular turn, then the player will definitely not lose during that turn, since that player can make a valid move by flipping any of the first $n-7$ coins that shows heads. The last $7$ coins are in $7$ distinct groups, which are all the $A_i$ where $i$ is congruent to one of $(n-6), (n-5), ... , n$ modulo $8$ and $i$ is an integer between $0$ and $7$ inclusive. The only group which does not contain any of the last $7$ coins is thus $A_m$ , where $m \equiv n-7 \equiv n+1 \pmod{8}$ and $m$ is an integer between $0$ and $7$ inclusive. This group thus contains only coins from the first $n-7$ coins, which means that a player does not lose during a particular turn if there is at least one coin in $A_m$ that shows heads during that turn. Now we consider the number of coins in $A_m$ that show heads. During each turn, the player for that turn will flip $8$ coins in a row, which means that the player will flip exactly $1$ coin in $A_m$ . So, after every turn, the number of coins in $A_m$ that show heads will either increase or decrease by $1$ , i.e. its parity will change. This parity thus remains unchanged every two turns. In other words, the parity of the number of coins in $A_m$ showing heads right before a player's turn is invariant with respect to each player (and will be different for both players). All the coins show heads initally, so if the number of coins in $A_m$ was initially odd, then the parity of the number of coins in $A_m$ showing heads will always be odd (and thus non-zero) right before the first player's turn. So there must be at least one coin in $A_m$ that shows heads during the first player's turn (at any point during the game), and as proven earlier, the first player will thus never lose. On the other hand, if the number of coins in $A_m$ was initially even, then the parity of the number of coins in $A_m$ showing heads will always be even right before the first player's turn, and thus always odd (and non-zero) right before the second player's turn. So there must be at least one coin in $A_m$ that shows heads during the second player's turn (at any point during the game), and the second player will thus never lose in this case. We now find the relationship between the number of coins in $A_m$ and $n$ . Let $n \equiv n' \pmod{8}$ , where $n'$ is an integer between $0$ and $7$ inclusive. Then the number of coins in $A_m$ within the first $n$ coins is the same as the number of coins in $A_m$ within the first $n - n'$ coins, since $A_m$ does not contain any of the last $7$ coins. Furthermore, since $n-n' \equiv 0 \pmod{8}$ , the number of coins in $A_j$ within the first $n-n'$ coins are all the same (as $j$ ranges from $0$ to $7$ ). So, the number of coins in $A_m$ is equal to $\frac{n-n'}{8}$ . Letting the number of coins in $A_m$ be $x$ , we have $8x = n-n'$ . If $x$ is odd (i.e. first player never loses), then $n-n'=8(2y+1)=16y+8$ for some integer $y$ , i.e. $n = 16y+8+n' \equiv 8+n' \pmod{16}$ . If $x$ is even (i.e. second player never loses), then $n-n'=8(2z)=16z$ for some integer $z$ , i.e. $n = 16z+n' \equiv n' \pmod{16}$ . Keeping in mind that $n'$ is an integer between $0$ and $7$ inclusive, we thus conclude that the second player never loses when $n \equiv 0,1,...,7 \pmod{16}$ while the first player never loses when $n \equiv 8,9,...,15 \pmod{16}$ .

We have established that, given any particular $n$ , one of the players will always have a valid move (and will thus never lose), but we have not shown that this player will necessarily win (because the game may go on indefinitely and not produce a winner). We shall proceed to show that this player can play in a way so as to force a win. During this player's turn, he or she should choose the $8$ coins such that the leftmost coin of these $8$ coins is the leftmost coin showing heads among the first $n-7$ coins. (Note that we have already proven earlier that such a coin always exists for the never-losing player.) Since there are no other coins showing heads to the left of this coin, this coin will never ever be affected by any future moves after being flipped to tails in this move, i.e. it will permanently show tails. So the total number of coins which must permanently show tails will increase by at least one after this player's move. But this number cannot increase indefinitely, since there can be a maximum of $n$ coins which show tails (owing to the fact that there are only $n$ coins). Therefore, assuming the never-losing player adopts this strategy, when the number of coins which must permanently show tails reaches the maximum (and cannot increase anymore), it must be the other player's turn. Thus, this (latter) player will lose, since the first $n-7$ coins all show tails and he or she will have no more valid moves. (Note that if any of the first $n-7$ coins shows heads, then the maximum number of coins which must permanently show tails is not yet reached since we can flip the leftmost coin which shows heads to make it permanently show tails.) Therefore, we have constructed a winning strategy for the never-losing player.

Now it remains to calculate the number of games for which the first player has a winning strategy, i.e. the number of integers between $105$ and $1135$ inclusive which are congruent to $8,9,...,15$ modulo $16$ . For any $16$ consecutive integers, there will be exactly $8$ that satisfy the criteria. Since $1031 = 64\times 16 + 7$ , we know that there will be $64\times 8 = 512$ games among the first $64\times 16 = 1024$ games (i.e. $n=105,106,...,1128$ ) where the first player has a winning strategy. For the remaining $7$ games where $n=1129,1130,...,1135$ , then $n \equiv 9,10,...,15 \pmod{16}$ , so all these $7$ games are games where the first player has a winning strategy. Therefore, the total number of games where the first player has a winning strategy is $512+7=519$ .

Number the coins from right to left as $C_1, C_2, \ldots, C_n$ . Each time a player makes a move, one of the coins in the set $C = \{C_{8}, C_{16}, \ldots, C_{8 \times \lfloor\frac{n}{8}\rfloor}\}$ will get flipped. When there are no more legal moves, none of the coins in $C$ will be showing heads. When the game starts, there are $\lfloor\frac{n}{8}\rfloor$ coins in $C$ that show heads. So when $\lfloor\frac{n}{8}\rfloor$ is odd, the first player will always win the game and when $\lfloor\frac{n}{8}\rfloor$ is even, the second player will always win the game.

To determine how many of the starting positions are winning positions for the first player, we first observe that if $k$ coins is a winning position, then $k + 8$ is a losing position and $k+16$ is a winning position. $1031 = 64 \times 16 + 7$ , so we can say that half ( $512$ ) of the first $1024$ positions (from $105$ to $1128$ ) are winning for the first player and half are losing. It remains to check the positions from $1129$ to $1135$ . We observe that $\frac{1128}{8} = 141$ , so $1129$ through $1135$ are winning. So $512 + 7 = 519$ of the possible $1031$ starting positions are winning for the first player.