WW pp.807 & 814 says that n pairs can be done in n moves, and quotes M. Delannoy, La Nature, June 1887, p.10. Curiously, I didn't find it in Singmaster's Sources, but then, as my Mother was wont to point out, I'm not a good looker. R. On Mon, 9 Dec 2002, James Propp wrote:
Tim Chow (tchow@alum.mit.edu) asks the following question, which he has already posted to rec.puzzles and sci.math and has asked me to post here as well (please send replies directly to him as well as to the math-fun list, since he is not a current subscriber):
Subject: Berloquin 5 heads/5 tails puzzle
In one of Pierre Berloquin's books (_100_Perceptual_Puzzles_ I think), he describes the following puzzle. We have ten coins in a row, five heads and five tails, tightly packed with no gaps between adjacent coins.
H H H H H T T T T T
The object is to rearrange the coins into an alternating heads/tails pattern, i.e., one of the following two patterns:
H T H T H T H T H T
T H T H T H T H T H
Again there are no gaps between adjacent coins. The rearrangement must be accomplished in five "moves," where a move consists of taking any two touching coins and moving them into a two-coin gap, if such a gap exists, or to one end of the row, if no such gap exists. For example, initially there is no two-coin gap, so a possible move would be to take the "H T" coins in the center and move them to the right end, yielding
H H H H T T T T H T
Now there is a two-coin gap, so on the next move we would have to take two adjacent coins and move them into the gap, e.g., we could try
H H H H T H T T T T
As these examples illustrate, the coins are not allowed to switch places during the move, i.e., of the two moved coins, the one on the left before the move must remain on the left after the move. Also, moving coins to the end of the row is illegal if there is a two-coin interior gap. The two coins that are moved must be touching; so for example the isolated "T" at the right end in the last picture above cannot be moved on the next move.
Berloquin gives a solution, but I will not spoil your fun by giving it here. I got quite interested in this puzzle many years ago when I first learned it (from a friend actually, not from Berloquin's book), and I believe I managed to show that the obvious generalization to 2n coins can be solved in n moves for all n >= 3. In my solutions I never needed to move a coin that was immediately adjacent to the gap, although I don't think this constraint was imposed by Berloquin. Unfortunately, I did not save my solution. So here are my questions.
1. Is Berloquin the inventor of this puzzle? 2. Has a general solution for n >= 3 been published somewhere? 3. How many solutions are there as a function of n? (Possibly intractable.) 4. Is the puzzle still solvable if we impose some extra "elegance" constraints? For example, we might want to require that the moves alternate "left, right, left, right, ..." (where by a "left" move I mean a move that takes the moved coins to a location that lies to the left of their location before the move, and similarly for "right").
(Jim Propp)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun