Sliding 10 coins to make them alternate

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

PARTIAL ANSWER

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.