July 2003
—————————
In my July diary I posed the following brain-teaser:
Of two unknown integers, each between 2 and 99 inclusive, a person P is told the product and a person S is told the sum. When asked whether they know the two numbers, the following dialogue ensues:
P: "I don't know them."
S: "I knew that already."
P: "Then I now know the two numbers."
S: "Then I now know them, too."
What are the two numbers? Prove that your solution is unique.
—————————
Solution
This is an exceptionally elegant puzzle. You start by noticing that if the numbers were
two primes (7 and 11, for
example), then P would know them at once on being given the product (77). Since he begins by telling us he
doesn't know them, they are not
both primes.
Furthermore, none of the prime factors of either number can be bigger than 47. Why not? Well, consider a case where
one of them is; let's say,
it's 59. The smallest number this is a factor of is 59, the next smallest is 118, and so on. Since we have been told
that our unknown integers are
both between 2 and 99 inclusive, 59 must be one of the numbers. The other one must be the product, divided by 59.
P could work all this out
from just the product, once he'd spotted that factor 59. Since he didn't, there can't be any prime factor like
this —i.e. bigger than
50.
All that is deduced from just the first one of those statements — the statement, by P, that after
being given the product, he does
not know the numbers!
You might want to pick up the logic and work it from there. For a complete solution, see
Prof. Dijkstra's paper here.