No Repeats (Posted on 2006-09-13)

	Submitted by Charlie
Rating: 4.5000 (2 votes)
Solution:	(Hide)
Based on Enigma 1404, New Scientist, 12 August 2006. 1. The following table illustrates a winning strategy for the first player. From left to right, it shows the status of the pennies after each move. The columns headed by * show the state after the first player's move. The first two moves (one by each player) are arbitrary but do not lose generality, as any two coins to flip would serve equally as well. * * * * hhh hht htt ttt tht thh tth hth hhh hht htt ttt tht thh hhh hht htt ttt tth hth hhh hht htt ttt There are only two courses shown above for the game to follow. In both, the first player's second move is to turn the last remaining head to tails. At that point the second player will turn one of them back to heads (not the first, as that would result in a repetition), and the first player another. It could play out as in the first row above or the third row. The second and fourth rows merely verify that the final move shown there for the first player is a winning move--not that the game ends there. The above may seem overly complicated, but it introduces the type of table that will be used for part 2, which is: 2. * * * * * * * * hhhh hhht hhtt thtt tttt httt htht ttht thht thhh tthh hthh htth ttth thth hhth hhhh hhht hhtt thtt tttt httt htht ttht thht thhh tthh hthh htth ttth hhhh hhht hhtt thtt tttt httt htht ttht thht thhh tthh hthh ----------------------------- hhhh hhht hhtt thtt tttt httt htht ttht thht thhh thth hhth htth ttth tthh hthh hhhh hhht hhtt thtt tttt httt htht ttht thht thhh thth hhth htth ttth hhhh hhht hhtt thtt tttt httt htht ttht thht thhh thth hhth hhhh hhht hhtt thtt tttt httt htht ttht thht thhh --------------------------------------- hhhh hhht hhtt thtt tttt httt htht ttht tthh hthh htth ttth thth hhth hhhh hhht hhtt thtt tttt httt htht ttht tthh hthh htth ttth hhhh hhht hhtt thtt tttt httt htht ttht tthh hthh hhhh hhht hhtt thtt tttt httt htht ttht ------------------------------------------------- hhhh hhht hhtt thtt tttt httt htth ttth thth hhth --------------------------------------- hhhh hhht hhtt thtt tttt httt htth ttth tthh hthh htht ttht thht thhh thth hhth hhhh hhht hhtt thtt tttt httt htth ttth tthh hthh htht ttht thht thhh hhhh hhht hhtt thtt tttt httt htth ttth tthh hthh htht ttht hhhh hhht hhtt thtt tttt httt htth ttth tthh hthh hhhh hhht hhtt thtt tttt httt htth ttth hhhh hhht hhtt thtt tttt httt ----------------------------------------------------------- hhhh hhht hhtt thtt thht ttht htht httt tttt ttth htth hhth thth thhh tthh hthh hhhh hhht hhtt thtt thht ttht htht httt tttt ttth htth hhth thth thhh hhhh hhht hhtt thtt thht ttht htht httt tttt ttth htth hhth ----------------------------- hhhh hhht hhtt thtt thht ttht htht httt tttt ttth thth hhth htth hthh tthh thhh hhhh hhht hhtt thtt thht ttht htht httt tttt ttth thth hhth htth hthh hhhh hhht hhtt thtt thht ttht htht httt tttt ttth thth hhth ----------------------------- hhhh hhht hhtt thtt thht ttht htht httt tttt ttth tthh hthh htth hhth thth thhh hhhh hhht hhtt thtt thht ttht htht httt tttt ttth tthh hthh htth hhth hhhh hhht hhtt thtt thht ttht htht httt tttt ttth tthh hthh hhhh hhht hhtt thtt thht ttht htht httt tttt ttth --------------------------------------- hhhh hhht hhtt thtt thht ttht htht httt htth hhth thth thhh tthh hthh hhhh hhht hhtt thtt thht ttht htht httt htth hhth thth thhh hhhh hhht hhtt thtt thht ttht htht httt htth hhth hhhh hhht hhtt thtt thht ttht htht httt ------------------------------------------------- hhhh hhht hhtt thtt thht ttht tttt httt htht hthh tthh thhh thth hhth htth ttth hhhh hhht hhtt thtt thht ttht tttt httt htht hthh tthh thhh thth hhth hhhh hhht hhtt thtt thht ttht tttt httt htht hthh tthh thhh ----------------------------- hhhh hhht hhtt thtt thht ttht tttt httt htht hthh htth ttth thth hhth ------------------- hhhh hhht hhtt thtt thht ttht tttt httt htht hthh htth ttth tthh thhh thth hhth hhhh hhht hhtt thtt thht ttht tttt httt htht hthh htth ttth tthh thhh hhhh hhht hhtt thtt thht ttht tttt httt htht hthh htth ttth hhhh hhht hhtt thtt thht ttht tttt httt htht hthh --------------------------------------- hhhh hhht hhtt thtt thht ttht tttt httt htth ttth thth hhth ----------------------------- hhhh hhht hhtt thtt thht ttht tttt httt htth ttth tthh thhh thth hhth hhhh hhht hhtt thtt thht ttht tttt httt htth ttth tthh thhh hhhh hhht hhtt thtt thht ttht tttt httt htth ttth hhhh hhht hhtt thtt thht ttht tttt httt ------------------------------------------------- hhhh hhht hhtt thtt thht ttht tthh hthh htth hhth thth thhh hhhh hhht hhtt thtt thht ttht tthh hthh htth hhth --------------------------------------- hhhh hhht hhtt thtt thht ttht tthh hthh htht httt tttt ttth htth hhth thth thhh hhhh hhht hhtt thtt thht ttht tthh hthh htht httt tttt ttth htth hhth ------------------- hhhh hhht hhtt thtt thht ttht tthh hthh htht httt tttt ttth thth thhh hhhh hhht hhtt thtt thht ttht tthh hthh htht httt tttt ttth ----------------------------- hhhh hhht hhtt thtt thht ttht tthh hthh htht httt htth hhth thth thhh hhhh hhht hhtt thtt thht ttht tthh hthh htht httt htth hhth hhhh hhht hhtt thtt thht ttht tthh hthh htht httt hhhh hhht hhtt thtt thht ttht tthh hthh hhhh hhht hhtt thtt thht ttht ----------------------------------------------------------- hhhh hhht hhtt thtt thth hhth htth ttth tthh hthh htht ttht thht thhh hhhh hhht hhtt thtt thth hhth htth ttth tthh hthh htht ttht tttt httt hhhh hhht hhtt thtt thth hhth htth ttth tthh hthh htht ttht hhhh hhht hhtt thtt thth hhth htth ttth tthh hthh --------------------------------------- hhhh hhht hhtt thtt thth hhth htth ttth tttt httt htht ttht thht thhh tthh hthh hhhh hhht hhtt thtt thth hhth htth ttth tttt httt htht ttht thht thhh ------------------- hhhh hhht hhtt thtt thth hhth htth ttth tttt httt htht ttht tthh hthh hhhh hhht hhtt thtt thth hhth htth ttth tttt httt htht ttht hhhh hhht hhtt thtt thth hhth htth ttth tttt httt hhhh hhht hhtt thtt thth hhth htth ttth hhhh hhht hhtt thtt thth hhth hhhh hhht hhtt thtt Again, rows that match those above them, but then do not continue the way those above continue, merely reiterate that that is a winning move for the first player. Again the first two moves are made arbitrarily with no loss of generality: hhhh hhht hhtt, as some two separate coins must be flipped as the first two moves. 3. Getting away from the above-type tables, let's use a tree: hhh | 1 hht | 2 htt_______________ | \\ 1 ttt hth | \\ | 2 tht tth tth | | \\ | \\ 1 thh hth thh thh ttt | | | | | 2 tth --- tht tht tht | | | | 1 hth --- ttt thh | | | 2 --- --- --- The numbers at the left indicate which player's move resulted in the state shown on the given line for each path. It is player 1 who has the choice between ttt and hth on his second move. If he chooses hth, player 2 will certainly win this misere game, so he'll choose ttt. But then player 2 will choose tht, forcing the leftmost column and a win for her.

	Subject	Author	Date
	Puzzle Thoughts	K Sengupta	2023-06-23 01:54:28
	Does anyone know...	JLo	2006-09-17 16:45:41
	It's obvious	Kit	2006-09-17 12:23:34
	Winning strategy for first part	JLo	2006-09-14 18:05:53
	re: Solution -- not so fast!	Steve Herman	2006-09-14 14:53:29
	A way to solve this	Old Original Oskar!	2006-09-13 13:15:19
	Solution	vswitchs	2006-09-13 13:13:42