another riddle

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.

Details about this computation are as follows: I first tried a brute force implementation to figure out the optimal strategy but 8 levels of recursion just take too long. I could thus experiment with the function

last=9

sol=function(n,a,b){
#n is depth and (a,b) is range
 ranj=b-a+1 
 if ((n==last)||(ranj==1)){
    return(b)
 }else{
  gain=a+sol(n+1,a+1,b)
  if (ranj>2){
   for (i in 2:(ranj-1))
     gain=max(gain,(a+i-1)+sol(n+1,a,a+i-2)+sol(n+1,a+i,b))}
  gain=max(b+(b-a)*sol(n+1,a,b-1),gain)
  return(gain)}}

for small enough values of b-a. The function sol returns the maximal expectation times b-a+1 to gain some computing time. The expected return for a given guess c is c if the guess is correct plus the expected gain for both sides, which has the major property that the denominator b-a cancels, leading to the recurrence property

G(n,c,a,b) = c + G⁰(n+1,a,c-1) + G⁰(n+1,c+1,b)

except at the end points.

While inapplicable for the direct resolution of the puzzle, this function sol was still good enough to figure out that the optimal guess at level 8 was b-1, at level 7 was b-3, and so on. (Again, provided the range (b-a) is large enough.) This led me to define the new function

lagz=rep(0,9)
for (i in 2:9) lagz[i]=2*lagz[i-1]+1

propsol=function(n,a,b){
 if ((n==last)||(a==b)){
    return(b)
   }else{
     i=b-lagz[10-n]
     return(i+propsol(n+1,a,i-1)+propsol(n+1,1+i,b))
     }}

which returns

> propsol(1,1,1000)/1001
[1] 380.3147

for its optimal expected gain. Since the gain is invariant by translation, we can also deduce the probability of winning as

> (propsol(1,1001,2000)-propsol(1,1,1000))/1001
0.5104898

The riddle of this week happened to be solved on this very blog about a month ago! Since it simply asks what is the expected number of uniform draws until the sum exceeds one. Which is Gnedenko’s exercice with solution e, discussed over a few blog entries.