The game Alice invented on her own is known as the (single lie) Rényi-Ulam game. Much material from this problem was originally adapted from the article Robert B. Ellis, Vadim Ponomarenko, Catherine H. Yan: How to Play the One-Lie Rényi-Ulam Game, available on-line at http://math.iit.edu/~rellis/papers/9how.pdf The paper is not too explicit in classifying all positions, this solution provides a (hopefully) cleaner and more concise classification.
First, we will describe the game in a more mathematical way. According to the problem statement, Peter was allowed to ask any yes/no question about the number he tries to guess. Formally, each such question can be represented as the set of numbers, for which Alice would answer “yes”. For example, if N = 5, both the question “Is your number odd?” and “Is your number 1 or 3?” can be represented as the set {1,3}.
Peter wins if at some point in the game there is only a single number such that at most one answer does not match it.
When measuring how many questions Peter needs in the worst case, it is helpful to think about the game in terms of an adversary argument. Alice will not have the number fixed at the beginning of the game. Instead, whenever both her answers are still valid (i.e., leave at least one possible number), she picks the answer that will force Peter to make more questions.
In other words, we can restate the game as follows: Suppose that Peter asked a question that can be represented by a set Q. Alice now can decide whether to assign a token (representing a lie) to each of the numbers in Q, or to all the other numbers. Numbers that still have less than two tokens are candidates for Alice’s number. Thus Peter wins at the moment when there is only one such number left.
Reducing the state space
Consider the following two situations:
Clearly, the minimum number of additional questions is the same in both cases. We don’t care about the actual values of the candidates. To represent a position in the game all we need are two integers – the count of numbers that match all answers, and the count of numbers that match all answers except for a single one.
For example, both situations above can be described as (1,4).
Similarly, when Peter makes a question, all that matters is how many numbers of each kind are in the corresponding set.
For example, in situation B above, the question “Is it 0, 1, or 7?” can be represented as (1,1), and the question “Is it 2, 3, or 4?” as (0,3).
What happens if we are in a situation (a,b) and Peter asks a question (c,d)? Should Alice answer “Yes”, we would have:
That means that the new situation is (c,a - c + d).
Should she answer “No”, using a similar analysis we can deduce that the new situation will be (a - c,c + b - d).
Note that if (c,d) is different from (0,0) and (a,b), Alice’s answer will surely give us some new information about the numbers.
Searching the state space
Let Count(a,b) be the smallest number of questions Peter needs in the situation (a,b). We can now make the following simple observation:
| Count(a,b) | = 1 + min(c,d)max Count(c,a - c + d), Count(a - c,c + b - d) | (1) |
where the minimum is taken over all valid questions (c,d) – that is, 0 ≤ c ≤ a, 0 ≤ d ≤ b, and (c,d) is neither (0,0) nor (a,b).
In words: After Peter makes his question, Alice considers both possible situations and answers so that Peter gets the one where he will need more additional questions. Now, Peter can consider all possible questions and pick the one where he’ll get to the best situation.
Thanks to the above recurrence (with terminating condition Count(1,0) = Count(0,1) = 0) we can easily compute the values Count(a,b) for small a, b using either dynamic programming, or recursion with memoization.
This approach was sufficient to solve the easy data set.
Introducing a weight function
To handle the larger inputs, we will consider a problem that will turn out to be slightly simpler: “Given the values a and b, and a limit q on the number of questions, is there a winning strategy for Peter?”
A good tool in analyzing questions such as this one is to assign a weight to each position, and to define the weight in such a way that each Peter’s move splits the weight between the two new possible positions.
As a formula, what we need is the following property to hold:
| weight(q, a, b) | = weight(q - 1, c, a - c + d) + weight(q - 1, a - c, c + b - d) | (2) |
It is not hard to find a suitable definition for the weight function. Probably the simplest one that works in this case is the function weight(q,a,b) = (q + 1)a + b. In words, if we are in a situation that is q questions away from the end of the game, each perfect match has weight q + 1, and each other candidate has weight 1.
Note that the situations where Peter has no questions left and won (0 questions and either (1,0) or (0,1)) both have weight 1.
We will now prove an important observation:
If weight(q,a,b) > 2q, Peter can not solve the situation (a,b) in q questions.
Proof: In each step the weight of the situation becomes split between the two possible new situations. Remember that Alice is the one who gets to choose one of the two situations. One possible strategy for her is to always pick the situation with a larger weight. In this way, the new weight is at least one half of the original weight. Thus after q questions the weight will still be larger than one.
The converse is not true. The problem lies in the fact that even if weight(q,a,b) ≤ 2q, Peter might not be able to find a question (c,d) that splits the weight evenly enough. For example, for q = 4 and the situation (3,1) the weight is exactly 16, but no valid question can split it into 8+8.
We will show that a slightly weaker result is true. We will show one optimal strategy for Peter that will always split the weight of the current position as evenly as possible.
Our universal question
In the situation (a,b) with a + b > 1 we can compute Peter’s question (c,d) as follows: Let q be the smallest integer such that weight(q,a,b) ≤ 2q.
If a is even, take (c,d) = 
a∕2,⌊b∕2⌋
. If a is odd, take (c,d) = 
⌈a∕2⌉,max
0,⌈(b + 1 - q)∕2⌉
.
We claim that one possible optimal strategy for Peter is to repeatedly ask this universal question until the game is over. We will now make an even stronger claim.
Computing the optimal number of questions
Consider a situation (a,b) with a + b > 1. Let q, c, and d be values for our universal question.
If each of the two situations we can get after Alice’s answer has weight less or equal to 2q-1, Peter can win from (a,b) in q questions, but not in q - 1. Otherwise, Peter can win in q + 1 questions, but not in q.
Proofs
Once we trust the claim from the previous section, we are done – given a situation, we just compute the universal question and check the weights for the two new situations we get.
What remains is to prove the claim. We will do this using several simpler lemmas.
Lemma 1. For q ≤ 9 our formula always computes the optimal number of questions, and one strategy how to achieve this number of questions is to repeatedly ask the universal question.
This is easily proved by letting a simple program (similar to the one used for the easy input file) check all positions solvable in less than 9 questions.
Lemma 2. Let q ≥ 2 be the smallest integer such that weight(q,a,b) ≤ 2q. Then weight(q,a,b) > 2q-1.
Obviously, weight(q,a,b) ≥ weight(q - 1,a,b). If weight(q,a,b) ≤ 2q-1, then also weight(q - 1,a,b) ≤ 2q-1, which would contradict the minimality of q.
Lemma 3. For q ≥ 9 if we ask the universal question and Alice answers, the new situation will have b ≥ q - 2.
From the position (a,b), after a question (c,d), the two possible new positions are (a1,b1) = (c,a-c + d) and (a2,b2) = (a - c,c + b - d).
In the universal question, we always have c = ⌈a∕2⌉. Thus b1 = a - c + d ≥ a - c = ⌊a∕2⌋ and b2 = c + b - d ≥ c = ⌈a∕2⌉.
If a ≥ 2(q - 2), then ⌊a∕2⌋≥ (q - 2), and thus both b1 and b2 are at least q - 2.
Otherwise, we’ll use Lemma 2. We have a(q + 1) + b > 2q-1 and a < 2(q - 2). It follows that b > 2q-1 - 2(q - 2)(q + 1).
Note that 2q-1 is exponential in q, and thus grows faster than the negative polynomial term. For example, it can easily be proved that for q ≥ 9 we have 2q-1 - 2(q - 2)(q + 1) > 3q + 3.
For b > 3q + 3 the value ⌈(b + 1 - q)∕2⌉ is positive. Thus either d = ⌊b∕2⌋, or d = ⌈(b + 1 - q)∕2⌉. In both cases, both b1 and b2 are at least ⌈(b - 1 - q)∕2⌉ > q - 1.
Lemma 4. The universal question splits the weight as evenly as possible. In the case that q ≥ 9 and (either a is even or b ≥ q - 2), this split is perfect – Alice gets to choose between two situations whose weights differ by at most one.
This lemma explains how our question was chosen.
If a is even, the universal question splits the “heavy” candidates (those that match all questions so far) evenly, and then the “light” candidates as evenly as possible.
If a is odd, we can’t split the “heavy” candidates evenly. The best we can do is to take c = ⌈a∕2⌉. We can now compute d so that the weights for the two new situations differ by at most 1. We get d = ⌈(b + 1 - q)∕2⌉.
For b ≥ q - 2, this d will be non-negative, and thus (c,d) will be a valid question. In the other case (a odd and b small) there is no perfect question, and obviously no other question is closer to the optimal split than (c,0).
Theorem 1. Consider a situation (a,b) with a + b > 1. Let q, c, and d be values for our universal question.
If each of the two situations we can get after Alice’s answer has weight less or equal to 2q-1, Peter can win from (a,b) in q questions, but not in q - 1. Otherwise, Peter can win in q + 1 questions, but not in q.
From Lemma 1 we know that Theorem 1 holds for q ≤ 9.
From minimality of q we get that weight(q - 1,a,b) > 2q-1, and thus Peter can not win in less than q questions.
From Lemma 4 we know that the universal question splits weight as evenly as possible. If one of the two new situations has weight more than 2q-1, this means that this will be the case for all other questions as well. Alice will pick the heavier situation, thus forcing Peter to use at least q + 1 questions.
All we need to show now is that Peter can win in q questions in the good case, and in q + 1 questions in the bad one.
From Lemma 3 we get that after the first question we will have b ≥ q - 2. In the good case, we will have weight(q - 1,a,b) ≤ 2q-1. In the bad case, we will still have weight(q,a,b) ≤ 2q as before.
In either case, Lemma 4 tells us that in such a situation the next universal question will make a perfect split, and Lemma 3 tells us that after the question b will once again be large enough. Thus we can repeat the entire process until we get to q = 9. Then it follows from Lemma 1 that Peter can win the game in 9 more questions.