## Joe’s Pyramid

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…