Archive for recursive function

Le Monde puzzle [#950]

Posted in Books, Kids, pictures, Statistics, Travel, University life with tags , , , , on March 10, 2016 by xi'an

A Le Monde mathematical puzzle with Alice and Bob:

Alice and Bob play a game with 100 tokens set in ten piles of 1, 9 piles of 2, 8 piles of 3, 7 piles of 4, and 4 piles of 5. They each take a token in turn, either to remove it from the game, or to create a new pile of one, provided this token is taken from a pile with at least two remaining tokens. The winner is the one left with the last token. If Alice starts, who is the winner?

I just wrote a most rudimentary recursive R function

 if (max(tokens)>0){
 #takes one token off
 for (i in (1:5)[tokens>0]){
 if (gain==1) break()}
 #create another singleton
 if (max(tokens[-1])>1){
 for (i in (2:5)[tokens[-1]>1]){
 if (gain==1) break()}}}

where token represents the number of remaining sets with 1, 2, 3, 4, and 5 tolkiens. With the suggested values, (10,18,24,28,20), the R code takes too long on my machine! Or even overnight on our server. So as usual I thought a bit more about it and started cutting at unnecessary bits, reaching the faster recursive function

  #clean up piles with single token
  if (max(tokens[-1])==0){
    #end: no choice left
    #all piles have to disappear, order should not matter
    #set one token appart
    #create another singleton

as all sets have to vanish at one point or another so order should not matter. However, with the starting values provided in the puzzle, two weeks of computation on our local cluster did produce nothing, as there are too many cases to examine! (The exact solution is that Alice cannot win the game if Bob plays in an optimal manner.)

Le Monde puzzle [#930]

Posted in Books, Kids, Statistics, University life with tags , , , on October 9, 2015 by xi'an

A game Le Monde mathematical puzzle:

On a linear board of length 17, Alice and Bob set alternatively red and blue tokens. Two tokens of the same colour cannot sit next to one another. Devise a winning strategy for the first player.

In the ‘Og tradition, this calls for a recurrent R code:

   # stopping rule
   if (sum(tak==col)==0){
     for (i in (1:n)[tak!=-col])
   # left positions
   if (sum(frei)>0){
     for (i in (1:n)[frei==1]){
   # outcome of best choice

While I did not run the rudimentary recursive function for n=17, I got a zero return from n=2 till n=12, meaning that the starting player is always going to lose if the other player plays optimally.

Le Monde puzzle [#910]

Posted in Books, Kids, Statistics, University life with tags , , on May 8, 2015 by xi'an

An game-theoretic Le Monde mathematical puzzle:

A two-person game consists in choosing an integer N and for each player to successively pick a number in {1,…,N} under the constraint that a player cannot pick a number next to a number this player has already picked. Is there a winning strategy for either player and for all values of N?

for which I simply coded a recursive optimal strategy function:

  if (length(mine)>0)
  if (length(fine)>0){
   for (i in 1:length(fine)) 

which returned a zero gain, hence no winning strategy for all values of N except 1.

> gain(NULL,NULL,1)
[1] 1
> gain(NULL,NULL,1:2)
[1] 0
> gain(NULL,NULL,1:3)
[1] 0
> gain(NULL,NULL,1:4)
[1] 0

Meaning that the starting player is always the loser!

Le Monde puzzle [#905]

Posted in Books, Kids, R, Statistics, University life with tags , , , on April 1, 2015 by xi'an

A recursive programming  Le Monde mathematical puzzle:

Given n tokens with 10≤n≤25, Alice and Bob play the following game: the first player draws an integer1≤m≤6 at random. This player can then take 1≤r≤min(2m,n) tokens. The next player is then free to take 1≤s≤min(2r,n-r) tokens. The player taking the last tokens is the winner. There is a winning strategy for Alice if she starts with m=3 and if Bob starts with m=2. Deduce the value of n.

Although I first wrote a brute force version of the following code, a moderate amount of thinking leads to conclude that the person given n remaining token and an adversary choice of m tokens such that 2m≥n always win by taking the n remaining tokens:


 if (n>2*m){
   for (i in 1:(2*m))

eliminating solutions which dividers are not solutions themselves:

for (i in 3:6){

which leads to the output

> subs=rep(0,16)
> for (n in 10:25) subs[n-9]=optim(n,3)
> for (n in 10:25) if (subs[n-9]==1) subs[n-9]=1-optim(n,2)
> subs
 [1] 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
> (10:25)[subs==1]
[1] 18

Ergo, the number of tokens is 18!

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.

# return 1 if current player can win, 0 otherwise

  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){

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

(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.)