Author: Filip Blašković (ZIB)
On a snowy winter day, a group of busy elves traveled through the enchanted forest, their sleighs packed with sweet presents from the famous North Pole bakery. These were not just any presents — the elves had carefully prepared five delicious types of cookies: ginger, honey, cinnamon, cardamom, and nutmeg. Thousands of boxes, carefully labeled and stacked on the sleighs, were destined for Santa Claus, who needed to distribute them to children worldwide. The elves were hurrying to reach Santa’s home in the valley before it was too late to begin his Christmas journey.
Just as they were about to leave the forest and enter the valley, something unexpected happened. A giant, cinnamon-colored Christmas monster named Lebkuchenschlucker leaped out from behind a bush, landing right in front of the elves’ sleighs! With a mischievous grin, the greedy monster grabbed all the cookie boxes in one swoop. He was just about to vanish back into the depths of the forest when the elves, thinking quickly, pleaded with him.
“Please!” they cried. “Santa Claus is waiting for these gifts; he must leave soon to deliver them to all the children. Could we at least have some of the boxes back?”
Lebkuchenschlucker paused, scratching his chin. After a moment, he smiled slyly and said:
“Very well, I will give you a chance. But only if you are willing to play a game.”
The elves exchanged nervous glances but knew they had no choice. They nodded in agreement.
The monster laid out the rules:
“Here is how it will work,” he said. “Each of you will receive a box of cookies, but the label on your box will be hidden. You will be able to see the labels on the other elves’ boxes but not your own.”
- First, decide on a strategy.
- Next, you will receive your presents.
- Finally, I will call on you one by one, in an order of my choosing, and when I call on one of you, they have to guess the flavor of cookies in your box aloud, so everyone can hear it. You will all of course know which elf I have called out.
“When the game starts, you are only allowed to talk if I ask you to, and even then you’re only allowed to guess your cookie taste.
At the end of the game, those who guess correctly will be allowed to keep their box and deliver it to Santa. Those who guess incorrectly must return to the bakery to get a new one.”
The monster then added:
“Oh, and don’t think you can rely on counting the flavors — I have far more cookie boxes hidden away than there are of you! You have to rely on hearing and your memory.”
The elves huddled together, deep in thought. How should they play the game to ensure they keep as many boxes as possible?
Here are the questions:
- If there are 100 elves, what is the maximum number of cookie boxes they are guaranteed to win back using the optimal strategy?
- What is the answer to the same question if the 100 elves play the same game, but this time they are divided into five friends cliques of 20 elves each before they get the chance to agree on a strategy? In this version, no elf within a friends clique can see the labels on the boxes of their friends during the game, but they can see the labels of all the elves in all other groups. However, all 100 of them can strategize together after finding out their friends cliques, but before actually getting the cookie boxes. Does this change the outcome, and how?
Possible Answers
- 50 and 20
- 50 and 40
- 95 and 90
- 97 and 80
- 96 and 80
- 96 and 96
- 99 and 0
- 99 and 80
- 99 and 95
- 100 and 100