## Le Monde puzzle [#965]

Posted in Kids, R with tags , , , on June 14, 2016 by xi'an

A game-related Le Monde mathematical puzzle:

Starting with a pile of 10⁴ tokens, Bob plays the following game: at each round, he picks one of the existing piles with at least 3 tokens, takes away one of the tokens in this pile, and separates the remaining ones into two non-empty piles of arbitrary size. Bob stops when all piles have identical size. What is this size and what is the maximal number of piles?

First, Bob can easily reach a decomposition that prevents all piles to be of the same size: for instance, he can start with a pile of 1 and another pile of 2. Looking at the general perspective, an odd number of tokens, n=2k+1, can be partitioned into (1,1,2k-1). Which means that the decomposition (1,1,…,1) involving k+1 ones can always be achieved. For an even number, n=2k, this is not feasible. If the number 2k can be partitioned into equal numbers u, this means that the sequence 2k-(u+1),2k-2(u+1),… ends up with u, hence that there exist m such that 2k-m(u+1)=u or that 2k+1 is a multiple of (u+1). Therefore, the smallest value is made of the smallest factor of 2k+1. Minus one. For 2k=10⁴, this value is equal to 72, while it is 7 for 10³. The decomposition is impossible for 2k=100, since 101 is prime. Here are the R functions used to check this analysis (with small integers, if not 10⁴):

```solvant <- function(piles){
if ((length(piles)>1)&((max(piles)==2)||(min(piles)==max(piles)))){
return(piles)}else{
i=sample(rep(1:length(piles),2),1,prob=rep(piles-min(piles)+.1,2))
while (piles[i]<3)
i=sample(rep(1:length(piles),2),1,prob=rep(piles-min(piles)+.1,2))
split=sample(rep(2:(piles[i]-1),2),1,
prob=rep(abs(2:(piles[i]-1)-piles[i]/2)+.1,2))
piles=c(piles[-i],split-1,piles[i]-split)
solvant(piles)}}

disolvant <- function(piles){
sol=solvant(piles)
while (min(sol)<max(sol))
sol=solvant(piles)
return(sol)}

resolvant <- function(piles){
sol=disolvant(piles)
lasol=sol;maxle=length(sol)
for (t in 1:piles){
sol=disolvant(piles)
if (length(sol)>maxle){
lasol=sol;maxle=length(sol)}}
return(lasol)}
```

## 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

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)}
```

```> subs=rep(0,16)