Let $k \geq 1$ and $N>1$ be two integers. On a circle are placed $2N+1$ coins all showing heads. Calvin and Hobbes play the following game. Calvin starts and on his move can turn any coin from heads to tails. Hobbes on his move can turn at most one coin that is next to the coin that Calvin turned just now from tails to heads. Calvin wins if at any moment there are $k$ coins showing tails after Hobbes has made his move. Determine all values of $k$ for which Calvin wins the game. Proposed by Tejaswi Navilarekallu
Problem
Source: INMO 2023 P4
Tags:
15.01.2023 15:08
My solution (also the official one). Calvin wins if $k \in \{1, 2, \dots, N+1\}$ and Hobbes wins otherwise. Label the coins $1, 2, \dots, 2N+1$. Note that if $k \geq N+2$ then Hobbes wins as follows: he pairs the coins $2i-1$ and $2i$ for $1 \leq i \leq N$. If Calvin in a move makes both coins in a pair tails, Hobbes in that move turns the one which was tails prior to Calvin's move back to heads. Thus, he can ensure that after his move, no pair has more than one tails. So, the number of tails after his move is $\leq 1+\frac{(2N+1)-1}{2}=N+1$, hence Hobbes wins. If $k \leq N$, then Calvin wins by simply turning coins $2i$ for $1 \leq i \leq N$. Now let $k=N+1$. Let $N=2m+\varepsilon$ where $\varepsilon \in \{0, 1\}$. Now consider $m$ arcs on the circle with the $i$th arc containing $\{4i+1, 4i+2, 4i+3, 4i+4\}$, for all $0 \leq i <m$. Calvin makes $3m$ moves as follows: on move $3i+1, 3i+2,$ and $3i+3$, he turns coins numbered $4i+2, 4i+4,$ and $4i+3$, respectively, to tails, for all $0 \leq i<m$. Thus, no matter what Hobbes does, each arc will have either $\{4i+2, 4i+3\}$ tails (type $\widehat{23}$), or $\{4i+3, 4i+4\}$ tails (type $\widehat{34}$), or all of $\{4i+2, 4i+3, 4i+4\}$ tails (type $\widehat{234}$), by the end of these $3m$ moves. We now split into cases: Case 1. $\varepsilon=0$. In this case, if we have any arc of type $\widehat{234}$, we get that there are $\geq 3+2(m-1)=N+1$ tails at the end and the game is won. Assume all arcs are of type $\widehat{23}$ or $\widehat{34}$; hence we currently have $2m$ tails. Now, if $4m+1$ has no tails neighbours, Calvin turns it to win. So assume the arc $\{4m-3, 4m-2, 4m-1, 4m\}$ is of type $\widehat{34}$. If $\{1, 2, 3, 4\}$ is also of type $\widehat{34}$, Calvin can turn $1$ to tails to win as it has no tails neighbours. If it is of type $\widehat{23}$, then we must have an $0 \leq i<m-1$ such that the $i$th arc is of type $\widehat{23}$ but the $(i+1)$th arc is of type $\widehat{34}$, which means that Calvin can turn $4i+1$ to tails to win, as it has no tails neighbours. Case 2. $\varepsilon=1$. Again, if we have any arc of type $\widehat{234}$, Calvin turns $4m+2$ and we end up with $\geq 3+2(m-1)+1=N+1$ tails at the end and the game is won. Assume all arcs are of type $\widehat{23}$ or $\widehat{34}$; hence we currently have $2m$ tails. If Calvin can turn $4m+1$, then he wins, by turning $4m+3$ next move; so assume the arc $\{4m-3, 4m-2, 4m-1, 4m\}$ is of type $\widehat{34}$. If $\{1, 2, 3, 4\}$ is of type $\widehat{34}$, then Calvin can turn $1$ and $4m+2$ to secure his win; so assume $\{1, 2, 3, 4\}$ is of type $\widehat{23}$. Thus, there exists $0 \leq i<m-1$ such that the $i$th arc is of type $\widehat{23}$ and the $(i+1)$th arc is of type $\widehat{34}$, hence Calvin wins by turning $4m+2$ and $4i+1$, in the next two moves.
15.01.2023 15:44
I am not sure what is done above but here's what I did: Pair $\{1,2,\ldots,2N\}$ (so they form $N$ pairs) and box $2N+1$ (home alone). Easy to see Calvin can flip $N$ coins no two adjacent. Now show that he can manage to flip the unpaired square by cleverly forming $TT$. For Hobbes, he can ensure each pair is never $TT$. So $\le 1\cdot N+1=N+1$.
15.01.2023 15:55
Answer is $k \leqslant N+1$, Calvin achieves this by (assuming Hobbes doesn't mess up and make it easier for him) flipping $C_1, C_3, \cdots, C_{2N-3}$, then $C_{2N-2}, C_{2N-4}, \cdots, C_{2}$ and finally $C_{2N+1}$. For Hobbes strategy, he pairs coins into $N$ consecutive groups of two plus an extra one and ensures there's at most one tail in ever pair.
16.01.2023 01:23
We shall prove that $k \leq N+1 $ works. We shall show there exists a winning strategy for each such value. First we show that for $k > N+1 $ there is no solution. Proof: Let there be $N+1$ many coins with heads arranged up. Let the number of coins in gaps be $x_1,x_2,… x_N$ Note $\sum_{i=1} ^{N} x_i= N$ and $x_i > 0$ which gives $ x_i = 1 $ under such conditions for each $i=1,2,…N$. Note that for gap size $= x_i =0$, Hobbes can always flip one of Calvin’s coins if the number of tails reaches $k$. Note now that for $k> N+ 1$, one of $x_i$, i.e one gap size must be zero. which shows us that Calvin doesn’t have a winning strategy completing the proof. For $k \leq N +1 $ , we continue with the construction. At each step Calvin can flip a coin tails such that it isn’t adjacent to any coins facing tails up to $k= N +1$. For each k, the gap sizes are $>0$ implying that for each such k, Hobbes cannot make a move and Calvin wins the game! Such a construction can be shown by considering a $k-sized$ subset of tails from $k= N+1$-configuration and flipping those coins at each step. It is rather trivial to see these coins aren’t adjacent from construction.