*Simple* puzzle time - guess the number
-
I'm thinking of a natural number N and you have to guess which one it is. When you ask about a number, I'll tell you whether you guessed correctly, and if you guessed incorrectly, I'll tell you whether the number is smaller or larger than the one you guessed.
There's no limit on how big N is. It could have 7 million digits, for instance.
Which strategy would minimize the number of guesses you need?
( @jon-nyc and @Horace can only post in this thread after 24 hours have passed!)
-
@klaus said in *Simple* puzzle time - guess the number:
I'm thinking of a natural number N and you have to guess which one it is. When you ask about a number, I'll tell you whether you guessed correctly, and if you guessed incorrectly, I'll tell you whether the number is smaller or larger than the one you guessed.
There's no limit on how big N is. It could have 7 million digits, for instance.
Which strategy would minimize the number of guesses you need?
( @jon-nyc and @Horace can only post in this thread after 24 hours have passed!)
Exponential changes in guess, then halfway back once your answer changes.
Please love yourself.
-
@aqua-letifer said in *Simple* puzzle time - guess the number:
Exponential changes in guess, then halfway back once your answer changes.
That's a good start, but what exactly do you mean by "exponential changes in guess"? What are you going to do in each step? Double the guess? Triple it? Multiply it by 5000? Choose a too low multiplier and you need too many steps in the first phase. Use a too high multiplier and your search interval for the second phase becomes too big, which means you need more guesses there...
-
@klaus said in *Simple* puzzle time - guess the number:
@aqua-letifer said in *Simple* puzzle time - guess the number:
Exponential changes in guess, then halfway back once your answer changes.
That's a good start, but what exactly do you mean by "exponential changes in guess"? What are you going to do in each step? Double the guess? Triple it? Multiply it by 5000? Choose a too low multiplier and you need too many steps in the first phase. Use a too high multiplier and your search interval for the second phase becomes too big, which means you need more guesses there...
I guess I'd go with e . Seems a natural enough start.
-
Let's take 2 as the multiplier. Let's denote the logarithm with base 2 as lg(x).
Then your strategy would need around lg(N) + lg(N) guesses; the left summand being the first phase of doubling the guess, the second summand being the second phase of binary search through the remaining interval.
But one can do better than that. For instance, try to think whether there is a strategy where 2lg(lg(N)) + lg(N) guesses are sufficient.
-
If anyone's interested, there's a nice paper from 1976 (!) that goes into the details.
https://www.sciencedirect.com/science/article/pii/0020019076900715
For instance, you can do a binary search for the first phase, that is, not just double but initially you double, then quadruple, then times 8 and so forth. That would reduce the number of guesses in the first phase to around lg(lg(N)) instead of lg(N) while also not making the search interval for the second phase too big.
