**T**he 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)
}

**T**hen 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=)?

**T**he 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

**I**t 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.

### Like this:

Like Loading...