### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,115)
- misc (2)
- project euler (2)
- puzzle (29)
- site news (43)
- tantalizer (29)
- teaser (3)

### Site Stats

- 166,357 hits

Programming Enigma Puzzles

17 December 2013

Posted by on **From New Scientist #2522, 22nd October 2005**

My logical friends Paul, Quentin, Rene, Steve and Taina were standing in a queue, but not in that order. After letting them look around at the queue I told them that they must now only look to the front and not look at anyone behind them.

From a bag containing three white hats and three black hats I placed a hat on each of their heads without anyone seeing the colour of their own hat (although everyone could see the hats ahead of them in the queue).

This left one hat in the bag. I explained all of this to them and asked them to say their name when they knew the colour of their own hat.

After a pause we heard the declarations “Rene” and “Steve” simultaneously and that led to a further declaration “Quentin”. No one else could work out the colour of their own hat.

In fact Paul’s hat was the same colour as the one in the bag, and Rene could see at least one hat of that colour.

What, from front to back, was their order in the queue?

[enigma1363]

Advertisements

%d bloggers like this:

I think this one is easier to solve analytically than programatically, but here’s a Python program that solves it in 35ms.

Solution:The order of the queue was Paul, Quentin, Steve, Rene, Taina.Here’s an analytical solution:

Suppose the queue is A, B, C, D, E.

If either D or E could see three hats of the same colour, then they would know their hat must be of the opposite colour. Initially there is a pause, so this doesn’t happen. So the first four hats must be 2 of each colour.

D knows E did not declare immediately, so E can see 2 hats of each colour. D can see two hats of one colour (let’s say white) and only one hat of the other colour (black), so D’s hat must black too, and so they can declare.

At the same time C would also be aware that D and E did not declare immediately, and so the first four hats are two of the same colour. If C can see two hats of the same colour (white hats on A and B) then they would know that the two hats of the other colour (black) must be on C and D, and so they can also declare.

So, C and D are Rene and Steve (in black hats), but we don’t know which is which.

On hearing the two declarations B would be able to work all this out, and so would know that their hat was the same colour as A’s, so they could declare.

Hence B is Quentin (in a white hat).

We are told that Paul’s hat is the same colour as the one in the bag. But we know the first four hats are (white, white, black, black), so there is one hat of each colour to assign to E and the bag. If Paul was E the two remaining hats would need to be of the same colour, so Paul must be A and is wearing a white hat, so the hat in the bag is also white. So Taina is in position E and is wearing a black hat.

So the order of the people is P, Q, R/S, T (and the order of the hats is w, w, b, b, b + w in the bag). Whatever position Rene is in she can see at least one hat that’s the same colour as the hat in the bag (as she can can see both of P and Q’s hats, which are the same colour as the hat in the bag).

But we are told right at the beginning of the puzzle that order of the queue is not P, Q, R, S, T hence it must be P, Q, S, R, T.