Ten pennies
- Ten pennies are placed in a circle.
- I am not blind.
- They are all showing Heads.
- I see.
- Can you make them all show Tails?
- No problem! Just turn them over.
- You can only turn three adjacent coins at a time.
- Then I don’t know if it is possible.
- If it is, find the least number of moves needed.
- Can I try to solve the problem with five pennies first?
- I did not know you were cheap, but be my guest.
Problem source: Wisconsin mathematics, engineering and science talent search.
June 19th, 2009 at 2:40 am
One solution is to turn every set of 3 consecutive coins once. This turns every coins thrice, thus changes them from 10 heads to 10 tails, as required.
Suppose the shortest solution had fewer than 10 moves. Then each coin starts heads, but ends up tails, and is thus turned an odd number of times. To turn every coin at least 3 times takes at least 30 coin-turns and thus at least 10 moves, therefore there is at least one coin that is turned only once. The coins can’t all be turned exactly once, because this needs 10 coin-turns, but each move turns 3 coins, so the total number of coin-turns is a multiple of 3. Thus the coins are not all turned by equal numbers of turns. Thus there are consecutive coins A B C D E F where D has been turned more times than C. As each coin is turned an odd number of times, D has been turned at least twice more than C. The only moves that affect either C or D are ABC, BCD, CDE and DEF. The moves BCD and CDE turn both C and D, so these moves cannot account for how D got turned twice more than C. Thus the only way this can happen is that the move DEF was made (at least) twice. But in this case, we could omit 2 occurrences of move DEF and obtain a shorter solution; contradiction.
Thus the shortest solution does not have any two consecutive coins being turned by unequal numbers of times. Thus the shortest solution has all the coins turned the same number of times. Thus the above-mentioned 10-move solution is shortest.
June 19th, 2009 at 9:51 pm
Another way to say the answer is the greatest common multiple of three turns and 10 coins is 30. So you will have to turn 30 coins over, and since 30/(3 at a time) = 10, you will have 10 moves.
That is how I thought of it at least.