Consider n pennies arranged in a straight line.
A move consists of taking a penny and turning it over (from head to tail or visa versa) and of doing the same to each of its neighbors.
If the penny happens to be at the end of the line, then it will have only one neighbor. For example, if the sequence is HHTH and you choose the 3rd penny, then your move would result in HTHT.
The question is, given any sequence of n pennies, is it possible to find a sequence of moves to bring it to all Heads? Show that the answer is no for n=5 but yes for n=6.
Starting with the second penny choose to perform or not perform the move in order to make the penny to the left Heads. Continue down the line all the way through the last penny.
If all the pennies are heads then the goal is met. If not then perform the move at all places that are not multiples of three. If the number of coins is not 2 mod 3 then all the pennies will be heads.
For example, starting with THHTTHT
Perform the move for the second yields HTTTTHT
Then the third to yield HHHHTHT
Do not perform the move for the fourth or fifth.
Then the sixth to yield HHHHHTH.
Finally the seventh (last) to yield HHHHHHT.
The goal is not met, so perform the move for the first, second, fourth, fifth, and seventh:
The first: TTHHHHHT.
Then second: HHTHHHT
Then fourth: HHHTTHT
Then fifth: HHHHHTT
Finally seventh: HHHHHHH
An algorithm
