14
$\begingroup$

I've been trying to solve this riddle:

Say I'm thinking of a number between 1 and 100. You can ask me 10 distinct yes/no questions to guess the number, but exactly one of my answers will be a lie and I won't tell you which one.

How can this be done?

$\endgroup$
  • 1
    $\begingroup$ If the questions don't have to be yes/no, then just ask "what is the number + n" 10 times. The question is only interesting if you restrict it to yes/no. $\endgroup$ – DanielV Dec 30 '17 at 13:24
  • 1
    $\begingroup$ I'm gonna guess that you are misreading the question you were given. The whole "you can't use LEM" is probably meant to say, "Is the number greater than 50" "No" Then you can't infer that it is less than 50 (LEM) because you don't know if that answer was a lie. It probably doesn't mean you can't use LEM in general (what a nonsensical thing to say), just that you can't assume a binary yes/no because that could have been the question that was the lie. $\endgroup$ – DanielV Dec 30 '17 at 13:58
  • 4
    $\begingroup$ This is going to need an unusually efficient coding. Once the questioner's strategy (i.e. the rule for which question to ask at which point, given earlier answers) is fixed, there are 10 different patterns of answers we can get for each of the 100 numbers, meaning we need to recognize 1000 answer patterns in total. That is very close to the $2^{10}=1024$ different answer patterns that are possible to give. So, for example, the strategy must be such that in most cases we'll guess wrong if it turns out all ten answers were honest. $\endgroup$ – Henning Makholm Dec 30 '17 at 14:21
  • 1
    $\begingroup$ Also, I'm able to get up to 64 without a hash function. $\endgroup$ – PyRulez Dec 31 '17 at 4:08
  • 1
    $\begingroup$ Here is a non-adaptive strategy for 72 (found by greedy search) pastebin.com/kebm2CPp $\endgroup$ – tehtmi Jan 1 '18 at 4:37
9
$\begingroup$

We can do it by brute force, assuming that

  • which questions we ask can depend on the answers to earlier questions, and
  • it is okay to ask "artless" questions of the form "is it one of 1, 5, 7, 16, 17, 18, 37, 57, 72, 73, 98?"

We can imagine that our opponent starts by choosing both which number he's thinking of and when in the game he's going to lie, combining into a sample space of $100\times 10=1000$ outcomes. At the end we will know both parts of the outcome. This does not make the problem harder: if we have a strategy that produces the secret number, we'll be able to deduce the lie-position too simply by comparing the answers to what they should have been.

At each point in the strategy, let's say that there are

  • $n$ questions left to ask,
  • $m$ numbers that the opponent can be thinking of if they have not yet lied (each of these numbers represent multiple outcomes),
  • $s$ numbers that the opponent can be thinking of if they have lied exactly once (each of these represents a single outcome).

This means that there are $nm+s$ different outcomes still in play. In order to be sure of winning we need to maintain the invariant that $nm+s\le 2^n$. This is certainly true -- but only just barely -- in the initial state where $n=10$, $m=100$, $s=0$.

Actually, let's be generous and allow the opponent to think of $101, 102, \ldots, 124$, but in that case he will not lie. (We don't need to tell him that's an option, but it makes the strategy slightly easier to describe if we imagine this is the case). This gives an initial state of $n=10$, $m=100$, $s=24$, and we can then keep the invariant as $$ nm+s = 2^n $$ exactly.

An initial observation is that each of the 100 (124) possible numbers can count among the $m$ or among the $s$ (or neither), but not both. This means that we have freedom to tailor our question such that what they do to the $m$ numbers is chosen independently of what they do to the $s$ numbers.

Now, the easy case first: If $m$ is even, then we ask a question about half of the $m$ numbers, and half of the $s$ numbers. No matter whether the answer is yes or no, we're now in a situation where $$ m_{\rm new} = m/2 \qquad s_{\rm new} = s/2 + m/2 $$ which exactly cuts $nm+s$ in half: $$ (n-1)m_{\rm new} + s_{\rm new} = nm/2 - m/2 + s/2 + m/2 = \frac{nm+s}2 $$

The case where $m$ is odd is slightly more involved. Then we can't ask any question that cuts $m$ in half. Let's split it as evenly as we can and ask a question that mentions $\frac{m+1}2$ of them. Then in the "yes" case we end up with $ m_{\rm new} = m/2 + \tfrac 12 $, which contributes more than before to the $(n-1)m_{\rm new}$ term, so we need to ask about correspondingly fewer than $s/2$ of the single outcomes in order to maintain the $mn+s=2^n$ invariant.

