Archive for recursive function

Le Monde puzzle [#860]

Posted in Books, Kids, R with tags , , , , on April 4, 2014 by xi'an

A Le Monde mathematical puzzle that connects to my awalé post of last year:

For N≤18, N balls are placed in N consecutive holes. Two players, Alice and Bob, consecutively take two balls at a time provided those balls are in contiguous holes. The loser is left with orphaned balls. What is the values of N such that Bob can win, no matter what is Alice’s strategy?

I solved this puzzle by the following R code that works recursively on N by eliminating all possible adjacent pairs of balls and checking whether or not there is a winning strategy for the other player.

topA=function(awale){
# return 1 if current player can win, 0 otherwise

  best=0
  if (max(awale[-1]*awale[-N])==1){
  #there are adjacent balls remaining

   for (i in (1:(N-1))[awale[1:(N-1)]==1]){

    if (awale[i+1]==1){
      bwale=awale
      bwale[c(i,i+1)]=0
      best=max(best,1-topA(bwale))
      }
  }}
  return(best)
 }

for (N in 2:18) print(topA(rep(1,N)))

which returns the solution

[1] 1
[1] 1
[1] 1
[1] 0
[1] 1
[1] 1
[1] 1
[1] 0
[1] 1
[1] 1
[1] 1
[1] 1
[1] 1
[1] 0
[1] 1
[1] 1
[1] 1
<pre>

(brute-force) answering the question that N=5,9,15 are the values where Alice has no winning strategy if Bob plays in an optimal manner. (The case N=5 is obvious as there always remains two adjacent 1′s once Alice removed any adjacent pair. The case N=9 can also be shown to be a lost cause by enumeration of Alice’s options.)

Le Monde puzzle [#815]

Posted in Books, Kids, R with tags , , , , on April 12, 2013 by xi'an

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.

the little half (another Le Monde puzzle)

Posted in Kids, R with tags , , , , on October 28, 2012 by xi'an

I found this Le Monde puzzle of June 16 I had stored and then somehow forgotten with my trips to Japan and Australia: There are n beans in a box, with 98≤n≤102). Two players take at each round either one bean from the box or “the little half” (i.e. the integral part of the half) of the remaining beans. The player remaining with a single bean to pick has lost. What is the value of n for which there exists no winning strategy for the second player? Now the R resolution is rather easy: Player 1 wins with n beans whatever his strategy if Player 2 loses with either (n-1) or [n/2] beans. This leads to a straightforward recursive function

solve=function(n){
if (n<4){
solve=(n>1)}else{
solve=(!(solve(n-1)))&&(!solve(trunc(n/2)))}
   solve}

as it is possible to win with 2 or 3 beans, providing the answer to the puzzle:

> solve(98)
[1] TRUE
> solve(99)
[1] FALSE
> solve(100)
[1] FALSE
> solve(101)
[1] FALSE
> solve(102)
[1] TRUE

if not an explanation!

Update (5:40, Central Time Zone): Robin’s question made me realise I had changed the wording of the problem when trying to solve it, moving from the little half to the large half in the above code! This means I should have used ceiling instead of trunc. The corrected R code stands as follows:

solve=function(n){
if (n<3){
solve=(n==2)}else{
solve=(!(solve(n-1)))&&(!solve(ceiling(n/2)))}
   solve}

and leads to the answer

> solve(98)
[1] FALSE
> solve(99)
[1] TRUE
> solve(100)
[1] FALSE
> solve(101)
[1] FALSE
> solve(102)
[1] FALSE
Follow

Get every new post delivered to your Inbox.

Join 557 other followers