Demento-Santa (deluxe edition)

The skills required for this deluxe challenge branch the realms of physics, combinatorics, and algebraic coding, and requires the confidence to believe in your answer for two separate substantial problems in order to arrive safely at the end of this glorious road. Normally this would be separated into two, and it would probably be best to have more than 3 attempts allowed, but I figured many people will have extra time around the holidays. With that, let us look at the elve's first challenge.

First challenge

At first glance, it appears that the elves can learn absolutely nothing by looking at the numbers of the other elves. Let's look at the possibile outcomes:

    Elf1     Elf2    Elf3
       1        1       1
       1        1       0
       1        0       1
       0        1       1
       1        0       0
       0        1       0
       0        0       1
       0        0       0

Consider this table from the perspective of a single elf. If Elf1 looks around and sees distinct numbers on the heads of the other elves, there is a 50% chance that he has a 0 or a 1. Similarly, if he sees the same number on the heads of the two other elves, he has a 50% chance of being a 0 or a 1.

Now, consider the middle six cases from the perspective of the group:

    Elf1     Elf2    Elf3
       1        1       0
       1        0       1
       0        1       1
       1        0       0
       0        1       0
       0        0       1

in these six cases, the elves can always win if they use the following strategy:

1. If an elf looks at the other two and sees different numbers, they refuse to guess.
2. If an elf looks at the other two and sees the same number, they guess the opposite number.

In these six cases, only one elf will guess in any given round and they'll always guess correctly.

In the remaining cases:

    Elf1     Elf2    Elf3
       1        1       1
       0        0       0

every elf will guess and they will all guess incorrectly. Across all assignments, this strategy yields an expected survival rate of 3/4.

This may appear as though information has appeared magically from nowhere. This (magic) would be the case if the individual elves were able to increase their ability to guess the number on their head.

In fact, it must be the case that, in the aggregate, each elf has still just a 50% chance of success at guessing his number. The strategy does not give them any new information.

Looking at any given elf, we see that each one makes two successful guesses and two incorrect guesses using the strategy so described. Therefore, each elf has a 50% success rate, as expected. What increases the population survival rate is the concentration of the wrong guesses. I.e. the elves are able to pack all of their wrong guesses into just two of the eight assignment cases.

Putting aside the task of identifying the actual guessing rules, we can generalize the above logic to find the maximum possible survival rate for a given number of elves.

Let's see if we can improve our chances with 4 elves. Again, each elf has a 50% success rate in their individual guesswork.

Overall, there must be $2S$ guesses made, where $S$ is the total number of successful guesses. If we try to match the success rate from the three elf cases, we'd need $\displaystyle\frac34\times 16 = 12$ successful guesses, and $12$ unsuccessful guesses. This is feasible because we can spread 12 successful guesses across 12 cases, leaving four cases (with room for 16 guesses) into which we must fit just 12 unsuccessful guesses. Let's call the fully packed unsuccessful guess cases "death strings".

Let's try for 13 successful guesses, making a survival rate of $\displaystyle\frac{13}{16} = 81.25\%$ . This would require us to fit 13 successful guesses into twelve rounds and 13 unsuccessful guesses into three death strings. But three death strings only have a capacity for 12 ( $3N$ ) guesses. Clearly this is not possible. The best strategy for 4 elves is then to match the strategy of 3 elves which can be achieved with either a more complicated guessing rule or simply by having one of the elves sit out from the game entirely (always refuse to guess).

In the 3 elf case we are able to make full use of the guess space to pack incorrect guesses into a small subspace of the guess space. In the 4 elf case we are unable to leverage the extra volume we're afforded. Generalizing a bit, we can see what condition must be met for us to maximally leverage the volume of the space and increase our chances from $\frac34$ .

In a space of $N$ elves, to have $S$ isolated successful guesses maximally pack a space, we must have $S$ unsuccessful guesses that we will pack into death strings of length $N$ , yielding $S/N$ death strings. We then have $2^N - S/N$ strings available to spread the correct guesses. This gives us a self-consistent equation for $S = U$ :

$2^N-\frac{U}{N} = U$

which implies $S = \frac{2^N}{1+1/N}$ or $S = \frac{N}{1+N}2^N$ . The success rate of the maximal packing strategy is the number of successful guess strings relative to the total number of guess strings:

$S/2^N = \displaystyle\frac{N}{1+N}$

Now, the maximal packings will occur whenever the expression for the number of successful guess strings is an integer, i.e. when $N+1$ divides $2^N$ . This is true whenever $N+1 = 2^k$ for some integer $k$ . Therefore, $N$ elves can maximally pack their incorrect guesses into death strings whenever $N = 2^k-1$ .

When this is true, they'll have a survival rate of

$\frac{S}{2^N} = \frac{2^N - \frac{2^N}{1+N}}{2^N} = \frac{N}{1+N}$

The maximal survival rate jumps whenever the number of elves playing the game, $N$ , is equal to $2^k-1$ $\forall k \in \mathbb{N}$ .

We can reflect these jumps by writing the survival rate in terms of $N$ as the floor of the $\log$ of $N$ . The survival rate as a function of $N$ is

$\frac{\displaystyle 2^{\left\lfloor \log_2 (N+1)\right\rfloor }-1}{\displaystyle 2^{\left\lfloor \log_2 (N+1)\right\rfloor }}$

img

This leaves the task of identifying the death strings, which we'll describe in a Python program at the end.

Second challenge

The second part of the challenge requires the elves to calculate the distribution of first passage times for radioactive decay, i.e., the probability that the atom's decay event doesn't happen until $t$ seconds have passed.

