Weihnachtsmann rot

Challenge from 20. December

Another Tricky Hat Challenge

Authors: Aart Blokhuis, Gerhard Woeginger

Project: 4TU.AMI

Challenge:

Santa Claus addresses the seventeen super-smart elves Alba, Bilbo, Carla, Dondo, Edda, Frodo, Greta, Harpo, Izzy, Jacco, Kira, Loco, Mila, Nemmo, Olga, Puzzo, and Quibo: “My dear super-smart elves! Once again, we want to have a tricky puzzle with coloured hats in the Mathematical Advent Calendar. For this reason, I will invite you over to my place for coffee and cake tomorrow afternoon.”
“Great, we are happy to accept your invitation!”, the seventeen elves shout in chorus.

Santa Claus continues: “Tonight I am going to prepare 16 red and 16 blue hats. Tomorrow's game will then consist of two phases. During the first phase, Quibo has to wait outside alone. The other sixteen elves come to my vestibule, where the 32 hats are lying on top of the dresser. I will randomly point at one of the elves. Then, this elf has to choose a red or a blue hat to put on the head. Afterwards, I point at a second elf, who also has to choose a hat. Then I point at a third, fourth, fifth elf, and so on, until the fifteenth elf has chosen a hat and put it on the head. At the end, I myself will choose a hat for the remaining sixteenth elf. Since the sixteenth elf does play a special role in the game, this elf will be called Elf X. Are there any questions about this first phase of the game?”

Alba wants to know: “In which order are you going to point at the elves?”
“The order is arbitrary, just as it comes to my head,” answers Santa Claus.

Then, Bilbo asks: “Does the second elf know the hat colour of the first elf, at the moment when he or she has to pick the own hat colour?”
“Yes!” answers Santa Claus. “Everything in this game is transparent. With the sole exception of Quibo waiting outside, every elf is able to see all the hats on all the heads of all the other elves at any time.”

Finally, Carla wants to know: “Which colour are you going to pick for Elf X?”
“I am going to pick the colour that I find appropriate,” says Santa Claus.

Santa Claus continues: “In the game's second phase, Quibo is finally allowed into the vestibule. Quibo's task is to arrange the sixteen other elves into a long row from left to right. Every elf ending up to the left of Elf X must leave and stay hungry. However, every elf standing to the right of Elf X receives a piece of apple pie and a cup of coffee. Also Elf X and Quibo receive pie and coffee. Are there any questions about this second phase?”

Dondo asks: “Are we allowed to help and advise Quibo in arranging the row of sixteen elves?”
“No!”, answers Santa Claus. “You are not allowed to communicate any information to Quibo. And you are also not allowed to cheat! But of course you already know all that from hat puzzles in the preceding editions of the Mathematical Advent Calendar.”

The seventeen elves start to ponder. They discuss and they think. They think and they discuss. Then, they discuss some more, and then they think some more. Eventually they manage to develop an amazing strategy that maximizes the number M of elves who receive pie and coffee—independently of the decisions and actions of Santa Claus in the first phase of the game.

Which of the following statements is true for this number M?

Artwork: Friederike Hofmann

PDF download

Possible answers:

  1. M ≤ 5.

  2. M = 6.

  3. M = 7.

  4. M = 8.

  5. M = 9.

  6. M = 10.

  7. M = 11.

  8. M = 12.

  9. M = 13.

  10. M ≥ 14.

You have to log in to be able to submit your answer.