tl;dr : Bob can guess x within
$\log_{\sqrt5-1}{n} \approx \log_{1.236}{n}$ which is an improvement on the initial upper bound of $2 \log_{1.5} n \approx \log_{1.225}n$ guesses.
Bob's guessing strategy to achieve this upper bound involves a Fibonacci sequence or the golden ratio. I've not mathematically proved this limit, but it has been empirically verified for selected values of $n$ up to $10^9$.
It is trivially possible for Bob to guess $x$ within n guesses. i.e.
1. Pick a number in the interval [1,n] that he's not guessed before.
2. If Alice says it's right, stop.
3. Otherwise repeat from step 1.
But Bob wants to prove he's smart, so one way to improve on this (at least in the average case) would be:
1. Start with "candidate guesses" including all numbers in the interval [1,n]
2. Remove a number at random from the candidate guesses...
3. If Alice says it's right, stop.
4. Check all previous responses against each number still in the candidate list.
5. Drop any remaining candidates where Alice would have given 2 lies in a row.
6. Repeat from step 2.
If Alice was answering at random (unless the randomly chosen answer eliminated all possibilities for x), then each number has 50% chance being compatible with each response, so on average, this could eliminate about 25% of the numbers each guess - those incompatible with two consecutive responses.
But Alice is probably smart and wants to make Bob look stupid, so will make it take longer than this if she can.
Bob still hasn't strictly improved the upper bound on the duration of the game, so risks looking stupid even though his expected average number of guesses is much lower. Instead he can get more systematic:
Define $f_0$ as the empty set $\emptyset$, and $t_0$ as the set containing all numbers in the interval [1,n].
For guess $i$ there are two possibilities:
- if $f_{i-1} = \emptyset$, Bob guesses the median value from $t_{i-1}$. If Alice says "higher", Bob defines $t_i$ as the subset of $t_{i-1}$ that are higher than the median, and $f_i$ as the subset of $t_{i-1}$ that are lower than the median, and conversely if Alice says "lower".
In other words, $t_i := \{t_{i-i} | \operatorname{true}_i\}, f_i := \{t_{i-i} | \operatorname{false}_i\}$
- if $f_{i-1}$ is non-empty, Bob guesses the median value from $f_{i-1}$.
If Alice's response is the same as her response to guess $i-1$, define $t_i := t_{i-1}\cup \{f_{i-1}|\operatorname{true}_i\}$, and $f_i := \emptyset$.
If Alice's response contradicts her response to guess $i-1$, it will necessarily also be false for all members of $t_{i-1}$, so define $t_i := \{f_{i-1}|\operatorname{true}_i\}$ and $f_i := t_{i-1}$.
Either way, Bob has eliminated half of $f_{i-1}$
However, this is not optimal because:
When Alice gives two consecutive responses that don't contradict each other, Bob is forced to start again with $f_i = \emptyset$, taking an extra guess to get back "where he was".
So, of course, Alice will do that, picking a new $x$ that doesn't break the rules.
To improve his technique, Bob could instead
- if $f_{i-1}$ is non-empty, Bob guesses the whichever of the 33rd and 67th percentiles (1/3 or 2/3 of the way down the list of remaining numbers) from $f_{i-1}\cup t_{i-1}$ falls within $f_{i-1}$.
That way, if Alice's response agrees with her previous response, Bob eliminates 1/3 of all remaining numbers, and otherwise, although he eliminates fewer numbers with guess $i$, he also avoids "wasting" a guess merely to create a non-empty $f_{i+1}$, so ends up ahead overall.
An example game following these rules:
Alice: "Ok, you've got to guess a number from 1 to 100"
Bob: "50?"
Alice: "Higher" (without loss of generality)
Bob sets $t_1$ as 51-100, and $f_1$ as 1-49
Bob: "33?"
Option 1:
Alice: "Higher"
Bob now knows Alice cannot have picked 1-33, as she would have been lying twice - the game starts completely fresh with Bob having 34-49 and 51-100 as the possibilities, and the most recent answer not contradicting either
Bob: "67?"
(half-way through list of remaining numbers, then continues equivalently to after his initial guess of "50")
Option 2:
Alice: "Lower"
Bob now knows for sure that Alice lied in one of her last 2 answers, but doesn't know which. 34-49 would represent 2 consecutive lies and can be immediately eliminated. 1-32 ($t_2$) are compatible with the last answer, and 51-100 ($f_2$) are incompatible with the last answer
Bob: "73?"
Option 2.1
Alice: "Lower"
Bob now knows Alice cannot have picked 74-100, as that would be 2 lies in a row, so the game restarts afresh with Bob having 34-49, and 51-72 as the possibilities
Bob: "53?"
(half-way through list of remaining numbers, then continues equivalently to after his initial guess of "50")
Option 2.2
Alice: "Higher"
Bob now knows for sure that Alice lied in one of her last 2 answers, but doesn't know which. 51-72 would represent 2 consecutive lies and can be immediately eliminated. 74-100 ($t_3$) are compatible with the last answer, and 1-32 ($f_3$) are incompatible with the last answer
Bob: "20?"
(The game continues in this manner. When the game resets with an option 1, Bob eliminates 1/3 of the numbers in 2 turns, when it does NOT reset, Bob eliminates at least 1/6 of the numbers each turn (and "usually" more than this), so it's at least equivalent to 1/3 every 2 turns...)
He'll probably find that Alice cheats in another way, as she clearly didn't like this game anyway!
As such the time taken is
approximately $2 \log_{1.5} n$
I subsequently wrote a program to simulate the game - evaluating the complete game tree recursively checking the sub-game for either possible response from Alice (except when there are just 1 or 2 items remaining, or we're restarting and already saw a subgame with the same $n$ and diarised the result).
This shows that all branches of the tree do in fact complete within the estimate given.
Result for 1 items: MinDepth:0, MaxDepth:0, TreeCount:1
Result for 2 items: MinDepth:0, MaxDepth:1, TreeCount:2
Result for 3 items: MinDepth:1, MaxDepth:2, TreeCount:5
Result for 4 items: MinDepth:2, MaxDepth:3, TreeCount:9
Result for 5 items: MinDepth:2, MaxDepth:4, TreeCount:15
Result for 6 items: MinDepth:3, MaxDepth:4, TreeCount:22
Result for 7 items: MinDepth:3, MaxDepth:5, TreeCount:33
Result for 8 items: MinDepth:4, MaxDepth:6, TreeCount:44
Result for 9 items: MinDepth:4, MaxDepth:6, TreeCount:59
Result for 10 items: MinDepth:4, MaxDepth:7, TreeCount:79
Result for 20 items: MinDepth:7, MaxDepth:10, TreeCount:517
Result for 30 items: MinDepth:8, MaxDepth:11, TreeCount:1676
Result for 40 items: MinDepth:9, MaxDepth:13, TreeCount:4010
Result for 50 items: MinDepth:10, MaxDepth:14, TreeCount:7960
Result for 100 items: MinDepth:13, MaxDepth:17, TreeCount:70564
Result for 200 items: MinDepth:15, MaxDepth:21, TreeCount:656182
Result for 500 items: MinDepth:19, MaxDepth:25, TreeCount:12995318
Result for 1000 items: MinDepth:22, MaxDepth:29, TreeCount:125724646
Result for 2000 items: MinDepth:24, MaxDepth:32, TreeCount:1225574962
Result for 5000 items: MinDepth:28, MaxDepth:37, TreeCount:24937382705
Result for 10000 items: MinDepth:30, MaxDepth:41, TreeCount:243874388920
Result for 20000 items: MinDepth:33, MaxDepth:44, TreeCount:2386461531926
Result for 50000 items: MinDepth:36, MaxDepth:49, TreeCount:48698821559827
Result for 100000 items: MinDepth:39, MaxDepth:52, TreeCount:476533288398158
The numbers for "MaxDepth" (which is 1 lower than number of guesses Bob needs) are short of the $2\log_{1.5}n$ formula by about 3 guesses for larger values of $n$.
It's possible that
even this modified approach is slightly non-optimal. Some tweaks to the exact percentiles used may be appropriate to better balance the benefit from avoiding "wasting" a guess against the alternative benefit of eliminating more numbers, perhaps dynamically depending on the size of the sets that will remain.
This would result in MinDepth and MaxDepth being closer to equal in the simulation above...
At this point we were directed to the original place this puzzle appeared, with all answers deleted until the contest closes. I figured that having done most of the effort I might as well enter the contest too, so signed up with that site, and modified my "checking" program first to be better optimised (which allowed my original program to exhaustively check for n=1000000 in less time than it previously took for n=100000), and then to actually play the game (as per original challenge) rather than doing an exhaustive search of the entire game tree.
During the course of these optimisations, I found (empirically) that a slight improvement could indeed be obtained,
the exact formulation of which was a bit clumsy in the program due to "off by 1" errors when trying to simplify it.
I defined a "surplus" for the number of options that are "false" by comparing 2/3 of these numbers with the number of options that would be "double false" by the proposed guess, and then adjusting the proposed guess by 2/3 of THIS difference.
The overall effect would seem the same as guessing to exclude 2/3 of the "false" numbers, but that simplification hadn't worked when I tried it in the program.
In practical terms, this optimisation reduced the maximum number of guesses for $n = 1000000$ from 63 to 62, whilst the attempted simplification actually increased it to 64.
Without a detailed case-by-case analysis of the effect of the different tweaks, I'm not sure if the asymptotic behaviour can be further improved, but I later realised that the original problem isn't scored by how fast "Bob" can guess the answer anyway, just by whether he does it within 120 guesses for $n = 10^9$ or not - a limit comfortably met by my implementation which should do it within 100 guesses.
A simplification after re-visiting later
I discovered that a simpler strategy gives the same minimum number of guesses:
Bob picks the median of a list where all numbers that are incompatible with the last answer appear 3 times, and all numbers that are compatible with the last answer appear once.
If he does this every time, the number picked will always (for remaining $n > 3$) be within the list of incompatible numbers, unless that list is empty.
This is equivalent to
picking the index of the incompatible number to use as the next guess as $\lfloor{|f_i|/2 + |t_i|/6}\rfloor$ (indexing into the set $f_i$ from the end furthest from $t_i$)
Further improvements
This remains non-optimal, and I modified the tree search program again to diarise results from ALL subtree searches (rather than just those where $f_i = \emptyset$), and look for nearby improvements - i.e. if one subtree was a different depth to the other, try to find a nearby guess that would make both subtrees the same depth.
As a result of this, I adjusted the factors when picking the index, and found an optimal result (where no adjustments were made) was where:
it picks the index of the incompatible number to use as the next guess as $\lfloor{0.5|f_i| + 0.191|t_i|}\rfloor$
Unfortunately, I have no mathematical justification for
the factor of 0.191. I simply confirmed that, when it was 0.190 the index got adjusted upwards for several items, and when it was 0.192, the index got adjusted downwards for several items. With 0.191, no adjustments were made for various runs doing fully exhaustive searches for various values of $n$ up to 10,000,000 (by which point the 64 bit integer holding the size of the search tree overflowed).
Practically, this means that for sufficiently large $n$
the maximum depth of the search tree is reduced by 3 compared to my original program. e.g. Bob can guess a number from 1 to 100000 within 50 guesses, rather than the 53 implied by MaxDepth = 52 from the originally posted output.
Taking the final output of the final version, and correlating the MaxDepth (which is 1 fewer than the number of guesses Bob makes), the number of guesses appears to correlate approximately as:
$2\log_{1.53}n-3$, or equivalently $\log_{1.237}n-3$.
With the various optimisations, an exhaustive tree search for $n=10^9$ was just practical with the search program. I aborted it on the first attempt so the output below is only up to $n=10^8$, confirming Bob can guess this within
83 guesses, which agrees with the predicted $\log_{1.237}n-3 = 83.6$.
Full output from final version before I aborted it:
Result for 1 items: MinDepth:0, MaxDepth:0, TreeCount:1
Result for 2 items: MinDepth:1, MaxDepth:1, TreeCount:3
Result for 3 items: MinDepth:2, MaxDepth:2, TreeCount:7
Result for 4 items: MinDepth:2, MaxDepth:3, TreeCount:11
Result for 5 items: MinDepth:3, MaxDepth:4, TreeCount:19
Result for 6 items: MinDepth:3, MaxDepth:4, TreeCount:29
Result for 7 items: MinDepth:4, MaxDepth:5, TreeCount:43
Result for 8 items: MinDepth:4, MaxDepth:6, TreeCount:55
Result for 9 items: MinDepth:5, MaxDepth:6, TreeCount:75
Result for 10 items: MinDepth:5, MaxDepth:6, TreeCount:97
Result for 20 items: MinDepth:7, MaxDepth:9, TreeCount:657
Result for 30 items: MinDepth:9, MaxDepth:11, TreeCount:2111
Result for 40 items: MinDepth:10, MaxDepth:12, TreeCount:5045
Result for 50 items: MinDepth:11, MaxDepth:13, TreeCount:10017
Result for 100 items: MinDepth:14, MaxDepth:17, TreeCount:87999
Result for 200 items: MinDepth:17, MaxDepth:20, TreeCount:800839
Result for 500 items: MinDepth:22, MaxDepth:24, TreeCount:15498977
Result for 1000 items: MinDepth:25, MaxDepth:27, TreeCount:149747071
Result for 2000 items: MinDepth:28, MaxDepth:31, TreeCount:1444319497
Result for 5000 items: MinDepth:33, MaxDepth:35, TreeCount:28404978955
Result for 10000 items: MinDepth:36, MaxDepth:38, TreeCount:274868698129
Result for 20000 items: MinDepth:39, MaxDepth:41, TreeCount:2679840172029
Result for 50000 items: MinDepth:43, MaxDepth:46, TreeCount:53155392616903
Result for 100000 items: MinDepth:47, MaxDepth:49, TreeCount:509697594947469
Result for 1000000 items: MinDepth:58, MaxDepth:60, TreeCount:951117301279173505
Result for 10000000 items: MinDepth:68, MaxDepth:71, TreeCount:[REDACTED - overflow]
Result for 100000000 items: MinDepth:79, MaxDepth:82, TreeCount:[REDACTED - overflow]
A later run for 1000000000 items had MaxDepth:92 implying Bob can do it in 93 guesses.
With MinDepth and MaxDepth of the exhaustive tree search much closer, it is unlikely that any significant improvement can be made from this point. The search process directly confirmed optimality for various tested values of $n$ up to $10^7$, as all subtrees were verified to be of the same MaxDepth as a balanced tree whenever possible.
However, I'd be fascinated if anyone can post an answer with a decent mathematical justification for the latter optimisations that I discovered only empirically.
Looking at the numbers again, there seems to be a hint, as re-using the earlier simplification, the final formulation could be described as:
The median of a list where each number compatible with the last guess appears once, and each incompatible number appears $1+\phi$ times (or equivalently $\phi^2$ times), where $\phi = \frac{1+\sqrt5}2$ is the golden ratio. If so, a more precise "correct" factor for the code would be 0.190983..., with 0.191 "close enough" for all practical values of $n$.
The Fibonacci sequence would be relevant...
Final complexity analysis
Given that the final solution is (assumed) optimal, it has the same asymptotic behaviour in all branches of the game tree, so picking an easy branch to analyse:
[numbers $[1,2k]$ remain, none of which are incompatible with Alice's last response (if any)]
Bob: $k$
Alice: "lower"
Bob: [follows formula] $2k - \frac k2+\frac{k}{2\phi^2}$
Alice: "lower"
[numbers $[1,2k - \frac k2+\frac{k}{2\phi^2}]$ remain, none of which are incompatible with Alice's last response]
(in asymptotic case, ignoring the effect of excluding $k$ itself)
In two turns we've returned to a state equivalent to starting the game afresh with a lower value of $n$, the ratio between the starting count and ending count is
$\frac{2k}{2k - \frac k2+\frac{k}{2\phi^2}} = \frac{2}{2 - \frac 12+\frac{1}{2\phi^2}}$, so each turn the asymptotic average ratio between numbers remaining on consecutive turns is
$\sqrt{\frac2{2 - \frac 12+\frac{1}{2\phi^2}}}$ which simplifies to $\sqrt5-1$
Therefore the bounding log function is $\log_{\sqrt5-1}{n} \approx \log_{1.236}{n}$
