Joe’s Pyramid

January 30, 2011 at 9:16 pm (Monte Carlo)
Tags: , , , ,

Yesterday, while reading the last issue of the NewScientist, I came across the following very cute riddle:

Lazy, I asked myself if it were possible to write {10} lines long Python code to solve this innocent looking enigma. The whole pyramid is entirely determined by the {6} numbers lying at the bottom, and each one of them is an integer between {1} and {99}: these numbers must be different so that there are at most {\binom{99}{6} \approx 1.1 \times 10^9} possibilities to test! Brute force won’t work my friend!

When stupid brute force does not work, one can still try annealing/probabilist methods: this works pretty well for Sudoku (which is NP-hard) as this is brilliantly described here and there. The principle is simple: if one can find a good energy function {E:\{1, \ldots, 99\}^6 \rightarrow \mathbb{R}} such that a solution to the problem corresponds to a low energy configuration, one can do MCMC-simulating annealing-etc on the target distribution

\displaystyle \pi(\text{configuration}) \propto e^{-\beta \cdot E(\text{configuration})}.

The issue is that it might be very difficult to choose a sensible energy function {E(\cdot)}. Foolishly, I first tried the following energy function, and then ran a random walk Metropolis algorithm with {\pi} as target probability:

\displaystyle \pi(\text{configuration}) \propto e^{\beta \cdot {\text{Height}}(\text{configuration})}

where {\text{Height}(\text{configuration})} is the numbers of levels that one can fill, starting from the bottom, without encountering any problem {i.e} no repetition and no number greater than {100}. With different values of {\beta} and letting run the algorithm for a few millions iterations ({5} min on my crappy laptop), one can easily produce configurations that are {5}-levels high: but the algorithm never found any real solution {i.e} a configuration with height equal to {6}.

Now I am curious wether this is possible to produce a non-stupid energy function {E(\cdot)} so that this riddle is solvable in a reasonable amount of time by standard MCMC – annealing methods.

As a conclusion, I should mention that with a pen and a cup of coffee, one can easily find a solution: I will not spoil the fun, but just say that the configuration space is not that big if one think more carefully about it…

1 Comment