Demento-Santa (deluxe edition)

Discrete Mathematics Level 5

Demento-Santa enters the workshop at his evil lair on the South Pole where he is holding a number of elves he has kidnapped from Santa's workshop at the North Pole. He offers them a grand bargain. Although they're starved, tired, and can't even support their own weight, he'll open the bay doors and let the elves make a run for it if some subset of \(2^n -1 \) (for an integer \(n\)) elves can play and survive the following game:

  1. First, Demento-Santa puts the elves into separate the rooms and affixes a 0 or 1 (randomly) to the forehead of each elf. In each room is a set of closed-circuit monitors that allow each elf to see every other elf, but not themselves. In other words, each elf can see the numbers of the other elves but not their own number. On Demento-Santa's command, every elf must either guess the number on his head, or decline to guess. If no elves guess, they all instantly die. If any elf guesses incorrectly, they also all die. If the elves that guess all guess correctly, they survive this stage of the grand bargain.

  2. Demento-Santa has a radioactive element, Mousekingium, in his collection. It is special, just for Demento-Christmas, and has a half-life of exactly 69 seconds. He will put one atom of Mousekingium into a box. If it takes longer to decay (in seconds) than there are elves playing the game, the elves win the second round and the bay doors open.

The question is: how many of the elves should play in the game if the elves want to maximize their chance for survival?

Details and assumptions

  • The elves all guess at the same time and cannot communicate with each other once the game begins.
  • The elves can discuss a strategy before the game begins.
  • Mousekingium decays like any normal radioactive element.
  • The number of elves that play the game must be of the form \( 2^n -1 \).

Problem Loading...

Note Loading...

Set Loading...