-1
$\begingroup$

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?

  1. Choose a uniform random real, $n$, in the range $0-2$.

  2. Calculate $10^n$, where $n$ in the random number we got above.

  3. Round $10^n$ to the nearest integer $k$.

Bonus:

  • What is the best first question?
  • Is it possible in an average of 6 questions?
  • What is the maximum number of questions required?
$\endgroup$
4
  • 4
    $\begingroup$ What’s an infinitedesimal? $\endgroup$
    – Sneftel
    Dec 24, 2023 at 4:30
  • 3
    $\begingroup$ I assume the feedback given after each guess is the same as usual, the lower, higher, or same? $\endgroup$
    – justhalf
    Dec 24, 2023 at 4:56
  • 1
    $\begingroup$ Assuming infinitedesimal means a uniform distribution. how is best measured? what metric measures the goodness of a game? $\endgroup$
    – Jasen
    Dec 24, 2023 at 5:49
  • $\begingroup$ All of the given answers assume that we are trying to guessing the number, with responses being higher or lower for an incorrect guess. The recent edit of yes/no responses does not agree, nor can it be inferred as the original intent. $\endgroup$ Dec 26, 2023 at 1:00

3 Answers 3

1
$\begingroup$

Let's do

binary search on the 0-2 interval.

So if the random number is 1.9, our guesses would be 10^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.

Try it online!

$\endgroup$
2
  • $\begingroup$ One million iterations give an average of rot13(sbhe cbvag avar sbhe) guesses. Penguino's method is slightly better at rot13(sbhe cbvag rvtug avar rvtug frira) guesses. $\endgroup$ Dec 25, 2023 at 2:58
  • $\begingroup$ @DanielMathias Seems sensible; I was probably optimising for the simplicity of the method more than for squeezing out the final bit of performance. $\endgroup$
    – Bass
    Dec 25, 2023 at 3:16
1
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The number can always be guessed in seven or fewer guesses by using a binary search algorithm. $\endgroup$ Dec 24, 2023 at 21:24
  • 1
    $\begingroup$ Ah, I see the problem. The OP never mentioned that after you guess, you are told whether the true answer is higher or lower than your guess. That was in the linked problem that was listed as inspiration for this one, which I didn't read. $\endgroup$
    – Stevish
    Dec 27, 2023 at 14:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.