Arrangement of dimes to bring all heads

Question

Consider an arrangement of n dimes in a straight line. A move consists of taking a dime and turning it over (from head to tail or vice versa) and of doing the same to each of its neighbors. If the dime is at the end of the line, then it will have only one neighbor. For example, if the arrangement is HHTH and you choose the second dime, then your move would result in TTHH. The general question is this: Given any arrangement of n dimes, is it possible to find a sequence of moves to bring it to all heads?

Answer 1

Thanks @saulspatz for the numerical evidence, without which I could not have found this proof:

For any length $k$, going from the left to the right in one pass, find the first T, flip it to H without affecting all the Hs to its left. E.g. HHTTH -> HH(TTH) -> HH(HHT). By doing so you are left with either all Hs (done) or all Hs except the rightmost position is T. In the this latter case:

• if $k = 3n$, you have $3n-1$ Hs. Go from right to left in one pass, flip non-overlapping sets of 3 coins to T, and the final set of 2 coins also to T. Now you have all Ts. Flip them all over to Hs, which is doable because $k=3n$.

• if $k = 3n+1$, you have $3n$ Hs. Do the same as above to get to all Ts. Now flip them as $2 + 3 + 3 + \cdots + 3 + 2$ back to all Hs.

The above procedure constructively proves that the problem is solvable for all $k= 3n$ or $3n+1$.

To show that $k=3n+2$ is NOT solvable first observe that in any sequence of moves, if you make the same move, i.e. at a certain position $i$, twice, their effects cancel out, EVEN IF they were done at separate (discrete) time in the sequence. Thus any move sequence (of any length) actually boils down to a subset of all possible moves. There are $k$ possible moves, so there are only $2^k$ subsets. For the problem to be solvable, each subset must have a DIFFERENT effect, since there are $2^k$ possible starting positions. However, for $k=3n+2$, the moves $3 + \cdots + 3 + 2$ and the moves $2 + 3 + \cdots + 3$ have the same effect. So the no. of all possible effects $< 2^k$ and some starting position must be unsolvable.

ALTERNATE VIEW: The move at position $j$ ($1 \le j \le k$) can be modeled as a $k$-vector $v_j$ with $1$s at positions $j-1, j, j+1$ (ignore out of range entries) and $0$ everywhere else. Then doing the $j$th move and then the $j_2$th move can be modeled as $v_j + v_{j_2}$ mod2, and doing a subset $M$ of moves can be modeled as $\sum_{j \in M} v_j$. This suggests a matrix representation. (Assume mod2 from now on.)

Let $A$ be the (tri-diagonal) $k \times k$ matrix where $A_{ij} = 1$ if $|i-j|\le 1$ and $0$ otherwise. So a subset $M$ of moves can be represented as a $k$-vector $m$ where $m_j = 1$ if $j \in M$ and $0$ otherwise, and doing those moves have effect $A m$, i.e. the end result is flipping all positions $p$ where $[Am]_p = 1$.

Any given starting position can be represented by a $k$-vector $t$ where $t_j = 1$ if the $j$th position is T, and $0$ if it is H. So solving $t$ means finding $m$ s.t. $t = Am$. Thus, the problem is solvable for all $t$ iff $A$ has full rank, or equivalently, $det(A) \neq 0$. Let $d_k$ be the determinant of the $k\times k$ version of the $A$ matrix. From the structure of the tridiagonal matrices by looking at the minors, one can show $d_k = d_{k-1} + d_{k-2}$. Staring from $d_2 = 0, d_3 = 1$ the rest of the sequences goes $1, 0, 1, 1, 0, 1, 1, 0, 1$ etc. This again shows the problem is solvable (for all starting positions) iff $k = 3n$ or $3n+1$.

Further, for $k=3n+2$, while $A_{k \times k}$ does not have full rank, it contains $A_{(k-1)\times (k-1)}$ as a block, and the block has full rank, so $rank(A_{k \times k}) = k-1$. Therefore, the number of solvable starting positions $=|range(A_{k \times k})| = 2^{k-1}$, i.e. exactly half the starting positions are solvable.

