Let $1 \leq n \leq 2021$ be a positive integer. Jack has $2021$ coins arranged in a line where each coin has an $H$ on one side and a $T$ on the other. At the beginning, all coins show $H$ except the nth coin. Jack can repeatedly perform the following operation: he chooses a coin showing $T$, and turns over the coins next to it to the left and to the right (if any). Determine all $n$ such that Jack can make all coins show $T$ after a finite number of operations.
Problem
Source: 2020 Thailand October Camp 1.3
Tags: combinatorics, coins
NTstrucker
24.02.2022 18:53
$n=1011$.
Use induction to show that if $m=2n+1$ is odd, $\underbrace{H \cdots H}_{n} T \underbrace{H \cdots H}_{n}$ can change to $\underbrace{T \cdots T}_{2n+1}$ without choosing the leftmost or the rightmost coins.
If $m=3$, $HTH \to TTT$.
If $2n-1$ works, we prove it for $m=2n+1$. First use induction hypothesis to obtain $H \underbrace{T \cdots T}_{2n-1} H$. (because we never choose the $2$ nd or the $2n$ th coins, the leftmost and the rightmost coin doesn't change.) Then we can perform like $H \underbrace{TTT \cdots TTT}_{2n-1} H \to TTH \underbrace{T \cdots TTT}_{2n-3} H \to \cdots \cdots \to T \underbrace{TTT \cdots T}_{2n-3} HTH \to \underbrace{T \cdots T}_{2n+1}$.
Regard the coin sequence as mappings: $H(x)=x+1$ and $T(x)=-x$. For example, $HTH$ is $H \circ T \circ H (x)=H(T(H(x)))=-x$.
To deal with the leftmost and the rightmost coins, we add an "invisible" coin $H$ at each end. Jack cannot choose the invisible coin, but when he choose the leftmost or the rightmost coin, the invisible coin should also be turned over.
It's easy to verify that $H \circ T \circ H = T \circ T \circ T = T$, and $H \circ T \circ T = T \circ T \circ H = H$, so the operation doesn't change the mapping.
Initially, the mapping is $H^n \circ T \circ H^{2022-n} (x)=-x+2n-2022$ (note that we add an $H$ at both ends), and the target mapping is $U \circ T^{2021} \circ V (x)=U(-V(x))$, where $U, V \in \{H,T \}$ is unknown. Because $H(-H(x))=-x$, $H(-T(x))=x+1$, $T(-H(x))=x+1$, $T(T(x))=x$, the linear coefficient and the parity together show that the only possibility is that $-x+2n-2022=-x$, so $n=1011$.