1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ I don't think there is a better way. $\endgroup$
    – Arthur
    Mar 26, 2017 at 0:13
  • $\begingroup$ @Arthur I was thinking use some properties of the number 100 like a binary representation (1100100) to do some magic or something, immediately arriving at the conclusion that is was 6 guesses 29/32 times. $\endgroup$
    – Joao Noch
    Mar 26, 2017 at 0:17
  • $\begingroup$ Note that $2^7=128$, but that doesn't change anything. $\endgroup$ Mar 26, 2017 at 0:18
  • $\begingroup$ @RossMillikan if it helps $100=2^6+2^5+2^2$ $\endgroup$
    – Joao Noch
    Mar 26, 2017 at 0:19
  • 1
    $\begingroup$ You might want to be slightly more specific about what you mean by "average". Are you assuming the chooser picks the number at random (according to which distribution?) and you are averaging over that? Are you assuming that the guesser's algorithm is randomized, and you are averaging over the guesser's choices? $\endgroup$
    – Anonymous
    Mar 26, 2017 at 7:43

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ What about a formula that when given the range (1-100) outputs the guess average length? I just want an easier way to find the average number of guesses. $\endgroup$
    – Joao Noch
    Mar 26, 2017 at 1:09
  • $\begingroup$ This answer assumes that the chooser picks a number at random. In a game, both players try their best and thus the chooser may be e.g. "hiding" his numbers in 1 or in 100, making the average higher. $\endgroup$
    – mlc
    Mar 27, 2017 at 6:35
  • $\begingroup$ Hey, don't I have a 2 in 99 chance of winning in two guesses, 4 in 97 chance of winning in three, etc because if you are on your second guess you are selecting out of a range of 99 options? (every number except 50) $\endgroup$
    – Joao Noch
    Apr 2, 2017 at 1:29
  • $\begingroup$ Not quite. Before you start, you have a 2 in 100 chance of winning in exactly two guesses, as you will do so if the number is 25 or 75 (or some small variation). Having failed on the first guess, your chance on the second depends on the result of the first. If your first was 50 and you are told lower, your chance on the second is 1 in 49. If you are told higher it is 1 in 50. If you are told correct, your chance on the second is zero. $\endgroup$ Apr 2, 2017 at 4:35
0
$\begingroup$

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)
$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .