This is a similar but harder version of 6 Tries to Guess a Number Between 1-100.

You friend gives you $n$ tries to guess an integer $x$, $1\le x\le 100$. Your guesses must be of the following type:

Is $x$ greater than $k$?

Where $k$ is an integer. However, your friend will give you an answer to your question only after a delay of a question. A illustration of how this game would play in practice:

You: Is $x$ greater than 30?
Friend: ...
You: Is $x$ greater than 60?
Friend: $x$ is greater than 30.
You: Is $x$ greater than 75?
Friend: $x$ is not greater than 60.
etc.

Your last guess would never be answered.

What is the minimal number of moves $n$ to ensure you know the number your friend is thinking of, and what is the optimal strategy? Note that you don't have to specifically state $x$ as a guess.

up vote 11 down vote accepted

I can do it in 11 guesses.

Let's generalize the range of numbers to be $N$ (instead of 100). I'll give a solution that lets you figure out $N$ in a number of guesses $g$ that's asymptotically

$$ g = \log_{\phi}N +1 = \log_2 N/ \log_2(\phi)+1 \approx 1.44 \log_2 N + 1$$

where $\phi$ is the golden ratio $1.618...$. Compare this to $\log_2 N$ for the standard guessing game, and $2 \log_2 N$ for the simple modified strategy where you make each guess twice to get around the time delay.

Start by making a guess that splits the $N$ possible values into parts of size $pN$ and $qN$, for fractions $p+q=1$ that we'll optimize later. For now, think of them as roughly $p \approx 1/3, q \approx 2/3$.

Now, you don't get the answer until you make another guess. Let call this situation the good state, where you're waiting on an answer that splits your interval into $p,q$ fractions. Now, you make a guess that splits the larger interval of size $qN$ into intervals of size $pqN$ and $q^2N$.

There's two possibilities.

  • If the previous guess tells you the number is in the $qN$-size interval, you're now back in the good state, but with an interval of size $qN$.

  • If it tells you the number is to the $pN$-size interval, your current guess is moot, which we call a bad state, but the number is narrowed down to a smaller interval. But, just as when the game started, we'll make a guess that splits the interval into $p,q$-fractions, putting us in the good state of size $pN$.

So, we see that once we're in a good state with interval size $N$, we return to a good state of size

  • $qN$ in one turns
  • $pN$ in two turns

So, from a good state, every two turns decrease your interval size by an amount that's either $q^2$ or $p$. We get the best worst-case behavior if they are equal, and since $p=1-q$, we can solve

$$q^2=1-q$$

to get the inverse of the golden ratio

$$q = \frac{-1+\sqrt{5}}{2} = 1/\phi \approx 0.618$$

Since a guess is needed to get from the initial bad state to a good state, after $g$ guesses, the size of the interval is

$$N/\phi^{g-1}.$$

So, it takes $g = \log_{\phi}N+1$ guess to get down to an interval of size 1.

So far, I've been pretending you can guess real numbers that are no necessarily integers. But that's fine, since one can always asks the for integers that it implies (Whether $x \geq 10$ for whether $x > 9.63\dots$), and pretend it's an answer to your question. The valid integers are contained in your interval, so once you get down to an interval of size $1$, it can only contain one integer and you're done.

This give $g \approx 10.57$ for $N=100$, so 11 guesses suffice. Compare this to 14 guesses for the naive strategy.

  • Should $$N/\phi^{k-1}.$$ be $$N/\phi^{g-1}.$$? That seems to make sense to me... – Chris Jan 15 '15 at 10:23
  • 1
    @Chris Yup, thanks, fixed it. – xnor Jan 15 '15 at 10:26
  • "So, from a good state, every two..." two turns can also take you to a bad state of size pqN. – Taemyr Jan 15 '15 at 12:50
  • @Taemyr That's fine, the interval is still smaller than $q^2 N$, and it will be $q^3N$ next turn. – xnor Jan 15 '15 at 22:05
  • 1
    For the guessing game with delay=0, 2^k is the largest N that guarantees that the answer will be determined in at most k questions. For the guessing game with delay=1, Fibonacci(k+1) is the largest N that guarantees that the answer will be determined in at most k questions. Wouldn't it be fascinating to generalize it further in terms of delay? – witzar Feb 6 '15 at 22:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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