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 10 Error: 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.
April 12, 2013 at 10:49 am
Excellent like always! But it can actually work with sizes different to a power of 2, e.g. 48 -> 3/3/6/12/24. In fact it works if you can divide the size 3 times per 2… so if 2^3 (8) is a factor of size!
April 12, 2013 at 3:03 pm
Thanks, I had my reasoning wrong (as I should have guessed from the fact the number of bins did not count!)