Best Method To Guess a Random Number Between 1 and 100? Suppose there is a random integer between 1 and 100. Two people are playing a game where the goal is to try and guess this random integer. The winner is decided by who can correctly guess this random integer in the fewest amount of guesses.

*

*Player 1 chooses random integers until he correctly guesses the number (let's say that even those his guesses are random, he will not guess a number that he has already guessed)

*Player 2 guesses integers 1,2,3,4,5... until he correctly guesses the number

I am trying to figure if one of these methods is a "better" method of guessing the correct number.
Here is my logic so far:

*

*Obviously, if the number is closer to 0, Player 2 has a better method

*Obviously, if the number is closer to 100, Player 1 has a better method

*If the number is around 50, I have a feeling that Player 1 still has a better method.

Is there a way to quantify which of these methods is better? Is there a way of estimating the average number of guesses required to guess the correct number using Player 1's method compared to Player 2's method?
I was thinking of writing a computer simulation that would see how many times Player 1 wins compared to Player 2 over several games, but I was looking for a more "mathematical way" of approaching this problem.
Could someone please help me with this?
Thank you!
 A: If the only answers are "Matches" or "Doesn't match", you can't do better than asking for each. If your oponent finds out you are asking in some particular order, she can arrange it to select your last guess, so it'll take 100 guesses. Best strategy is to guess at random (no repeats).
If the answers are "Match", "Too high", "Too low", best strategy is to guess at the middle of the remaining range, i.e., 50, and then 25 or 75, etc. This will take at most roughly $\log_2 100 = 6.64$ guesses.
A: How Many Guesses on Average?
In order to determine the best approach, we can compute the expected number of guesses using that approach. A strategy that we expect to require fewer guesses on average will surely be the better strategy.
Going in Order
Suppose you guessed by starting with 1, then 2, then so on. How many guesses, on average, would that take?
Well, $\frac{1}{100}$ of the time the number would be 1 and you would get it the first try. Then another $\frac{1}{100}$ of the time, it would be 2 and you'd guess it on the second try. This continues, all the way up through 100, where $\frac{1}{100}$ of the time you'd guess it last and take 100 guesses.
Adding up these cases, the expected value is:
$$\frac{1}{100} + 2*\frac{1}{100} + 3*\frac{1}{100} ... + 100 * \frac{1}{100}$$
which is equivalent to
$$\frac{1 + 2 + 3 + ... + 100 }{100}$$
And, as a young Carl Friedrich Gauss allegedly but famously computed, that comes out to
$$\frac{5050}{100} = 50.5$$
So, by going in order, your average guess count with this strategy is 50.5.
Guessing at Random
Let's look at the other approach. Given that the target number is already chosen, you have a $\frac{1}{100}$ to randomly guess the correct number on the first try. Simple enough.
What about the second try? Well, that means you got it wrong first and then right, so the probability would be: $\frac{99}{100} * \frac{1}{99}$, which simplifies to...  $\frac{1}{100}$ again. And for three guesses, you'd have to get it wrong twice and right once: $\frac{99}{100} * \frac{98}{99} * \frac{1}{98}$ or $\frac{1}{100}$.
So each guess count has a probability of $\frac{1}{100}$. But didn't we just see that? That means the expected value is
$$\frac{1}{100} + 2*\frac{1}{100} + 3*\frac{1}{100} ... + 100 * \frac{1}{100} = 50.5$$
Generalizing
Because the target number is equally likely to be any number between 1 and 100, there will always be a $\frac{1}{100}$ chance that we will need a certain number of guesses. One strategy might favor low numbers, but as you observed, it will then suffer when the target is chosen to be high. This balances out such that no strategy is better than others (so long as you never repeat). Any strategy will average to 50.5 required guesses when applied to a large number of games.
A: If the original number is selected uniformly at random it doesn't matter; both strategies work exactly as well, in the sense that the distribution over the number of tries they need to succeed are the same. Namely, after $k$ wrong guesses, both players only know that the number is uniformly random over all the remaining possibilities, so each player has a probability of $\frac{1}{100 - k}$ of winning on the next guess regardless of how they choose it, deterministically or randomly.
In fact every strategy does equally well; you don't learn anything from a guess other than ruling out the guess, so every guess gives you exactly the same amount of information and it's not possible for any strategy to do better than any other.
A: Personally, I'd start by writing the computer simulation to see if there is in fact anything there to prove.  (It won't take long.)
If the two methods are the same on average you will have saved yourself a lot of time looking for a formal proof.
It may also give you some idea of how the two methods vary over the range of numbers.