Can we do that, however? The risk is that $s$ is so small that we cannot split it unevenly enough to correct for the uneven split of $m$. If we ask about $x$ of the $s$ numbers, we get $$ s_{\rm new} = x + (m-m_{\rm new}) $$ and so we can solve for $x$ to find $$ (n-1)m_{\rm new} + s_{\rm new} = \frac{nm+s}2 \iff x = \frac{s-n+2}2 $$ This will automatically be an integer (given that $m$ was odd, $s=2^n-mn$ will have the same parity as $n$), but it also needs to be non-negative, which is the case iff $s\ge n-2$.

Is there a risk that $s<n-2$? This can only happen if $m$ is $\lfloor 2^n/n\rfloor$ -- but the smallest $n$ for which that number is odd is $12$ (the next are $18$ and $25$), so that case cannot possibly arise here where $n$ starts out at $10$.

So the strategy will work.


This generalizes to problems of the form

Ask $n$ questions to guess one of $m$ numbers, given that the opponent lies exactly once.

Clearly it is a necessary condition for this to be solvable that $nm\le 2^n$. The smallest case where this (and the above strategy) is not sufficient is $n=12, m=341$, where we see from the analysis above that no matter which question we ask first, either "yes" or "no" will lead us to having too many possible outcomes in the next step.

If we manage to ask the first question, though, the fact that $s$ gets a new contribution of about half of $m$ at each step means that we will never again have to worry about $s$ being too small.


Still unsolved: Is it possible to get through if we have to ask all our questions simultaneously without seeing any answers (and the questions cannot explicitly refer to which answers are provided for other questions or where the lie is)?

Intuitively I doubt it; that would need an extremely efficient packing of groups of 10 points in the 10-dimensional hypercube of possible answer sequences.

$\endgroup$
0
$\begingroup$

This variant variant has gained some attention in the comments and in other answers. I think it will shed some light on the original question, so I'll give an answer here.

Is it possible to get through if we have to ask all our questions simultaneously without seeing any answers (and the questions cannot explicitly refer to which answers are provided for other questions or where the lie is)?

The answer is that we can only do this if out of $80$ possible numbers, $100$ is too much. So any strategy to the original question must adapt the questions according to the answers we have got.


Essentially, all our questions are "Is the number in the set $S_i$?" for $i=1,2,\dots,10$, and we choose the sets $S_i$ before knowing the answers to these questions. For each number in $1,\dots,100$, we create a binary codeword where the $i$th symbol tells whether the number is in the set $S_i$. When we write down the answers, we get another binary word, and since there is exactly one lie, we know that the word differs from the codeword of the correct answer in exactly 1 position.

(In what remains, the distance between two codewords is the number of positions in which they differ.)

So, our task is to find a set $C$ of codewords so that no binary word is at distance $1$ from two different codewords. This is equivalent to the condition that no two codewords have distance exactly $2$.

We can split the set $C$ to two parts, $C_e$ containin all codewords with even number of $1$s, and $C_o$ containing all codewords with odd number of $1$s. No codeword in $C_e$ is at distance $2$ from a codeword in $C_o$, so what remains is to check the condition on $C_e$ and $C_o$ separately. In addition, the distance between two codewords in $C_e$ (and in $C_o$) is never odd. So the condition is that the minimum distance between two codewords in $C_e$ (and in $C_o$) is $4$.

The maximum size of a binary code of length $n$ and minimum distance $d$ is given by the coding-theoretic function $A(n,d)$. In particular, $A(10,4)=40$. So the maximum size for both $C_e$ and $C_o$ is $40$. Therefore, $|C|\leq 80$. The bound can be reached by taking a binary code of length $9$ and minimum distance $3$ with $40$ codewords, and creating two codewords from each codeword by adding both a $0$ and a $1$ at the end. Here is an example.

$\endgroup$
-1
$\begingroup$

For each $n$ from 1 to 10 ask "Is Sha-512(your number|n) even?" Now, for each of the number $z$ from 1 to 100 and each $n$ from 1 to 10, check if Sha256(z|n) is even. When $z$ is your number, it will match your answers in exactly 9 cases. Other numbers will match for on average 5 numbers, since Sha-512 models a random oracle.

$\endgroup$
  • 2
    $\begingroup$ Even though the average number of correct responses for each of the 99 wrong answers is only 5, the expected number of false "9 rights" matches in addition to the right answer should be $99\binom{10}{9}2^{-10}=0.97$. $\endgroup$ – Henning Makholm Dec 31 '17 at 4:44
  • 2
    $\begingroup$ For a random oracle, the probability that there will be only one of the 100 numbers that match exactly 9 of the answers is only 38%. $\endgroup$ – Henning Makholm Dec 31 '17 at 4:52
  • $\begingroup$ @HenningMakholm well, it is only a guess. $\endgroup$ – PyRulez Dec 31 '17 at 19:54
  • 1
    $\begingroup$ Also remember the birthday paradox: the chance that all 100 numbers get distinct correct answer sequences is less than 1%. $\endgroup$ – Henning Makholm Jan 1 '18 at 16:44

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.