Two students $ A$ and $ B$ are playing the following game: Each of them writes down on a sheet of paper a positive integer and gives the sheet to the referee. The referee writes down on a blackboard two integers, one of which is the sum of the integers written by the players. After that, the referee asks student $ A:$ “Can you tell the integer written by the other student?” If A answers “no,” the referee puts the same question to student $ B.$ If $ B$ answers “no,” the referee puts the question back to $ A,$ and so on. Assume that both students are intelligent and truthful. Prove that after a finite number of questions, one of the students will answer “yes.”
Problem
Source: IMO ShortList 1991, Problem 30 (BUL 3)
Tags: algebra, game, game strategy, combinatorics, IMO Shortlist
iTAQ
18.08.2008 19:23
I'm confused... If no one knows the other number, how can this kind of question show the answer?
MellowMelon
19.08.2008 01:40
Example: Suppose $ A$ picked $ 4$, $ B$ picked $ 2$, and the referee wrote down $ 6$ and $ 8$. $ A$ says he doesn't know, because $ B$ could have picked $ 2$ or $ 4$. $ B$ says he knows, because he knows $ A$ had to pick $ 2$ or $ 6$, and $ A$ would have known if he picked $ 6$.
xxp2000
28.11.2008 06:39
Let the two numbers on blackboard be $ X<Y$. Also use $ A$ and $ B$ to represent the number from students A and B, respectively. (1) Suppose no "yes" in round 1. A knows $ B<X$, otherwise B would have said "yes" and solve $ A=Y-B$. Similarly B knows $ A<X$. (2) Suppose no "yes" in round 2. If B saw $ Y-B>=X$, he would have known $ A$ could not be $ Y-B$ since he knew $ A<X$ and then he would have said "yes' by solving $ A=X-B$. Hence, A knows $ Y-B<X$, or $ B>Y-X$. Similarly B knows $ A>Y-X$. (3) Suppose no "yes" in round 3. A knows $ B<2X-Y$. B knows $ A<2X-Y$. ... Each round without "yes" will tighten A's knowledge on B, also B's knowledge on A. Here knowledge means both upper bound and lower bound. Let us call the series of upper bounds $ x_n$ and lower bounds $ y_n$. We see that $ x_{n+1}=X-y_n$ and $ y_{n+1}=Y-x_n$. Obviously $ x_n$ are strictly decreasing and $ y_n$ are strictly increasing. So in a finite number of rounds, A or B have to answer yes. The stopping rule is one of the following four: (i) $ X-A<x_n\leq Y-A$, A say yes and solve $ B=X-A$. (ii) $ X-A\leq y_n<Y-A$, A say yes and solve $ B=Y-A$. (iii) $ X-B<x_n\leq Y-B$, B say yes and solve $ A=X-B$. (ii) $ X-B\leq y_n<Y-B$, B say yes and solve $ A=Y-B$.
demetre
25.09.2019 18:35
Suppose $A$'s number is $a$, $B$'s number is $b$, and the two numbers on the board are $r_1 < r_2$. Suppose $A$ and $B$ both keep saying $``$no.$"$ Each person always has two guesses as to what the other person's number is. $A$ knows that $b$ must either be $r_1-a$ or $r_2-a$. Likewise, $B$ knows that $a$ must either be $r_1-b$ or $r_2-b$. Meanwhile, at every stage of the game, there are certain restrictions on what the value of $a$ and $b$ could be. For example, the only thing known initially is that $a,b > 0$. A person will answer $``$no$"$ if and only if both of his guesses satisfy the known restrictions at the given time. Suppose $\alpha_n$ denotes all the restrictions on $a$ after $A$ has said $``$no$"$ for the $n$th time, and likewise for $\beta_n$. Define $\alpha_0 = [a>0]$ and $\beta_0 = [b>0]$. When $A$ says $``$no$"$ for the $n$th time, he is saying $``$ I don't know which of my guesses, $r_1-a$ or $r_2-a$, is correct, since both of them satisfy $\beta_{n-1}$", and in saying this, he is conveying useful information about the value of $a$, which contributes to the restriction $\alpha_n$. Try this out for the first couple of times, and you'll see the following pattern for $n>0$: $\alpha_n = [(n-1)(r_2-r_1) < a < (n)(r_1-r_2) + r_2]$ $\beta_n = [(n)(r_2-r_1) < b < (n)(r_1-r_2) + r_2]$
First consider $n=1$.
When $A$ says $``$no$"$ for the first time, he is saying $``$both of my guesses satisfy $\beta_0 = [b>0]"$, or in other words, $r_1-a>0 \text{ and } r_2-a > 0$. Hence the restrictions on $a$ are now $[0<a<\text{min}(r_1,r_2)]$. Thus, it is verified that $\alpha_1 = [0<a<r_1]$ as required.
When $B$ says $``$no$"$ for the first time, he is saying $``$both of my guesses satisfy $\alpha_1"$, which conveys that $0<r_1-b<r_1$ and $0<r_2-b<r_1$. As before, this implies $0<b<r_1$, but the second inequality adds the restriction that $b>r_2-r_1$. Hence it is verified that $\beta_1 = [r_2-r_1 < b < r_1]$ as required.
Now for the induction.
When $A$ says $``$no$"$ for the $nth$ time, he is saying $``$both of my guesses satisfy $\beta_{n-1}"$. In other words, $[(n-1)(r_2-r_1) < r_1-a < (n-1)(r_1-r_2) + r_2]$ and $[(n-1)(r_2-r_1) < r_2-a < (n-1)(r_1-r_2) + r_2]$. The first halves of these inequalities taken together mean $[a<(n-1)(r_1-r_2) + \text{min}(r_1,r_2)]$ which gives $[a<(n)(r_1-r_2) + r_2]$. Meanwhile, the second halves taken together give $[a>(n-1)(r_2-r_1)]$. This gives the required value for $\alpha_{n}$.
When $B$ says $``$no$"$ for the $nth$ time, he is saying $``$both of my guesses satisfy $\alpha_n"$. In other words, $[(n-1)(r_2-r_1) < r_1-b < (n)(r_1-r_2) + r_2]$ and $[(n-1)(r_2-r_1) < r_2-b < (n)(r_1-r_2) + r_2]$. The first halves of these inequalities taken together mean $[b<(n-1)(r_1-r_2) + \text{min}(r_1,r_2)]$ which gives $[b<(n)(r_1-r_2) + r_2]$. Meanwhile, the second halves taken together give $[b>(n)(r_2-r_1)]$. This gives the required value for $\beta_n$.
Since $r_1<r_2$, it is clear that the bounds are shrinking in tighter and tighter, which cannot go on indefinitely. Hence, at some point, one must answer $``$yes$"$.