Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
3  
Welcome to Puzzling.SE! I've cleaned up the question a bit. Is this what you had in mind? – Deusovi Feb 25 at 5:01
    
Yes, thank you. This sounds much better than before! – Ccyan Feb 25 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 at 5:23
2  
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 at 5:32
3  
Is it OK if at the end the coins alternate but don't all touch? – xnor Feb 25 at 7:30
up vote 11 down vote accepted

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.

share|improve this answer
    
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 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
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.