**Xi'an's Og » R**, and kindly contributed to R-bloggers)

**T**he last puzzle was as follows:

Take a card stack with 32 cards and divide it into five non-empty piles. Amoveconsists indoublinga 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.

Filed under: Books, Kids, R Tagged: infinite recursion, Le Monde, mathematical puzzle, R, recursive function

**leave a comment**for the author, please follow the link and comment on his blog:

**Xi'an's Og » R**.

R-bloggers.com offers

**daily e-mail updates**about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...