BTW here are $A^{-1}$ for $k=12$ and $13$, just for fun. The $j$th column (or row) is how one would solve a single T at $j$. The patterns are quite different for $3n$ and $3n+1$.

0 1 1 0 1 1 0 1 1 0 1 1
1 1 1 0 1 1 0 1 1 0 1 1
1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 1 1 0 1 1
1 1 0 1 1 1 0 1 1 0 1 1
1 1 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 1
1 1 0 1 1 0 1 1 1 0 1 1
1 1 0 1 1 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1
1 1 0 1 1 0 1 1 0 1 1 1
1 1 0 1 1 0 1 1 0 1 1 0

1 0 1 1 0 1 1 0 1 1 0 1 1
0 0 1 1 0 1 1 0 1 1 0 1 1
1 1 0 0 0 0 0 0 0 0 0 0 0
1 1 0 1 0 1 1 0 1 1 0 1 1
0 0 0 0 0 1 1 0 1 1 0 1 1
1 1 0 1 1 0 0 0 0 0 0 0 0
1 1 0 1 1 0 1 0 1 1 0 1 1
0 0 0 0 0 0 0 0 1 1 0 1 1
1 1 0 1 1 0 1 1 0 0 0 0 0
1 1 0 1 1 0 1 1 0 1 0 1 1
0 0 0 0 0 0 0 0 0 0 0 1 1
1 1 0 1 1 0 1 1 0 1 1 0 0
1 1 0 1 1 0 1 1 0 1 1 0 1

Answer 2

Not an answer, but too long for a comment. I wrote this python script

import numpy as np
from scipy.sparse.csgraph import connected_components

for k in range(4,11):
    n=2**k
    masks =  {3}
    j=0
    while 7*2**j < n:
        masks.add(7*2**j)
        j+= 1
    masks.add(n//2+n//4)
    A = np.zeros((n,n), dtype = int)
    for i in range(n):
        for m in masks:
            A[i, i^m] = 1
    supernodes=connected_components(A)
    print(k, supernodes[0])

For $4\le k< 11,$ it computes the adjacency matrix of the graph whose vertices are the $k-$bit binary strings, where two vertices are adjacent if one can be transformed into the other by a single flip (substituting $1$'s and $0'$s for heads and tails, of course.)

Then it computes the connected components of the graph. The problem is possible if and only if the number is one. Here is the output:

4 1
5 2
6 1
7 1
8 2
9 1
10 1

The script is very fast, so it can probably be used to determine what the pattern is. supernodes[1] is a list that encodes the components. For example, when $k=5$ this list is

[0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0]

This means that TTTTT is in component $0$, TTTTH and TTTHT are in component $1,$ and so on. Perhaps one might be able to find a pattern and prove that it is impossible in certain cases, but I'm dubious.

The script bogs down considerably a $k$ increases. I found that $k=11$ is the only other value below $14$ for which it's impossible. I got bored waiting for the $k=14$ case to finish.

EDIT

I've checked that it's impossible for $n=14$ so now I'm willing to guess that it's possible except when $n\equiv2\pmod3$. One thing I have verified which may be useful, is that in the impossible cases, there are exactly two connected components, and that if two strings different only in the last character, (or only in the first character, by symmetry) then it is impossible to transform one into the other.

So for example, when $n=5,$ every $4-$character string occurs as a prefix of one word in each component So far, I haven't figured out how it is decided which components the five-character strings go in. Here is component $0$:

['TTTTT', 'TTTHH', 'TTHTT', 'TTHHH', 'THTTH', 'THTHT', 'THHTH', 'THHHT', 'HTTTH', 'HTTHT', 'HTHTH', 'HTHHT', 'HHTTT', 'HHTHH', 'HHHTT', 'HHHHH']

and here is component $1$:

['TTTTH', 'TTTHT', 'TTHTH', 'TTHHT', 'THTTT', 'THTHH', 'THHTT', 'THHHH', 'HTTTT', 'HTTHH', 'HTHTT', 'HTHHH', 'HHTTH', 'HHTHT', 'HHHTH', 'HHHHT']

Given a five-character string over $\{H,T\}$ how can we decide which component it should go in without searching the components?