9
$\begingroup$

Q. Two students A and B think of a positive integer. They tell the teacher their positive integer, but they don't tell each other their positive integer.

The teacher tells both of them two different positive integers, and says that one integer is the sum of two integers by A and B.

(For example, if A thought of $3$ and B thought of $5$, The teacher would say $8$ and $9$, or $8$ and $4$, ...)

The teacher then asks student A, "Do you know which one is the sum?"

If A says "No", the teacher would ask B the same question.If B says "No", A need to answer the question again, and B and so on.

Prove that they can figure out the sum after enough questions asked.

$\endgroup$
15
$\begingroup$

Let $a$ and $b$ be the integers thought of by A and B, and let $N$ and $n$ be the integers given by the teacher, where $N>n$. Assume for contradiction that both A and B keep on saying "no" forever.

If $a\geq n$, then A knows $n$ cannot be the sum and will say "yes" the first time. Thus after A's first "no", B knows $a<n$.

If $b\leq N-n$, then $a+b<N$ (since $a<n$), so B knows $N$ cannot be the sum and will say "yes" the first time. Thus after B's first "no", A knows $b>N-n$.

If $a\geq 2n-N$, then $a+b>n$ (since $b>N-n$), so A knows $n$ cannot be the sum and A will say "yes" the second time. Thus after A's second "no", B knows $a<2n-N$.

If $b\leq 2N-2n$, then $a+b<N$ (since $a<2n-N$), so B knows $N$ cannot be the sum and will say "yes" the second time. Thus after B's second "no", A knows $b>2N-2n$.

If $a\geq 3n-2N$, then $a+b>n$ (since $b>2N-2n$), so A knows $n$ cannot be the sum and will say "yes" the third time. Thus after A's third "no", B knows $a<3n-2N$.

If $b\leq 3N-3n$, then $a+b<N$ (since $a<3n-2N$), so B knows $N$ cannot be the sum and will say "yes" the third time. Thus after B's third "no", A knows $b>3N-3n$.

By induction, this argument can be continued forever:

after B's $k$th "no", A always knows $b>k(N-n)$.

But $b$ cannot be greater than $k(N-n)$ for ALL $k$, so eventually B must say "yes" (unless A does first) and the game is up.

QED.

$\endgroup$

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.