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.
We can prove that it is not always possible if n = 5, using a parity argument. Ignoring the center penny, consider the parity to be the number of heads in the other 4 coins. If the other 4 coins have an even number of heads, then the parity is even. If the other 4 coins have an odd number of heads, then the parity is odd. Every move leaves the parity unchanged, so arrangements with an even parity cannot be converted to arrangements with an odd parity.
Specifically, the following arrangements cannot be converted to 5 heads:
HH?HT
HH?TH
HT?HH
TH?HH
HT?TT
TH?TT
TT?HT
TT?TH
This argument also works for 8 pennies and 11 pennies and (3n + 2) pennies. For 8 pennies, ignore the 3rd and 6th coins, which makes the arrangement xx?xx?xx. If you ignore every 3rd penny, then any flip turns exactly two unignored pennies.
And yes, I know that I have not yet proved that it is always possible for 6 pennies.
no for n = 5 (spoiler)
