a closed-form but intractable birthday

An interesting [at least for me!] question found on X Validated yesterday, namely how to simulate efficiently from the generalised birthday problem (or paradox) distribution, which provides the probability of finding exactly k different birthday dates as

where m is the number of individuals with a random birthday and n the number of days (e.g., n=365). The paradox with this closed-form formula (found by the inclusion-exclusion rule) is that it is too unstable to use per se. While it is always possible to run m draws from a uniform over {1,…,n} and count the number of different values, e.g.,

x=length(unique(sample(1:n,m,rep=TRUE)))

this takes much more time than using the exact distribution, if available:

sample(1:m,1e6,rep=TRUE,prob=eff[-1])

I played a little bit with the notion of using an unbiased estimator of the said probability, but the alternating series means that the unbiased estimator may end up being negative, which is an issue met in recent related papers like the famous Russian Roulette.

Le Monde puzzle [#860]

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

awalé

Following Le Monde puzzle #810, I tried to code an R program (not reproduced here) to optimise an awalé game but the recursion was too rich for R:

Error: evaluation nested too deeply:
infinite recursion / options(expressions=)?

even with a very small number of holes and seeds in the awalé… Searching on the internet, it seems the computer simulation of a winning strategy for an awalé game still is an open problem! Here is a one-step R function that does  not produce sure gains for the first player, far from it, as shown by the histogram below…  I would need a less myopic strategy by iterating  this function at least twice.

onemorestep=function(x,side){
# x current state of the awale,
# side side of the awale (0 vs 1)

M=length(x);N=as.integer(M/2)
rewa=rep(0,M)
newb=matrix(0,ncol=M,nrow=M)

for (i in ((1:N)+N*side)){

 if (x[i]>0){
   y=x
   y[i]=0
   for (t in 0:(x[i]-1))
     y[1+(i+t)%%M]=y[1+(i+t)%%M]+1

   last=1+(i+t)%%M
   if (side){ gain=(last<=N)
    }else{ gain=(last>N)}

   if (gain){# ending up on the right side
     rewa[i]=0
     while (((last>0)&&(side))||((last>N)||(!side)))
     if ((y[last]==2)||(y[last]==3)){
          rewa[i]=rewa[i]+y[last];y[last]=0
          last=last-1
          }else{ break()}
     }
   newb[i,]=y
   }
  }
if (max(rewa)>0){
  sol=order(-rewa)[1]
  }else{ sol=rang=((1:N)+N*side)[x[((1:N)+N*side)]>0]
   if (length(rang)>1) sol=sample(rang,1,prob=x[rang]^3)}

   return(list(reward=max(rewa),board=newb[sol,]))
}

interesting puzzle

In addition to its weekly mathematics puzzles, Le Monde is now publishing a series of vulgarisation books on mathematics, under the patronage of Cédric Villani. Jean-Michel Marin brought me two from the series, one on the golden number and one on Pythagoras’ theorem. (This is actually a translation of a series published by El Pais last year.) Those books are a bit stretched given the topic, even though I enjoyed the golden number (the second one having a lot of redundancy with the first one.) However, I came upon an interesting question, namely about the maximum size of a cube that could fit through a tunnel drilled through the unit cube. Sadly, I could not find an answer to this problem on the web, even though the book mentions a solution with a side larger than one…

Le Monde puzzle [#810]

The current puzzle is as follows:

Take a board with seven holes and seeds. The game starts with one player putting the seeds on the holes as he or she wishes. The other player picks a seed wherever. Then, alternatively, each player picks a seed in a hole contiguous to the previous one. The loser is the one finding only empty holes to pick from. Who is the winner with 28? 29? 30 seeds?

This is a simplified version of the awalé or oware we used to play with my kids.

I first defined a recursive function on the win/loose value of a particular location, based on the assumption that each player was picking the best location at each step:

f=function(x,i){
 if (x[i]==0){# losing location
    v=0;return(v)}else{

   if ((i>1)&&(i<7)){
     x[i]=x[i]-1;return(1-max(f(x,i-1),f(x,i+1)))
     }else{

       if (i==1){ x[i]=x[i]-1;return(1-f(x,2))}
       if (i==7){ x[i]=x[i]-1;return(1-f(x,6))}
       }
}}

and then checked whether or not winning solutions were available for 28, 29, and 30 seeds dropped at random:

N=28 #number of seeds
glosol=1  #boolean
for (t in 1:10^3){#random starts

  seeds=sample(1:7,N,rep=TRUE)
  x=rep(0,7)
  for (i in 1:7) x[i]=sum(seeds==i)

  sol=i=0 #second player result
  while ((i<7)&&(sol==0)){
        i=i+1;sol=f(x,i)}
  if (sol==0){ #winning configuration for first player
    glosol=0;print(x);break()}
  }

getting solutions for 28 (5 6 2 3 5 5 2) and 30 (6 6 2 4 4 5 3), but none for 29.

Actually, the rule seems to be that odd numbers get no solutions and even numbers get solutions (e.g., 1 1 1 1 1 2 1 for 8 seeds). (This means further that to build a winning allocation for 2N seeds, we only need to take a configuration at random with 2N+1 seeds and check which seed we need to remove to get a winning (for the “other” player) configuration.)