Guessing a number between $1$ and $100$ with 10 distinct questions and 9 honest answers

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?

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.