13
$\begingroup$

A 2-player game depends on two positive integers n and k known in advance to both participants. Albert has a secret number from 1 to n. Bob asks Albert a sequence of "yes" or "no" questions about the secret number, which may depend on answers received previously. Albert may lie or tell truth however he wants, but he cannot lie more than k times in a row.

Bob's goal is to find a number m from 1 to n that he knows with absolute certainty is not Albert's secret number. He makes a statement "your number is not m", where m is some integer from 1 to n. If this statement is accurate, Bob wins, else Albert wins.

Prove that if n=1025, and k=10, then Bob has a winning strategy.

$\endgroup$
3
  • $\begingroup$ I'd be interested in a follow-up to this, for what each player's optimal strategy and chances of winning would be for $k+1 < n \leq 2^k$, either (a) when Albert's secret number is fixed in advance, or (b) when after Bob guesses, Albert can decide on any secret number that's consistent with the answers he's given. $\endgroup$ Sep 19, 2022 at 4:46
  • $\begingroup$ Given this this puzzle requires us to prove that the secret number is not some value the answer will be the same if albert chan change his choice. $\endgroup$
    – Jasen
    Sep 19, 2022 at 6:18
  • $\begingroup$ I found a strategy that will work 99.9% of the time... $\endgroup$
    – caPNCApn
    Sep 23, 2022 at 22:30

3 Answers 3

15
$\begingroup$

How about this:

First, Bob asks "Is your number 1025?" until he gets a "yes" answer, or until he gets 11 "no" answers. If Bob gets 11 "no" answers, then he can say "The number is not 1025."
Otherwise, he asks "Does the binary expansion of your number have a 1 in the _s place?" for each power of 2 from 1 to 1024. Bob then says "Your number is not (number from 1 to 1024 which is inconsistent with every answer Albert gave about the binary expansion)."

This method works for $n > 2^k$.

$\endgroup$
7
  • 2
    $\begingroup$ Is your number 1025? yes, no, yes, no, yes, no $\endgroup$
    – manish ma
    Sep 18, 2022 at 0:32
  • 3
    $\begingroup$ If his first answer to "Is your number 1025?" is yes, I go onto the second part immediately. $\endgroup$ Sep 18, 2022 at 0:50
  • $\begingroup$ Thanks for explaining, can you give an example please? Let's say my number is 1024. I lied to your first question and said my number is 1025. $\endgroup$
    – manish ma
    Sep 18, 2022 at 6:50
  • $\begingroup$ My next questions would be "Does the binary expansion of your number have a 1 in the 1's position?", "... in the 2's position?", "... in the 4's position?", and so on. $\endgroup$ Sep 18, 2022 at 11:49
  • 2
    $\begingroup$ @AndrewSavinykh That it's not 1024. $\endgroup$ Sep 19, 2022 at 4:38
7
$\begingroup$

This is very much the same as the top voted answer. However, it may not be immediately obvious why the method with the binary expansion questions always works, so here's the same solution reworded to avoid (nearly) all the maths.

To start, we force an answer of "YES, the secret number is 1025". To do this, we ask "is the secret number 1025" repeatedly until the answer is a YES. We are guaranteed to get a YES by the eleventh time, because 11 consecutive NOs would allow us to win by claiming "well, then the secret number really isn't 1025".

Then, we'll force 10 consecutive denials about some single number. We don't care at all, which number it will be, and neither will we care if the answers are true or false, just that all the answers are denials.

We can do this in many equivalent ways, but let's use a deck of 1024 cards numbered 1 to 1024, which we will split in two equal halves each time, and ask: "Is the secret number on a card in this half?". After we get an answer, we choose the half for which the answer indicates the secret number is not in, discard the other half, and repeat.

We initially have 1024 cards, so we can play this game for exactly 10 rounds, always keeping the half the answer says the secret number is not in, until there's only a single card left. (1024 -> 512 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1)

Once we have arrived at the final card, we can claim "the secret number is not the number on this card", and we will be correct: we now have 11 consecutive answers saying it's not that number: one saying the secret number is 1025 (which is not on any card), and ten answers saying the secret number is not the number on this card in particular.

Since lying 11 times in a row is forbidden by the rules, at least one of those answers must be true.

And yes, this is exactly what @ralphmerridew does with the binary representations, although their approach is way more concise and optimised for maths aficionados to understand.

$\endgroup$
-4
$\begingroup$

This appears to require a hybrid of the answers previously suggested.

Ask "Is your number 1025?" eleven times, or until Albert says yes, whichever comes first.

If Albert says no eleven times, then they must all be true (otherwise Albert lied eleven times in a row, contradiction). So Bob says "Your number is not 1025."

If Albert says yes, then Bob moves on to part two:

"Is your number a number from 1 to 1024 whose first binary digit is 1?"

"Is your number a number from 1 to 1024 whose second binary digit is 1?"

and so on. Now let x be the number from 1 to 1024 that disagrees with all of Albert's answers in part two. If x was Albert's number, then Albert lied eleven times in a row (once at the end of part one, then ten more times in part two) (contradiction). So Bob says "Your number is not x."

$\endgroup$
2
  • 10
    $\begingroup$ This isn't a hybrid, it's just the same as the top answer $\endgroup$ Sep 18, 2022 at 2:42
  • $\begingroup$ Ugh, yeah, pretty sure I misread that one. There's a slight difference in the answers to the second set of questions if the number is 1025, but I suspect the general approach is valid regardless. $\endgroup$
    – Ed Murphy
    Sep 18, 2022 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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