Here’s my answer to the elves, cakes and gremlins puzzle. I’m quite sure this is not the only solution, and it may well not be the best solution, but I believe it works.

I think the key to this puzzle is criterion 3: “*Assuming there is at least one locker that remains empty throughout an elf’s attempt to find a free locker, it must find that empty locker in no more than L attempts*“. Effectively this means that each elf has to check each locker for an empty one, and check each locker at most once. However, if each elf checks the lockers in the same order (or a cyclic permutation there of), we are going to get the bunching problem mentioned in the puzzle.

My solution is for each elf to pick a locker at random, check whether it is empty, and if not to pick another locker, proceeding through the lockers in a randomly chosen permutation. However, constructing a truly random permutation from a large set of lockers tends to be memory intensive. We don’t require every permutation to be equally likely; we merely require that there is little chance of collision with the permutations chosen by other elves (either simultaneously or before).

One simple solution to this is as follows. When the elf receives a cake to place, he should first determine a number of steps to advance \(S\) which is a randomly chosen number between \(1\) and \(L-1\) that is coprime with \(L\). The elf should then pick a random locker (assuming the lockers are numbered \(0 .. N-1\)), and if the locker has a cake in, move on by \(S\) steps (using modular arithmetic, i.e. if he reaches the end of the lockers, starting from the beginning) . As \(S\)* *and \(L\) are coprime, this will ensure each locker is visited exactly once.

Why? Because if after \(n\) steps the elf has moved on by \(nS\) lockers. For the elf to check the same locker twice, \(nS\) would have to be divisible by \(L\). But the smallest multiple of \(S\) divisible by \(L\) is \(LS\) as \(L\) and \(S\) are coprime. We can thus deduce that he’ll visit each locker exactly once. Another way to look at this is that the integers from \(0 .. N-1\) are isomorphic to a cyclic abelian group \(\mathbb{Z}/n\mathbb{Z}\).

If

\(C_n = \left \langle {g} \right \rangle\) is the cyclic group of order \(n\) which is generated by \(g\), then:

let

\(a \in C_n: a = g^i\)

and let

\(H = \left \langle {a} \right \rangle\)

i.e \(H\) is a subgroup of \(C_n\) generated by \(g^i\). Then:

\(\left|{H}\right| = \frac n {\gcd \left\{{n, i}\right\}}\) where *gcd* is the greatest common divisor.

Hence where \(n\)* *and \(i\)* *are coprime, the order of the subgroup is equal to the order of the group.

The remaining task is for the elf to find a value of \(S\) which is coprime to \(L\)* *and is between \(1\) and \(L-1\). This can easily be done by picking a random number between \(1\) and \(L-1\), and incrementing by one (modulo \(L-1\)), until the \(\gcd\) of \(S\) and \(L-1\) is \(1\) (i.e. they are coprime). This can easily be calculated using the Euclidean algorithm. With a little bit of handwaving (properly addressed in my next post), we can note that the probability of two numbers being coprime is \(6/\pi^2\), so it will find such a coprime pretty quickly, and there are many such coprimes for a large \(L\), certainly many more than the number of elves if \(L \gg E\).

This gives the algorithm as follows (in pseudo-C), which is pleasingly simple:

int placeCake(int L) { int s; int n; int c; /* First pick a random step between 1 and L-1 (inclusive)*/ s = 1 + rand() % (L-2); /* while loop guaranteed to terminate as gcd(1,L)=1 */ while (gcd(s,L) != 1) { s = 1 + (s % (L-2)); } /* now we know the step is coprime to L */ /* pick a random first locker */ n = rand() % L; /* L iterations covers all lockers as gcd(L,S)=1 */ for (c = 0; c < L; c++) { if (!placeCakeIfEmpty(n)) /* returns 0 on success */ return n; n = (n+S) % L; } return -1; }

I’ve done another post on why finding a coprime step is fast, and why there are lots of them.

Comments (0)Trackbacks (0)