# Sliding 10 coins to make them alternate

You have 10 coins: five heads, then five tails, all in a row.

HHHHHTTTTT (H is for heads and T is for tails.)

In each move, you can take two adjacent coins and move them somewhere else. You cannot switch the coins as you move them, and you may not move other coins. (This includes spreading them apart to make room!)

If all ten coins are in a row, then you may move a group of two to either end. Otherwise, your next move must fill the gap left by the previous move.

How can you get them to alternate (either HTHTHTHTHT or THTHTHTHTH) in just 5 moves?

Here's an example game that does not succeed:

Start: H H H H H T T T T T
1: H H H H - - T T T T H T
2: H - - H H H T T T T H T
3: H T H H H H T T T - - T
4: H T T H H H T T H T


Any move from the last position would take coins out of the middle, so the last move cannot succeed in putting the coins adjacent to each other.

• Welcome to Puzzling.SE! I've cleaned up the question a bit. Is this what you had in mind? – Deusovi Feb 25 '16 at 5:01
• Yes, thank you. This sounds much better than before! – Ccyan Feb 25 '16 at 5:03
• If you move the two right-most coins to the left; does the next move have to move two coins to the right, or not? (there is no gap in this scenario) – M.M Feb 25 '16 at 5:23
• Do you have to end in the same place you started? Do the coins have to be directly next to each other? If you use the empty space on the right, can you use the empty space on the left later on? – Deusovi Feb 25 '16 at 5:32
• Is it OK if at the end the coins alternate but don't all touch? – xnor Feb 25 '16 at 7:30

0) H H H H H T T T T T - -
1) H - - H H T T T T T H H
2) H T T H H T T - - T H H
3) H T T H - - T H T T H H
4) H T T H T H T H T - - H
5) - - T H T H T H T H T H

The following ideas helped me to find the solution (sorted by obviousness):

1. First, you have to make room to move coins, ie, move two coins to the end. There is no point in closing the row before you are done.

2. As pointed out by Deusovi's partial answer, you really have to place a final pair with every move except the first.

3. By beginning with [2,3], I can create two alternated pairs in the next move.

4. It all hangs on the final move that closes the gap. If I could just get rid of that...

5. I can by taking the coins from the other side.

• I didn't see your answer when I posted mine :( Beat me to it by a few minutes. (I just wrote a computer program) This is btw one of only 2 possible answers, the other being the mirror image of this. – Dennis_E Feb 25 '16 at 10:00

I was able to do it in 6.

1. H H - - H T T T T T H H
2. H H T T H T - - T T H H
3. H - - T H T H T T T H H
4. H T H T H T H T T - - H
5. H T H T H T H - - T T H
6. H T H T H T H T H T


Some of this logic may be wrong. Feel free to point out mistakes.

The first move must be dedicated to taking a pair out of the row. That means we only can shuffle around 8 coins overall.

Assume we will end with HTHTHTHTHT.

Since we only have enough moves to shuffle eight coins, and we need to get four alternating pairs in place, every move but one has to pick up two alternating coins.

Assume the first one will be the move that does not pick up two alternating coins.

Our only options for groups to move on turn 1 are:

2 and 3, 4 and 5, 6 and 7, 8 and 9

If you move either of the two middle groups, then you cannot replace them with an alternating pair on the next turn. WLOG, take group [2,3].

0 HHHHHTTTTT
1 H  HHTTTTTHH


This next move is forced since we must pick up an alternating pair going in the proper order.

2  HTHHHTTTT  H
(HTHTHTHTHT  )


The parentheses are what we need. Observe the differences between what we need and have.

2  HTHHHTTTT  H
(HTHTHTHTHT  )
...!..!.!!.!


We must make at least three moves to switch around four groups, but one of the groups is a single coin completely isolated; it will require at least two moves to fix. Therefore, this is not going to work.

If we end with HTHTHTHTHT, then the first move will pick up alternating coins.

The only alternating coins to pick up are the middle two. Therefore this move is forced:

0 HHHHHTTTTT
1 HHHH  TTTTHT
(HTHTHTHTHT)


There is not a movable alternating pair in the right order.

Therefore we will not end with HTHTHTHTHT.

Therefore we will end with THTHTHTHTH.