Average number of guesses for simple game

Question

The guess-a-number game starts with one player (the chooser) picking a number between 1 and 100 (inclusive) and secretly writing it down. The other player (the guesser) attempts to guess the number. After each guess, the chooser responds with “correct” (the guesser guessed the number and the game is over), “higher” (the actual number is higher than the guess), or “lower” (the actual number is lower than the guess).

What is the average number of guesses the guesser will need to find the number given that he uses the optimal, most efficient strategy?

I found that it will be 6 guesses $29/32$ times and 7 guesses $3/32$ times using the most clumsy method ever which I won't post. It can be no more than 7 since $2^7=124>100$.

It was like

$(100-1)/2 = 49.5, \\(49-1)/2 = 24, \\(50-1)/2 = 24.5 \\-> 24, 25 $

with 24 $3/4$ of the time and 25 $1/4$ of the time, etc etc etc.

What is a better way (since the method had so many opportunities for error I'm probably wrong anyway)?

Answer 1

If you want to split the interval, your first guess should be $\frac {100+1}2=50.5$ You can be a bit more efficient by making your guesses whole numbers, giving a chance of getting "correct". early. So if your first guess is $50$, you get away with $1$ guess $1/100$ of the time, while if you guess $50.5$ you lose the chance to be lucky. You have $2/100$ chance of winning in two guesses, $4/100$ chance in three, and so on. Other than that, binary search cannot be beaten.

Answer 2

The answer is 5.8 exactly.

Between 1 and 100: There is 1 number that takes 1 guess (50). There are 2 numbers that take 2 guesses (25, 75). There are 4 numbers that take 3 guesses (12, 38, 62, 88).

Likewise, there are 8 numbers that take 4 guesses, 16 that take 5, and 32 that take 6.

This means there are 37 remaining numbers that take 7 guesses.

1*1+2*2+4*3+8*4+16*5+32*6+37*7 = 580.

Meaning it will take 580 guesses to guess each number between 1 and 100. For a single number the average is 580/100 = 5.8.

Answer 3

The average number of guesses would be ~5.80905. As the analytical approach to solving this would be rather extensive, the answer could be estimated with a simple simulation, in which the program follows the optimal strategy of cutting the set of values in half by selecting the mid point, and then we average the number of trials after a large number of iterations.

n <- 100
count<-c() 

for (i in 1:100000){
  
  s <- round(runif(1,0.5,n+0.5),0)
  iter <- 1
  guess <- trunc(n /2)
  iter_par <-trunc(guess/2)
  
  while (guess!= s){

    ifelse(guess<s,guess<-guess+iter_par,guess<-guess-iter_par)
    iter_par<-round(iter_par/2,0)
    ifelse(iter_par<1,iter_par<-1,iter_par<-iter_par)
    iter<-iter+1
  }
  
  count<-append(count,iter)  
 
}

mean(count)