Le Monde puzzle [#815]
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
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
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.