8
$\begingroup$

The rain was still falling and Alice and Bob were terribly bored of having to stay inside the caravan, so they decided to play a game. The game is that Alice chooses a number $x$ in the interval [1,n] (where Bob knows n), and Bob tries to guess x. For each of Bob's guesses, Alice tells Bob if his guess is greater than, lesser than, or equal to $x$.

They figured that this game was quite boring. Alice decided to start lying and Bob started losing, and he got annoyed. They changed the rules again such that Alice couldn't lie twice in a row. Also, she had to tell the truth when her number is guessed correctly. Alice's number was not fixed at the start, but her answers are chosen in such a way that there is always at least one integer $x$ which is consistent with her statements (either truths or lies).

Bob could ask every number, but wants to guess fast and prove that he is smart.

What is Bob's optimal stategy, and how long would it take him?

Just to clarify rules:

  • Alice has an integer x
  • Bob does not know x, so Alice can theoretically change x as long as it fits with her answers.
  • x is in the inclusive interval [1,n]
  • Bob knows n
  • Bob guesses a number g
  • Alice says x < g, x > g, or x = g
  • Alice can lie according to the following rules:
    • Alice cannot lie twice in a row
    • Alice cannot say "x > g" or "x < g" when x = g
    • Alice cannot say "x = g" when x < g or x > g
  • Bob is trying to guess x in as few guesses as possible

I could solve this riddle when Alice lies once by having Bob ask Alice every question thrice and takes the majority one, as she could lie only once. But I could not solve the original one. Any help will be appreciated.

$\endgroup$
  • 2
    $\begingroup$ Suppose that x is 3, Bob asks x < 5? Alice lies and says no. Then Bob asks x < 5 again. Alice cannot lie twice, she must say yes. But no number is consistent with both answers given to Bob. So the problem has no general solution. (Or I didn't fully understand the question) $\endgroup$ – Florian F Jun 8 at 14:42
  • 5
    $\begingroup$ Interesting choice of opening line here ;-) $\endgroup$ – Stiv Jun 8 at 14:47
  • 2
    $\begingroup$ I saw "Alice and Bob" and my head started hurting lol. $\endgroup$ – Ankit Jun 8 at 16:20
  • 2
    $\begingroup$ This exact question is from an ongoing contest, which ends on 15th June: codechef.com/JUNE20B/problems/GUESSG. It would be very helpful if the community refrains from discussing the solution of this problem till the 15th, so as to maintain fairness of the contest. We would also request the answers posted till now to be removed and re-published once the contest ends. $\endgroup$ – CodeChef Jun 10 at 13:31
  • 1
    $\begingroup$ I’m voting to close this question because it's from an ongoing contest as stated by @CodeChef above. $\endgroup$ – Rand al'Thor Jun 10 at 18:24
2
$\begingroup$

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}$

| improve this answer | |
$\endgroup$
  • $\begingroup$ The solution of brute forcing everything was already mentioned in the puzzle and it specifically says "Bob could ask every number, but wants to guess fast and prove that he is smart." Your second solution doesn't consider the fact that it could be a lie truth, truth lie, or truth truth. (If I am wrong about this please correct me, I will remove my vote.) Hence the downvote. $\endgroup$ – Ankit Jun 9 at 18:33
  • $\begingroup$ @hexomino that is a great question that I think should be asked in the main comment thread. My guess is that she can't lie about that because then the game would end. $\endgroup$ – Ankit Jun 9 at 18:41
  • $\begingroup$ @Ankit the point is that Bob specifically picks a number to guess that would make Alice's last response a lie - Alice cannot possibly give two truths in a row (w.r.t. the numbers Bob is trying to eliminate) based on Bob's guesses. For the numbers where Alice's response would be two truths in a row, Bob is still considering those in the $t_i$ set. $\endgroup$ – Steve Jun 10 at 7:20
  • $\begingroup$ Current "final" version of code referred to in my answer can be found at pastebin.com/F8J9FGZf $\endgroup$ – Steve Jun 23 at 15:45
0
$\begingroup$

Disclaimer: This was completely independently created. I do use a tercile (3-way) split, like @Steve, but my answer and explanation is a bit different and more thorough. If you feel they are too similar, please do give him some credit as well.

For the sake of this post, the 1st tercile is 1/3 way through the set and the 2nd tercile is 2/3 way through. This can also be called T1 and T2. It is different than a third. The first third is between 0 and T1, etc. I will call the first third t1, the middle third t2 and the final third t3. When I say "<", I mean x < g. When I say ">", I mean x > g. T means truth, L means lie.

The answer: The game can always won by Bob in at most

3*roundUp(logbase1.5(n))+9 moves (this formula isn't perfect, it is often less but never more)
For 100 it would take 24 guesses max.

... much less than just the trivial brute force guessing.

Reasoning (aka the strategy Bob should use):

Assuming that Alice plays optimally, 1/3 of the current set of possible answers can be shaved off after 3 questions. This is done by asking for T1 and then T2 twice. Doing this will remove 1/3 of the options as shown by the following diagram:
enter image description here
*** I say to ask T2 a third time but this is unnessecary as this will give t2 & t3 or t2.

Once there are 9 or less possible answers, Bob should just start guessing one by one.

| improve this answer | |
$\endgroup$
  • $\begingroup$ What happens when the result is >T1, <T2, >T2? If it is LTL, the result is t1, if it is TTL, the result is t2, if it is TLT, the result is t3. $\endgroup$ – justhalf Jun 10 at 7:55
  • $\begingroup$ @justhalf if Alice answers >T1, <T2, >T2, you can remove t1, as if you ask for T2 again, Alice can not possibly say the answer is in t1. This is shown in my picture as another line of questioning. $\endgroup$ – Ankit Jun 10 at 16:02
  • $\begingroup$ I don't get your explanation yet. If >T1 is a lie, and <T2 is truth, and >T2 is a lie, then the truths are: <T1, <T2, and <T2, which is consistent with t1, right? $\endgroup$ – justhalf Jun 26 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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