Le Monde puzzle [#815]

April 11, 2013
By

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

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.


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

To 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...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.