Inspired by Another 6 tries to guess a number between 1-100, what is the most efficient strategy of questions requiring yes/no answers to guess the number $k$, if $k$ is formed in the following way?
Choose a uniform random real, $n$, in the range $0-2$.
Calculate $10^n$, where $n$ in the random number we got above.
Round $10^n$ to the nearest integer $k$.
Bonus:
It is possible to guess in an average of less than 6 tries. It is a bit fiddly to try and explain but basically:
Rule 1
1) At each stage use a binary choice question that splits the remaining possibilities into approximately equiprobable sets.
Rule 2
2) Where possible, split the remaining possibilities into two subsets which are each a power of two or if that doesn't fit well with rule 1, then split them so the lower magnitude set is a power of two.
A very much non-optimized algorithm following those rules works out as follows:
First split at (<=12,>12). If <=12 then split at (<=4,>4), then use a simple binary (half and half) split henceforth. If >12 then split at (<=28,>28). If <28 then use a simple binary split henceforth. If >28 then split at (<=52,>52) and then if <=52 split at (<=36,>36). Either way use a binary split henceforth. If greater than 52 then split at (<=68,>68) and use a binary split henceforth.
Following that algorithm I get an average of
4.8987 (thanks Daniel)
guesses. I am sure that a better optimized algorithm can do a little better.
So for my algorithm the first question should be:
"Is your number less that or equal to twelve?"
Note that as 100 < $2^7$, you can always get the number in at most 7 guesses using a 'standard' binary search - that has a better worst case number of questions, but on average is less efficient than my proposed algorithm.
Let's do
binary search on the 0-2 interval.
So if the random number is 1.9, our guesses would be10^1,10^1.5,10^1.75, and so on.
Our first guess is then 10, and the next guess is either 32 or 3, depending on the answer, and so on.
This gives a bad worst case, but those happen on unlucky cases that are quite rare. On the other hand, we hit the majority of cases extremely fast. So fast, actually, that the average number of guesses is
a bit less than 5.
EDIT: I missed the main question! You must guess...
10 times on average to guess the correct number. See below for all the logic, but guessing 1-10 will cover about 51.05% of values of n.
Original answer:
At first I thought that the best first guess must be:
1. Because the lower the number, the more often it will come up.
However...
That was before rounding. From 0 to ~0.176, you get a number between 1 and 1.4999, which rounds to 1. So, 1 has a 8.8% chance (0 - 0.176 represents about 8.8% of the numbers from 0-2) of being drawn. But from ~0.177 to ~0.397, you get numbers from 1.5 to 2.4999, which all round to 2. So, 2 has around an 11% chance of being drawn. After that, 3 is generated by any number from ~0.398 to ~0.544, which only represents 7.3% of the numbers from 0-2.
So, the best number to guess first is:
2. Followed by 1, then 3, 4, 5, 6. And these 6 guesses only cover about 40.6% of the numbers that could be chosen for n, so, on average, you could not guess the number in only 6 tries.