First, let's consider the role of the half-life. If a group of radioactive atoms decay with the rate $k$ , then we expect the number of undecayed atoms to change as $\dot{N}(t) = -kN(t)$ . The solution is given by $N/N_0 = \exp -kt$ . We can find the half life of the atoms by solving for $t$ in $\frac12 = \exp -kt$ , yielding $\displaystyle t_{1/2} = \frac{\ln 2}{k}$ , or equivalently, $k = \frac{\ln 2}{t_{1/2}}$ .

Therefore, Mousekingium atoms, which have a half-life of $69\mbox{ s}$ , have a decay rate of $k_{69} = \frac{\ln 2}{69} \displaystyle \mbox{ s}$ .

Now, let's suppose there are a large number of identical Mousekingium atoms at time $t = 0$ and let $P_0(t)$ be the probability that a given atom of Mousekingium has not decayed by time $t$ . This probability decays as

$\dot{P_0}(t) = -k_{69}P_0(t)$

(because systems with undecayed atoms decay at the rate $k$ ) which yields $P_0(t) = \exp{-k_{69}t}$ . Therefore, the probability that the atom of Mousekingium lasts until $t$ seconds or later is given by $\exp -k_{69}t$ .

For our elves, who pick $n$ elves to play the game, the chance that the atom won't decay until $N$ seconds is $\exp-k_{69}N$ .

Putting it all together

From the first part, we have the chance for survival as a function of the number of players: $P_1 = \displaystyle 1- 2^{-\left\lfloor \log_2 (N+1)\right\rfloor }$ . The chance for the atom of Mousekingium to last longer in seconds than the number of players is given by $P_2 = \exp-k_{69}n$ . Since this function monotonically decays with the number of players, we only have to consider the jump points of the first game in determining the optimal number of players to choose, i.e. where $N = 2^k-1$ : 3,7,15,31, et cetera.

The probability of the elves surviving the first game is given by $P_1$ and is independent of the chance for them to survive the second game $P_2$ . The chances for them to survive both games is then $P_1 \times P_2 = \displaystyle 1- 2^{-\left\lfloor \log_2 (N+1)\right\rfloor } \exp-k_{69}N$ .

We can finish the problem off by plotting this quantity over the series: 3, 7, 15, 31, ... :

img

Numerically:

 N  P1*P2
 1  0.495
 3  0.728
 7  0.816*
15  0.806
31  0.710
63  0.523

we see that 7 is the optimal number of elves to play in order to maximize the chance for survival, assuming the elves can divine the death string maximal packing strategy and remember how to calculate first passage times.

Appendix

We gave a proof that the maximum survival rate for $N$ elves in the first game is given by $\displaystyle 1- 2^{-\left\lfloor \log_2 (N+1)\right\rfloor }$ but we didn't identify the death strings in that space. Here we display the death strings for the case of 7 elves.

According to the calculation, for 7 elves we have $2^N\frac{N}{1+N} = 112$ successful guess strings and $128-112 = 16$ death strings. Now, considering the death strings with a metric of the Hamming distance, defined as the number of bit flips required to move between two strings:

$\mbox{Hamming}(111,101) = 1$ $\mbox{Hamming}(111,010) = 2$ $\mbox{Hamming}(001,001) = 0$

et cetera.

Each guess string in the space will have 7 nearest neighbors (flipping an entry at each position in the string).

It wouldn't make any sense for any of the nearest neighbors of a death string to also be death strings. If it were, we could have, for instance, both $1111000$ and $1111010$ as death strings.

In either case, Elf6's information is the same, therefore, Elf6 would be make the same guess in both cases. This is a contradiction however as both are supposed to be death strings. He can't make an incorrect guess both times by guessing the same thing both times if his number is different in both cases.

Therefore, the death strings have a Hamming distance of at least 2 from one another.

If each set of nearest neighbors to death strings is unique, they would account for all $16\times 7 = 112$ safe strings. If we go to next nearest neighbors, each death string would have 42 possibilities, which means that there is crossover between the next nearest neighbors of any pair of death strings.

This implies that each death string has a unique set of nearest neighbors, which touch a neutral network of shared next nearest neighbors which in turn are one step from another death string (after passing through another unique set of nearest neighbors), giving each death string a distance of at least $1 + 1 + 1 = 3$ from any other death string.

This reduces the problem of finding the death strings to finding a set of 16 strings that are all 3 or more away from one another. We can assign the remaining 112 cases to successful guess strings.

The following Python program builds up the library of 128 strings in the 7 elf guess space and then filters them until all remaining strings have a Hamming distance of at least 3 to one another:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

    def hamming(s1, s2):
        return sum(d1 != d2 for d1, d2 in zip(s1,s2))

    def check(a):
        return [hamming(item1,item2) for item1 in a 
        for item2 in a[a.index(item1):len(a)] if item1 != item2]

    initialset = ['1', '0']

    for i in range(6):
        tempset = []
        for item in initialset:
            tempset.append(str(item + '1')) 
            tempset.append(str(item + '0'))
        initialset = tempset

    a = initialset[:1]
    for item in initialset[1:]:
        temp = a + [item]   
        if min(check(temp)) == 3:
            a.append(item)

    for item in a:
        print item

This returns the following set of death strings:

1111111
1111000
1100110
1100001
1010101
1010010
1001100
1001011
0110100
0110011
0101101
0101010
0011110
0011001
0000111
0000000

At that, we conclude the deluxe challenge.