Given a circular list of coins with Tails facing up. In each move, if we flip coin at position $i$, coins at positions $i-1$ and $i+1$ get flipped as well. That is, consider: $H H H T T$ : if I flip coin at index 3 (0-based indexing), then the result would be: $H H T H H$. ($H$ -> $T$ & $T$ -> $H$)
Initial state: $T T T T T … (N coins)$
Final state: $H H H H H … (N coins)$
What would be the minimum number of moves to make all coins have Heads facing up?
Best Answer
Consider $V:=\mathbb{F}_2^n$. Denote by $[n]$ the set $\{1,2,\ldots,n\}$. For $i\in[n]$, let $\mathbf{e}_i$ be the vector in $V$ with $1$ at the entry $i$, and $0$ everywhere else. A vector $\mathbf{v}=\sum_{i=1}^n\,a_i\mathbf{e}_i$ in $V$, where $a_1,a_2,\ldots,a_n\in\mathbb{F}_2$, is associated to the state where, for $i\in[n]$, the coin $i$ is heads up if and only if $a_i=1$.
For $i\in[n]$, let $\mathbf{u}_i:=\sum_{j=1}^m\,\mathbf{e}_{i+j-1}$, where indices are consider modulo $m$. Write $\mathbf{1}$ for the all-$1$ vector $\sum_{i=1}^n\,\mathbf{e}_i$. Now, the required task is possible if and only if there are $a_1,a_2,\ldots,a_n\in\mathbb{F}_2$ such that $\sum_{i=1}^n\,a_i\mathbf{u}_i=\mathbf{1}$. The smallest number of moves required is then the smallest possible value of $k:=\Big|\big\{i\in[n]\,\big|\,a_i\neq 0\big\}\Big|$. Observe that $$\sum_{i=1}^n\,\mathbf{e}_i=\mathbf{1}=\sum_{i=1}^n\,a_i\mathbf{u}_i=\sum_{i=1}^n\,a_i\,\left(\sum_{j=1}^m\,\mathbf{e}_{i+j-1}\right)=\sum_{i=1}^n\,\left(\sum_{j=1}^m\,a_{i-j+1}\right)\,\mathbf{e}_i\,.$$ That is, for each $i\in[n]$, $\sum_{j=1}^m\,a_{i-j+1}=1$. Hence, for all $i\in[n]$, $\sum_{j=1}^m\,a_{i-j+1}=\sum_{j=1}^m\,a_{(i-1)-j+1}$, or equivalently, $$a_i=a_{i-m}\,.$$ If $d:=\gcd(m,n)$, then we conclude that $a_i=a_{i+d}$ for every $i\in[n]$. Let $t\in\mathbb{N}$ be such that $m=td$. Thus, $1=\sum_{j=1}^m\,a_{i-j+1}=t\,\sum_{j=1}^d\,a_j$ for any $i\in[n]$. Therefore, the task is possible if and only if $t$ is odd, which is equivalent to saying that $\frac{m}{d}=\frac{m}{\gcd(m,n)}$ is odd.
Now, the minimum value of $k$ is attained when exactly one among $a_1,a_2,\ldots,a_d$ is $1$ (and the remaining numbers are $0$). That is, the smallest possible value of $k$ is $\frac{n}{d}=\frac{n}{\gcd(m,n)}$.