Archive for Alice and Bob

Le Monde puzzle [#1019]

Posted in Books, Kids with tags , , , , , , on September 7, 2017 by xi'an

A gamey (and verbose) Le Monde mathematical puzzle:

A two-player game involves n+2 cards in a row, blue on one side and red on the other. Each player can pick any blue card among the n first ones and flip it plus both following ones. The game stops when no blue card is left to turn. The gain for the last player turning cards is 20-t, where t is the number of times cards were flipped, with gain t for its opponent. Both players aim at maximising their gain.

1. When n=4 and all cards are blue, can the first player win? If not, what is the best score for this player?

2. Among all 16 configurations at start, how many lead to the first player to win?

3. When n=10 and all cards are blue, how many cards are flipped an odd number of times for the winning configuration?

The first two questions can easily be processed by an R code like the following recursive function:

liplop <- function(x,n,i){
  if (max(x[1:n])==0){
    return(i)
  }else{
    sol=NULL
    for (j in (1:n)[x[1:n]==1]){
      y=x;y[j:(j+2)]=1-y[j:(j+2)]
      sol=c(sol,20-liplop(y,n,i+1))}
    return(max(sol))}}

Returning

> liplop(rep(1,6),4,0)
[1] 6

Meaning the first player cannot win, by running at most six rounds. Calling the same function for all 4⁴=16 possible configurations leads to 8 winning ones:

[1] 0 0 0 1
[1] 0 0 1 1
[1] 0 1 0 1
[1] 0 1 1 1
[1] 1 0 0 0
[1] 1 0 1 0
[1] 1 1 0 0
[1] 1 1 1 0

Solving the same problem with n=10 is not feasible with this function. (Even n=6 seems out of reach!)

Le Monde puzzle [#1000…1025]

Posted in Kids, R with tags , , , , , , on March 28, 2017 by xi'an

Le Monde mathematical puzzle launched a competition to celebrate its 1000th puzzle! A fairly long-term competition as it runs over the 25 coming puzzles (and hence weeks). Starting with puzzle #1001. Here is the 1000th puzzle, not part of the competition:

Alice & Bob spend five (identical) vouchers in five different shops, each time buying the maximum number of items to get close to the voucher value. In these five shops, they buy sofas at 421 euros each, beds at 347 euros each, kitchen appliances at 289 euros each, tables at 251 euros each and bikes at 211 euros each, respectively. Once the buying frenzy is over, they realise that within a single shop, they would have spent exactly four vouchers for the same products. What is the value of a voucher?

going to war [a riddle]

Posted in Books, Kids, Statistics with tags , , , , , on December 16, 2016 by xi'an

On the Riddler this week, a seemingly obvious riddle:

A game consists of Alice and Bob, each with a $1 bill, receiving a U(0,1) strength each, unknown to the other, and deciding or not to bet on this strength being larger than the opponent’s. If no player bets, they both keep their $1 bill. Else, the winner leaves with both bills. Find the optimal strategy.

As often when “optimality” is mentioned, the riddle is unclear because, when looking at the problem from a decision-theoretic perspective, the loss function of each player is not defined in the question. But the St. Petersburg paradox shows the type of loss clearly matters and the utility of money is anything but linear for large values, as explained by Daniel Bernoulli in 1738 (and later analysed by Laplace in his Essai Philosophique).  Let us assume therefore that both players live in circumstances when losing or winning $1 makes little difference, hence when the utility is linear. A loss function attached to the experiment for Alice [and a corresponding utility function for Bob] could then be a function of (a,b), the result of both Uniform draws, and of the decisions δ¹ and δ² of both players as being zero if δ¹=δ²=0 and

L(a,b,\delta^1,\delta^2)=\begin{cases}0&\text{if }\delta^1=\delta^2=0\\\mathbb{I}(a<b)-\mathbb{I}(a>b)&\text{else}\\\end{cases}

Considering this loss function, Alice aims at minimising the expected loss by her choice of δ¹, equal to zero or one, expected loss that hence depends  on the unknown and simultaneous decision of Bob. If for instance Alice assumes Bob takes the decision to compete when observing an outcome b larger than a certain bound α, her decision is based on the comparison of (when B is Uniform (0,1))

\mathbb{P}(a<B,B>\alpha)-\mathbb{P}(a>B,B>\alpha)=2(1-a\vee\alpha)-(1-\alpha)

(if δ¹=0) and of 1-2a (if δ¹=1). Comparing both expected losses leads to Alice competing (δ¹=1) when a>α/2.

However, there is no reason Alice should know the value of α when playing the (single) game and so she may think that Bob will follow the same reasoning, leading him to choosing a new bound of α/4, and, by iterating the thought process, down all the way to α=0!  So this modelling leads to always play the game, with each player having a ½ probability to win… Alternatively, Alice may set a prior on α, which leads to another bound on a for playing or not the game. Which in itself is not satisfactory either. (The published solution is following the above argument. Except for posting the maths expressions.)

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 [#952]

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

A quite simple Le Monde mathematical puzzle again with Alice and Bob:

In a multiple choice questionnaire with 50 questions, Alice gets a score s such that Bob can guess how many correct (+5 points), incorrect (-1 point) and missing (0 point) Alice got when adding that Alice could not have gotten s-2 or s+2. What is Alice’s score?

A first point is that the overall score is s=5c-i with c+i≤50.  Without further information, the possible results are all integers 0≤c≤50 such that c≥s/5 and 0≤i=s-5c≤50. Possible scores range from -50 to 250, but a quick R check shows that ten values are impossible

vales=rep(0,le=50+1+250)
for (c in 0:50){
for (i in 0:(50-c))vales[5*c-i+50+1]=1}

which produces

> (1:length(vales))[vales==0]-50-1
[1] 231 236 237 241 242 243 246 247 248 249

Thus looking at the differences, there is only one case for which s-2 and s+2 are impossible values, namely s=239. This means c=48, i=1 since c=49 leads to an impossible i.

 

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

a refutation of Johnson’s PNAS paper

Posted in Books, Statistics, University life with tags , , , , , , , on February 11, 2014 by xi'an

Jean-Christophe Mourrat recently arXived a paper “P-value tests and publication bias as causes for high rate of non-reproducible scientific results?”, intended as a rebuttal of Val Johnson’s PNAS paper. The arguments therein are not particularly compelling. (Just as ours’ may sound so to the author.)

“We do not discuss the validity of this [Bayesian] hypothesis here, but we explain in the supplementary material that if taken seriously, it leads to incoherent results, and should thus be avoided for practical purposes.”

The refutation is primarily argued as a rejection of the whole Bayesian perspective. (Although we argue Johnson’ perspective is not that Bayesian…) But the argument within the paper is much simpler: if the probability of rejection under the null is at most 5%, then the overall proportion of false positives is also at most 5% and not 20% as argued in Johnson…! Just as simple as this. Unfortunately, the author mixes conditional and unconditional, frequentist and Bayesian probability models. As well as conditioning upon the data and conditioning upon the rejection region… Read at your own risk. Continue reading