Le Monde puzzle [#815]

The last puzzle was as follows:

Take a card stack with 32 cards and divide it into five non-empty piles. A move consists in doubling a pile size by taking card from a single and larger pile. Is it possible to recover the original stack by repeatedly using moves? Same question for 100 cards and five piles.

I first defined a recursive R function to check if this was obvious:

destock=function(stock){ vale=FALSE if (max(stock)==32){ #success         vale=TRUE}else{ #empty piles must remain empty i0=min((1:4)[stock[1:4]>0]) for (i in i0:4){ for (j in (i+1):5){ stuck=stock stuck[i]=2*stock[i] #doubling stuck[j]=stuck[j]-stock[i] #borrowing stuck=sort(stuck) vale=vale||destock(stuck) if (vale) break() } if (vale) break() }} return(vale) }

Then I launched the R code with random starting values:

stack=sample(1:5,27,rep=TRUE)stock=rep(1,5)for (i in 1:5) stock[i]=1+sum(stack==i)stock=sort(stock)

obtaining either a solution or “infinite recursion” warnings. In the first case, getting a sequence like

> destock(stock)[1]  5  5  7  7  8[1]  0  7  7  8 10[1]  0  0  8 10 14[1]  0  0  2 14 16[1]  0  0  4 12 16[1]  0  0  8  8 16[1]  0  0  0 16 16[1]  0  0  0  0 32[1] TRUE

and, in the second, observing an infinite cycle like

> destock(stock)[1]  3  4  7  8 10[1]  1  6  7  8 10[1]  2  5  7  8 10[1]  3  4  7  8 10[1]  1  6  7  8 10[1]  2  5  7  8 10[1]  3  4  7  8 10[1]  1  6  7  8 10Error: evaluation nested too deeply:infinite recursion / options(expressions=)?

The above shows that there exist pile configurations that do not allow for this recursive algorithm to converge. I then thought of introducing randomness in the exploration of the tree as possibly avoiding infinite regress

    for (i in sample(i0:4)){

and, lo and behold!, it worked for every attempt:

> destock(stock)[1]  3  4  7  8 10[1]  3  3  8  8 10[1]  0  6  8  8 10[1]  0  2  8 10 12[1]  0  2  2 12 16[1]  0  2  2  4 24[1]  0  2  2  4 24[1]  0  0  4  4 24[1]  0  0  4  8 20[1]  0  0  4  8 20[1]  0  0  4  8 20[1]  0  0  4  8 20[1]  0  0  4 12 16[1]  0  0  8  8 16[1]  0  0  0 16 16[1]  0  0  0 16 16[1]  0  0  0 16 16[1]  0  0  0 16 16[1]  0  0  0 16 16[1]  0  0  0 16 16[1]  0  0  0  0 32[1] TRUE

It is rather straightforward to prove that the scheme works for a size equal to a power of two like 32 while it cannot work for sizes different from a power of 2. Like 100.