greg@uwvax.UUCP (06/20/83)
Here is a solution to the problem posed by "ark" a few weeks ago.
The problem statement is repeated below. By the way, was this
problem presented and discussed in Mathematical Games? If so,
what issues of Scientific American? Do people have any other
references on the problem? Thanks.
I have picked two integers between 3 and 100 (inclusive),
and given their sum to Sally and their product to Paul,
both very clever mathematicians.
After suitable time for thought, Sally says to Paul:
"It is impossible for you to figure out my sum."
After more time for thought, Paul replies:
"I have figured out your sum."
After still more thought, Sally says:
"I have figured out your product."
What are the two numbers?
Solution:
The numbers are 13 and 16. An explanation follows.
Number of possible pairs of numbers the moderator may have picked:
4851. ( n*(n+1)/2, for n=98)
possible sums before given any additional information: 195, in the
range 6 .. 200. Call this set PosSum0.
Possible products before given any additional information: 2854, in
the range 9 .. 10000. (calculated by a computer program, as are the
other sets in this solution.) Call this set PosProd0.
We learn the following facts:
1) Paul does not know the numbers. (We learn this from Sally's first
statement.) This would not be true if Paul's product could be
uniquely factored into integers in the range [ 3 .. 100 ]. So, the
product must be a number N with the property that there is more than
one pair of integers x, y in [ 3 .. 100 ] (ignoring reflections)
with x*y = N. Call this set of products PosProd1. PosProd1
contains 1068 elements, and its first and last few members are:
{ 24, 30, 36, ... 7644, 7920, 8100 }
2) By looking at the sum, Sally can tell Paul does not know the
numbers. This means that the sum must be a number N with the
property that no matter how one forms a sum x+y = N, x, y in [ 3 ..
100 ], x*y is in PosProd1. This limits the sum to the set { 13, 19,
25, 29, 31, 37, 43, 49, 53, 55 }. Call this set PosSum1.
3) That Sally is able to make her inference tells Paul what the sum
is. That Sally can tell Paul does not know the numbers is in effect
telling Paul, "My sum is in the set { 13, .. 55 } (i.e. PosSum1)."
Paul can then use this information to determine the numbers. That
Paul can do this tells us that his product is a number N with the
property that of the various ways to factor it into terms x and y,
exactly one sum x+y is in PosSum1. There are 88 elements of
PosProd1 with this property. Let us call this set PosProd2. The
first and last few elements of PosProd2 are:
{ 30, 36, 40, ... 750, 754, 756 }
4) That Paul is able to make his inference tells Sally what the product
is. By guessing the numbers, Paul effectively tells Sally, "My
product is in the set PosProd2." This limits the possible sums to a
single number: 29. 29 is the only element of PosSum1 with the
property that of the various ways to break it up into addends x and
y, exactly one product x*y is in PosProd2.
5) We can now duplicate Sally's reasoning, and infer from the sum and
PosProd2 what the product must be: 208. (13, 16) is the only pair
of numbers both in the set [ 3 .. 100 ] whose sum is 29 and whose
product is in PosProd2.
- Greg Johnson
U. Wisc. - Madisonntt@dciem.UUCP (07/28/83)
Repeating the problem statement again:
--------------------------------------------
I have picked two integers between 3 and 100 (inclusive),
and given their sum to Sally and their product to Paul,
both very clever mathematicians.
After suitable time for thought, Sally says to Paul:
"It is impossible for you to figure out my sum."
After more time for thought, Paul replies:
"I have figured out your sum."
After still more thought, Sally says:
"I have figured out your product."
What are the two numbers?
--------------------------------------------
This was printed in Martin Gardner's Mathematical Games in the December 1979
Sci.Am., but with the upper bound changed to 20. A solution was given in the
same column as 4 and 13. In March 1980, MG printed a correction to the effect
that since the two mathematicians use the upper bound in their computations,
the solution is not independent of it; 4 and 13, he said, is correct for an
upper bound of 100, which is how the problem was originally proposed, while
there is no solution for an upper bound of 20. In May 1980 he gave solutions
for various other upper bounds.
According to the March column, the problem was originally proposed by one
David J. Sproule in Mathematics Magazine, March 1976 (vol 49 #2), page 96,
and a correct solution printed there, November 1977 (vol 50 #5), page 268.
Mark Brader, NTT Systems Inc.