IMO 1991 SL 30

Origin: BUL

Problem

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.”

Solution

Let a and b be the integers written by A and B respectively, and let x < y be the two integers written by the referee. Suppose that none of A and B ever answers ”yes”. Initially, regardless of a, A knows that 0 \leqb \leqy and answers ”no”. In the second step, B knows that A obtained 0 \leqb \leqy, but if a were greater than x, A would know that a + b = y and would thus answer ”yes”. So B concludes 0 \leqa \leqx but answers ”no”. The process continues. Suppose that, in the n-th step, A knows that B obtained rn−1 \leqa \leqsn−1. If b > x −rn−1, B would know that a + b > x and hence a + b = y, while if b < y −sn−1, B would know that a + b < y, i.e. a + b = x: in both cases he would be able to guess a. However, B answered ”no”, from which A concludes y −sn−1 \leqb \leqx −rn−1. Put rn = y −sn−1 and sn = x −rn−1. Similarly, in the next step B knows that A obtained rn \leqb \leqsn and, since A answered ”no”, concludes y −sn \leqa \leqx −rn. Put rn+1 = y −sn and sn+1 = x −rn. Notice that in both cases si+1 −ri+1 = si −ri −(y −x). Since y −x > 0, there exists an m for which sm −rm < 0, a contradiction.