0
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ This problem is here (or maybe puzzling.stackexchange) already, using light switches instead of coins. $\endgroup$ Jul 19 '15 at 2:50
  • $\begingroup$ Try smaller cases first and try to find a pattern. For $N=1,2,3,4,5,6,$ the values are $1,1,1,2,2,2$. What have you tried? What are you thinking? $\endgroup$ Jul 19 '15 at 3:22
  • $\begingroup$ Should I take $i\pmod N$? so that there are always three coins flipped? $\endgroup$
    – Empy2
    Jul 19 '15 at 3:54
  • $\begingroup$ You said that the list is circular, so if we have N coins and we flip the Nth coin, the (N-1)th and the first coin will be flipped too, won't they? In the same way, if we flip the first coin, the Nth coin and the second coin will be flipped too, right? $\endgroup$
    – Ramiro
    Jul 19 '15 at 4:06
  • 3
    $\begingroup$ You already received an answer to this question verbatim on Puzzling.SE. If you do cross-post a question, you should provide links to the other to avoid duplicated effort. However, I am confused as to why you are posting this given that the answer given elsewhere was quite complete. $\endgroup$ Jul 19 '15 at 20:32
3
$\begingroup$

Problem: Let $m,n\in\mathbb{N}$. There are $n$ coins labelled $1$, $2$, $\ldots$, $n$. A move consists of a selection of $i\in\{1,2,\ldots,n\}$ and flipping of coins $i,i+1,i+2,\ldots,i+m-1$ (where the coin labels are considered modulo $n$). Initially, all coins are tails up. When is it possible to flip these coins according to the rule so that they are heads up? When this task is possible, what is the minimum number of moves required?

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)}$.


Note: If a move is define to be choosing $i\in\{1,2,\ldots,n\}$ and flipping all coins with labels in $\left\{i-r,i-r+1,\ldots,i-r+m-1\right\}$ (here, labels are not considered modulo $n$) where $r\in\mathbb{Z}$ such that $0\leq r <m$ is fixed, then the task is always possible with the minimum number of moves being $\left\lceil\frac{n}{m}\right\rceil$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.