Qua locus

Keeping both eyes on the long game.

Red hats, blue hats, dwarves and a goblin – a logic puzzle


This blog has been split in three and all content moved to the new blogs – Qua Locus LifeQua Locus Tech and Qua Locus Puzzle – comments are disabled here.

100 dwarves are captured by an evil goblin milliner who has an over-abundance of red and blue hats and who really does not like dwarves. Being an evil goblin, he has concocted a fiendish, fiendishly complex game by which he hopes to kill as many of them as possible:

“You must all sit in a line, one behind the other, so that none of you can see any dwarves except the dwarves in front of you. I am going to blind fold each of you perfectly, then put a red or blue hat on your head. Then, I will remove the blind folds. In any order you like, each dwarf must say the colour of the hat they are wearing. If they get it wrong I shall eat them, but if they get it right I will be fair and set them free. However, should any dwarf attempt to see their own hat or say anything other than ‘red’ or ‘blue’ I will kill you all! By the simple laws of probability, I expect to feast on 50 delicious dwarves this evening. Ahahaha! Now, I will go and collect my hats, and you may talk amongst yourselves and ponder your fate. Ahahahaha!”

Assume the goblin is a goblin of his word and will set free any dwarf that guesses the colour of his hat correctly. Assume also that the dwarves are smart and have good memories. What strategy should they use so that as many of them survive as possible, and how many will survive?

Advertisements

Written by Christo Fogelberg

April 29, 02013 at 12:00

Posted in Puzzles

Tagged with

12 Responses

Subscribe to comments with RSS.

  1. Are there an equal number of red and blues hats?

    qwandor

    April 29, 02013 at 23:02

    • The distribution of red versus blue is unknown for the dwarves – they have to assume the Goblin milliner has at least 100 of each colour.

      Christo Fogelberg

      April 30, 02013 at 22:22

  2. I can get 1 dead and 99 saved. Could also save them all if they rioted when the goblin is holding 100 blindfolds. But dwarfs don’t have the balls for that.

    Tim wright

    May 1, 02013 at 05:37

  3. From Tim Wright by email:

    The dwarf at the end of the line stands up and calls everyone’s colour hats out in order. By the time the goblin has got to him, he’s finished. He gets eaten because he broke the rules. Everyone else knows their hat colour tho so can get it right. In the unlikely event that the goblin is standing at the end of the line to start with, then the one at the front can stand up and do the same. Sacrifice one to save many.

    However, you can do half an expected dwarf better 🙂

    EDIT: And actually the Goblin would kill all the dwarves for breaking the rules – so you can do a lot more dwarves better. Doh!

    Christo Fogelberg

    May 1, 02013 at 08:16

    • In my brief thinking about the puzzle the best I could do was an expected 75 dwarves saved. However Stephen just told me his solution which saves at least 99, though it does require that the dwarves know who is talking (and their position in the line).

      qwandor

      May 1, 02013 at 10:50

  4. I have 3 more dwarf puzzles which might interest you, perhaps I should post them on my blog.

    qwandor

    May 1, 02013 at 10:54

  5. The solution I came up with is: Each dwarf can see all the other dwarves in front of him. Based on this, the dwarves agree that the first dwarf to call out the colour of his hat will say red if there are an even number of red hats in front of him and blue if there are an odd number of red hats in front of him. Using this information, the next dwarf can see whether there are an even or odd number of red hats in front of him and work out with 100% certainty the colour of his own hat. Since the dwarves can hear what the previous dwarves have called out and know that everyone except the first dwarf is definitely right they can use the same logic to work out the colour of their own hat, and so all dwarves, up to and including the last dwarf to call out the colour of his hat, can work out the colour of their own hat. This means 99 dwarves can definitely survive, and the first dwarf has some probability of getting it right. Because we don’t have any information about the distribution of the hats it’s reasonable to assume a flat prior – ergo exp(99.5) dwarves will survive and there will be one very disappointed Goblin milliner!

    Christo Fogelberg

    May 27, 02013 at 08:20

    • Ooh, nice. The best solution I had (harder in some ways, but interesting as a different approach), based on a solution from Stephen, is this:

      Dwarf 1, at the back of the line, says ‘blue’ if dwarf 2’s hat is red, or ‘red’ if it is blue.
      Dwarf 2 now knows what his hat colour is, and remembers this. If dwarf 3’s hat is the same colour as the last colour which was said, he says his own hat colour (i.e. the opposite of what was said last). Otherwise, he remains silent. Now dwarf 3 knows his hat colour, which must be the opposite of whichever colour was last said (whether by dwarf 1 or 2), and can continue the process of either saying his colour or not. Once the end of the line is reached, all the dwarves (except number 1) know their hat colour, though only some of them have said it. The rest can then go through and say their colours.

      So again we can expect 99.5 dwarves to survive. They do need to agree beforehand on a tempo with which they will go down the line saying or not saying colours. If there are a lot of dwarves in a row with the same hat colour then there will be a long silence, so we must hope that the dwarves have good rhythm.

      qwandor

      May 27, 02013 at 12:53

      • Ahhh, I like this a lot – the idea of broadening the space of possible solutions by introducing time as another dimension like this is very nice.

        Christo Fogelberg

        May 27, 02013 at 14:27

  6. […] number 4 is from Christo’s blog (but do not look their until you have solved it, as there are spoilers): 100 dwarves are in a line, […]

    • Dwarf 1 assigns “Blue” to mean “odd number of blue hats in front of me”, and “Red” to mean “even number of blue hats in front of me”. Every dwarf now knows their hat based on observing the number of blue hats in front of them, whether the total blues are odd/even based on what Dwarf 1 says, and the colors called out by dwarves behind them.

      This extends to N dwarves. N – 1 guaranteed saved.

      Jose

      October 2, 02013 at 02:51


Comments are closed.

%d bloggers like this: