Enigmatic Code

Programming Enigma Puzzles

Enigma 1363: Hat stand

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

2 responses to “Enigma 1363: Hat stand

  1. Jim Randell 17 December 2013 at 8:23 am

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

    from itertools import permutations, combinations
    from collections import defaultdict
    from enigma import irange, diff, printf
    
    # the queue positions
    positions = (0, 1, 2, 3, 4)
    
    # find possible sequences of hats, such that n of the people can declare
    # ss = sequence of (hats, declared positions)
    def check(ss, n):
      # d maps: position -> sequence in front -> hat colour
      d = defaultdict(lambda: defaultdict(set))
      for (hs, ps) in ss:
        for i in diff(positions, ps):
          d[i][hs[:i]].add(hs[i])
      # now for each sequence find the required number of declarations
      r = []
      for (hs, ps) in ss:
        # positions that can declare
        ds = tuple(i for i in diff(positions, ps) if len(d[i][hs[:i]]) == 1)
        if len(ds) == n:
          r.append((hs, ps + ds))
      return r
    
    # possible arrangements of hats (the 6th entry is the bag = X)
    hats0 = []
    for white in combinations(irange(0, 5), 3):
      h = tuple(('w' if i in white else 'b') for i in irange(0, 5))
      hats0.append((h, ()))
    X = 5
    
    # find sequences where no-one can declare, then 2 people (R, S), then 1 person (Q)
    hats = hats0
    for n in (0, 2, 1):
      hats = check(hats, n)
    
    # consider these sequences (hats, declared)
    for (hs, ds) in hats:
      # assign positions to people for those that have declared
      # the declaration order is R, S, Q or S, R, Q (R and S declare at the same time)
      for (R, S, Q) in (ds, (ds[1], ds[0], ds[2])):
        # so the remaining positions are P and T
        for (P, T) in permutations(diff(positions, ds), 2):
          # P, Q, R, S, T are not in that order
          if (P, Q, R, S, T) == (0, 1, 2, 3, 4): continue
          # P's hat is the same as the one in the bag (X)
          if not(hs[P] == hs[X]): continue
          # and R can see at least one hat of that colour
          if not(any(hs[i] == hs[X] for i in irange(0, R - 1))): continue
          # output the people in queue order and attach the hats
          print(' '.join(q[1] + h for (q, h) in zip(sorted(zip((P, Q, R, S, T, X), 'PQRSTX')), hs)))
    

    Solution: The order of the queue was Paul, Quentin, Steve, Rene, Taina.

    • Jim Randell 17 December 2013 at 8:25 am

      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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: