Does this process always terminate?

Question

Consider the following "game". Take two natural numbers $n \leq m$ and let $S=n+m$ and $P=nm$. Take two logicians A and B, and tell A the value of $S$ and B the value of $P$. Now, A and B alternate asking each other "Do you know what my number is?", starting with A asking B. It is assumed that A and B always answer truthfully (i.e., each one answers "no" if and only if they do not have enough information to figure out the other's number). The game ends once either player answers "yes". The question is: for what natural $n$ and $m$ does the game end?

This problem was suggested in an answer to a question I saw on MathOverflow regarding mathematics-based magic tricks. The MO user claimed (without proof) that the game always ends.

I conjecture that the game does not always terminate, e.g. for $n=3$ and $m=4$.

Edit: What if we assume n>1? In that case I think termination will always occur but I'm not sure why. In any case, how does the number of steps relate to the choice $n$ and $m$?

Further question (assuming there are some $n$ and $m$ for which the game does not end): Suppose we modify the game to allow a player to resign once he deduces that the game would otherwise go on forever. Does this new game always terminate?

Answer 1

I assume, this is a generalization to what is known as Impossible Puzzle. In this puzzle, it is assumed, that $m,n>1$ and that $A$ and $B$ know that.

If you require this, too, then $n=3$ and $m=4$ is not a contradiction:

• $A$ is told the sum $7$ and $B$ is told the product $12$.
• From $B$'s perspective, both the pairs $(3,4)$ and $(2,6)$ are possible, so he says "I don't know the numbers."
• From $A$'s perspective, $(2,5)$ and $(3,4)$ are possible solutions. In the first case $m\cdot n$ is a product of two primes. Since $B$ said, that he didn't know the numbers, $A$ concludes, that the numbers are $(3,4)$.

Answer 2

Perhaps consult:

Austin, A. K.; A Calculus for Know/Don't Know Problems. Math. Mag. 49 (1976), no. 1, 12–14.

edited

"Math. Mag." = "Mathematics Magazine" a publication intended for students of mathematics. Should be available at college libraries, and also JSTOR. See http://www.maa.org/pubs/mathmag.html