Archive for recursive function

another riddle

Posted in Books, Kids, R with tags , , , , , , on March 29, 2016 by xi'an

A very nice puzzle on The Riddler last week that kept me busy on train and plane rides, runs and even in between over the weekend. The core of the puzzle is about finding the optimal procedure to select k guesses about the value of a uniformly random integer x in {a,a+1,…,b}, given that each guess y produces the position of x respective to y (less, equal, or more). If y=x at one stage, the player wins x. Optimal being defined as maximising the expected gain. After some (and more) experimentation, I found that, when b-a is large enough [depending on k], the optimal guess at stage i is b-f(i) with f(k)=0 and f(i-1)=2f(i)+1. For the values given on The Riddler, a=1,b=1000,k=9, my solution is to first guess at y=1000-f(9)=255 and this produces a gain of 380.31 with a probability of winning of 0.510, which seems amazingly large, but not so much when considering that 2⁹ is close to 500. Continue reading

Le Monde puzzle [#954]

Posted in Kids, R with tags , , , , , , on March 25, 2016 by xi'an

A square Le Monde mathematical puzzle:

Given a triplet (a,b,c) of integers, with a<b<c, it satisfies the S property when a+b, a+c, b+c, a+b+c are perfect squares such that a+c, b+c, and a+b+c are consecutive squares. For a given a, is it always possible to find a pair (b,c) such (a,b,c) satisfies S? Can you find the triplet (a,b,c) that produces the sum a+b+c closest to 1000?

This is a rather interesting challenge and a brute force resolution does not produce interesting results. For instance, using the function is.whole from the package Rmpfr, the R functions

ess <- function(a,b,k){
#assumes a<b<k
 ess=is.whole(sqrt(a+b))&
 is.whole(sqrt(b+k))&
 is.whole(sqrt(a+k))&
 is.whole(sqrt(a+b+k))
 mezo=is.whole(sqrt(c((a+k+1):(b+k-1),(b+k+1):(a+b+k-1))))
 return(ess&(sum(mezo==0)))
 }

and

quest1<-function(a){
 b=a+1
 while (b<1000*a){
  if (is.whole(sqrt(a+b))){
   k=b+1
   while (k<100*b){
    if (is.whole(sqrt(a+k))&is.whole(b+k))
     if (ess(a,b,k)) break()
    k=k+1}}
   b=b+1}
 return(c(a,b,k))
 }

do not return any solution when a=1,2,3,4,5

Looking at the property that a+b,a+c,b+c, and a+b+c are perfect squares α²,β²,γ², and δ². This implies that

a=(δ+γ)(δ-γ), b=(δ+β)(δ-β), and c=(δ+α)(δ-α)

with 1<α<β<γ<δ. If we assume β²,γ², and δ² consecutive squares, this means β=γ-1 and δ=γ+1, hence

a=2γ+1, b=4γ, and c=(γ+1+α)(γ+1-α)

which leads to only two terms to examine. Hence writing another R function

abc=function(al,ga){
 a=2*ga+1
 b=4*ga
 k=(ga+al+1)*(ga-al+1)
 return(c(a,b,k))}

and running a check for the smallest values of α and γ leads to the few solutions available:

> for (ga in 3:1e4)
for(al in 1:(ga-2))
if (ess(abc(al,ga))) print(abc(al,ga))
[1] 41 80 41 320
[1] 57 112 672
[1] 97 192 2112
[1] 121 240 3360
[1] 177 352 7392
[1] 209 416 10400
[1] 281 560 19040
[1] 321 640 24960
[1] 409 816 40800
[1] 457 912 51072

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

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

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

reward=function(tokens){
  #clean up piles with single token
  tokens[1]=tokens[1]+sum((tokens[-1]==1))
  tokens[-1][tokens[-1]==1]=0
  if (max(tokens[-1])==0){
    #end: no choice left
    gain=1*(tokens[1]%%2==1)
  }else{
    gain=0
    #all piles have to disappear, order should not matter
    i=min((2:5)[tokens[-1]>1])
    #set one token appart
    gain=max(gain,1-reward(tokens-((1:5)==i)))
    #create another singleton
    gain=max(gain,1-reward(c(tokens[1]+1,tokens[-1]-((2:5)==i))))}
  return(gain)}

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:

game=function(n=17,col=1,tak=rep(0,n)){
   frei=rew=0*tak
   # stopping rule
   if (sum(tak==col)==0){
     frei=(tak==0)}else{
     for (i in (1:n)[tak!=-col])
       frei[i]=(min(abs((1:n)[tak==col]-i))>1)}
   # left positions
   if (sum(frei)>0){
     for (i in (1:n)[frei==1]){
      prop=tak;prop[i]=col
      rew[i]=1-game(n=n,col=-col,tak=prop)}}
   # outcome of best choice
   return(max(rew))}

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:

gain=function(mine,yours,none){
  fine=none
  if (length(mine)>0)
    fine=none[apply(abs(outer(mine,none,"-")),
              2,min)>1]
  if (length(fine)>0){
   rwrd=0
   for (i in 1:length(fine)) 
    rwrd=max(rwrd,1-gain(yours,c(mine,fine[i]),
         none[none!=fine[i]]))
   return(rwrd)}
  return(0)}

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:

optim=function(n,m){

 outcome=(n<2*m+1)
 if (n>2*m){
   for (i in 1:(2*m))
     outcome=max(outcome,1-optim(n-i,i))
   }
 return(outcome)
}

eliminating solutions which dividers are not solutions themselves:

sol=lowa=plura[plura<100]
for (i in 3:6){
 sli=plura[(plura>10^(i-1))&(plura<10^i)]
 ace=sli-10^(i-1)*(sli%/%10^(i-1))
 lowa=sli[apply(outer(ace,lowa,FUN="=="),
                1,max)==1]
 lowa=sort(unique(lowa))
 sol=c(sol,lowa)}

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.

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

Follow

Get every new post delivered to your Inbox.

Join 1,019 other followers