Mr. S. and Mr. P.

Additional material

[ Editor: two variants with different dialogues. ]

[ Editor: Variant 1 (1996), posted by ronald ruegg
<102744.2436@CompuServe.com>: ]

> From among the positive integers, two numbers, not necessarily different
> and not greater than 100, were chosen.  The sum of those numbers was
> given to Mr. S and the product to Mr. P.  After returning to their
> homes, Mr. S called Mr. P on the phone and said, "I see no way you can
> determine my sum."  A short while afterwards, Mr. P called back to say,
> "I know your sum."  Some time later, Mr. S called Mr. P again and said,
> "Now I know your product."
>
> Which two numbers were chosen?

There is no unique answer in this variant, but four possible answers are:

    (1,4)
    (1,8)
    (7,8)
    (8,11)

By the way, I intended to say that this is a complete list of solutions
for the stated puzzle.

Dean Edmonds <deane@io.org> wrote:
> I agree that the answer is not unique, but how do you figure (1,4) being
> an answer? That would mean that Mr. P's product is 4 which could have been
> achieved as (1,4) or (2,2), making Mr. S's sum either 5 or 4. How could Mr. P
> know which it was? Similarly, (1,8) gives Mr. P a product of 9, which could
> also have been (3,3); (7,8)'s product is 56, which could also be (1,55),
> (2,28), etc.

You have to make the standard assumption for problems of this type;
you have to assume that Mr. S and Mr. P do not make any mistakes in
their reasoning and do not overlook anything.  Therefore, when Mr. S
says, "I can see no way you can determine my sum.", it really means
that there is no possible way that Mr. P can determine his sum.

This means that Mr. S's sum cannot possibly be 4, since (for all he
knows), Mr.  P's product could be 3, and in that case Mr. P would
already have deduced that the sum is 1+3 = 4.

Since Mr. P can rule out 4 as one of the sums Mr. S might have, he
knows that the product 4 must be 1*4, making the sum 5.

By the same token, (1,8) works because Mr. S's first statement allows
Mr. P to conclude that the sum cannot possibly be 6.

The (7,8) and (8,11) cases are more complicated.  Suffice it to say
that the other possibilities you mentioned (I think you meant (1,56)
rather than (1,55)) are not consistent with Mr. S's first statement.

> An example that works is (1,7). Mr. P's product is 7, which is prime, so
> he knows that the factors are (1,7) and that Mr. S's sum must therefore be 8.

Except that Mr. S would have to be lying or clueless to claim that "he
could see no possible way" for Mr. P to determine the sum.  Mr. P could
simply respond, "You're wrong.  I deduced your sum is 8 before you
called."

-- Dave Seaman <dseaman@purdue.edu>

[ Editor: in Edmonds's question, (1,8) has product 8, not 9; Seaman's
reply treats (1,8) as excluding the sum 6, i.e. the alternative (2,4)
with product 8. ]

[ Editor: Variant 2 (1997) was posed by PooSung Park
<sung@math.snu.ac.kr>.  Its full statement is not in the collected
material; it has a dialogue containing two "No, I don't know" answers,
and the questions were: ]

> 1) What are those two numbers? And unique?
>
> 2) This situation has two "No, I don't know".
>    How many "No" answers are possible in general?

[ Editor: Glenn Rhoads had answered: ]

> P's first statement implies that he has already ruled out all sums < 7.
> Thus for S's statement to help P, P's number can be factored into two
> numbers whose sum is 7.  2*5 is ruled out since P would have deduced the
> numbers immediately.  Thus, P's number factors into 3*4 which means
> that his number is 12.  12 factors into 2*6, sum=8,  and 3*4, sum=7.
> Since a sum of 7 has been ruled out, the numbers are 2 and 6.

[ Editor: Park replied: ]

> Ok. That's right. They are 2 and 6.
>
> But, how about the uniqueness?

The argument shows that this is the *only* possibility.

> > Since there is no limit on how big A and B could be, there is no limit
> > to the number of No answers preceding the "I know it response."
>
> That's not correct. There EXISTS the limit to the number of "No"
> answers.

Hmmn.  We have two NO responses. Suppose we have a third NO.
As above a yes means that the two numbers are 2 and 6, so a NO would
rule this out.

IF S said yes, then the above helped S.  This means S would have an
8.  3 and 5 were already ruled out; 2 and 6 were just ruled out so
the numbers would be 4 and 4.  A fourth NO by S rules out 4 and 4.

A yes by P would mean that he has a 16.  The only remaining possibility
is 2 and 8.  Thus a fifth NO rules out 2 and 8.

A yes by S would mean that he has a 10 and the only remaining possibility
is 4 and 6.  Thus a sixth NO rules out 4 and 6.

A yes by P would mean that he has a 24.  But there are two remaining
possibilities, 3/8 and 2/12.  Thus, P could not determine the numbers
and his only response is NO.  Any further statements do not eliminate
any remaining possibilities, thus both S and P will say NO forever.
I.e. there is no limit to the number of NO responses.

If you meant that the sequence of responses is finite and ends with a
yes, then the longest such sequence has 5 NOs. But the original
problem never said the sequence had to be finite.

-- Glenn C. Rhoads <rhoads@paul.rutgers.edu>

[ Editor: the range of the numbers in Park's version is not stated in
the collected material; Rhoads's reasoning implies that the numbers are
at least 2. ]

[ Editor: a variant with a different dialogue, rec.puzzles, June-July
  1994. ]

: There are 2 numbers, from 1 to 100 inclusive.
: There are 2 mathematicians.  M#1 knows the sum of the numbers, and
: M#2 knows the product.
: M#1 says "You can't possibly know the sum of these numbers" to which
: M#2 replies "well in that case I do" to which M#1 replies "Well in
: that case I know their product too."

-- (BRIAN6@vaxc.middlesex.ac.uk)

KOH KEW SOON <law20065@leonis.nus.sg> wrote:
>That's simple.  One of the numbers has got to be a prime number, eg. x,
>and the other number is 1.  So their sum is (x+1) and their product is
>x.  Mathn 2, knowing that the product is x, must realize that the two
>numbers have to be x and 1, and therefore work out the sum.  Mathn 1,
>given that, must realize that the numbers are x and 1.

I think you have misinterpreted the problem, though it may
be what the poser intended.  Suppose the numbers are 13 and 1.
The sum is 14.  How can M#1 say: "You can't **possibly** know the sum"
For all that M#1 knows, the numbers could be 13 and 1, in which case
the product will be 13 and M#2 will know the sum (without M#1
telling him anything)

The above reasoning in fact leads to a unique answer: 1 and 4

The sum of the numbers is 5.  M#1 thinks: "If the numbers are 2 and 3,
the product is 6, so M#2 cannot know whether the sum is 6+1=7
or 2+3=5.  If the numbers are 1 and 4, the product is 4, so
M#2 cannot know whether the sum is 1+4=5 or 2+2=4."
Hence, M#1 makes his statement.

Now, the product of the numbers is 4.  M#2 thinks: "If the
numbers were 2 and 2, the sum would be 4.  In that case, M#1
would not be able to rule out the possibility that the numbers
are 1 and 3, and hence he would not be able to make his
statement.  So the numbers cannot be 2 and 2.  Hence they must
be 1 and 4."
Thus he deduces the sum (and the numbers too), and makes
his statement.

M#1 now thinks: "If the numbers were 2 and 3, M#2 could not
have reasoned as in the above paragraph and made his statement.
In fact, the product would be 6, giving two possible sums of
5 and 7, in either case, I could not have made my statement, so
M#2 would have called me a liar!  So the numbers cannot be 2 and 3,
they must be 1 and 4."
Thus he deduces the product (and the numbers too), and makes
his second statement.

Note that if you consider larger numbers (like sum = 7) then
there are so many possibilities that M#2 cannot rule them all
out save one.  At least that's how it seems to me; I would
be happy to see another solution.

-- Vinay Gupta <gupta@cs.unc.edu>

This problem was published by Martin Gardner in MATHEMATICAL GAMES
in Scientific American Dec 1979.  He called it the impossible problem
and in the same issue gave the answers.  Mr S has 17 = 4+13, Mr P has
52=4x13.  The range was stated as numbers greater than one, and upper
bound of 20.  If Mr P has 52 it is easy to see that 52 is unique and so
he knows the answer without any help from Mr S.
If the range is increased then there is 2X26 to consider.  For this
Gardner uses Goldbach conjecture.  So that 2x26 cannot be used.
This is a defective problem.  One is obligated I believe to give
a least upper bound.  Other wise one can say like the small band
that they sold less than a million records and in fact way less.
I have a copy of that SA issue.

-- Joe Ascoly <ascoly@freenet3.scri.fsu.edu>

The following problem (if I have it right) was previously posted to
rec.puzzles:

Two integers in the range {1, 2, ..., 100}, not necessarily distinct,
are selected.  Mr. P knows their product but not their sum.  Ms. S
knows their sum but not their product.

  Ms. S: "You don't know the sum."
  Mr. P: "I do now."
  Ms. S: "Then I know the product."

What are the two numbers?

The problem does not have a unique solution.  Vinay Gupta has shown
here that the numbers could be 1 and 4.  However, 1 and 8 would also
serve.

WARNING! Very boring analysis follows.  You'd be better of to just
take my word it. {:-)

Call a sum "good" if it allows Ms. S her first statement, "bad"
otherwise.  A straightforward way to determine if a sum is good is to
examine the products of all pairs of numbers which yield the sum to
see if each product can be factored in more than one way into
factors which are in the range 1 - 100.

For example, the sum 9 must be 1 + 8, 2 + 7, 3 + 6, or 4 + 5.  The
corresponding products are 8 = 1*8 = 2*4, 14 = 2*7 = 1*14,
18 = 3*6 = 2*9, and 20 = 4*5 = 2*10.  So 9 is a good sum.  But 6 is a
bad sum because 6 = 1 + 5 and 1*5 = can only be factored in one way.

If you have the patience, check for yourself that the numbers
9, 11, 15, and 21 are all good sums.

Suppose now that our sum is 9 -- a good sum.  Then our numbers are
1 & 8, 2 & 7, 3 & 6, or 4 & 5.  Ms. S makes her first statement and
knows that the product is 8, 14, 18, or 20.

If the product is 20 Mr. P sees 1 + 20 = 21, and 4 + 5 = 9 among
the possible sums; since 9 and 21 are both good sums he is unable to
deduce the sum.  If the product is 18, possible sums include
2 + 9 = 11, and 3 + 6 = 9; again two good sums.  If the product is
14, the good sums 1 + 14 = 15 and 2 + 7 = 9 are each possible.

BUT if the product is 8 then the possible sums are 1 + 8 = 9 and
2 + 4 = 6.  Now Mr. P can eliminate the bad sum 6 and deduce the
sum to be 9.  Since 8 is the only product of the 4 original
possibilities which allow such a deduction, Ms. S can now make
her second deduction.

I have not checked to see if there are other solutions besides
(1,4) and (1,8).

-- Barry Paul <barry.paul@hofbbs.com>

People who've seen this one make the rounds a few dozen times
on rec.puzzles might nevertheless be interested in the
following:

1.  The same problem, but with one person given the sum and
    the other given the sum of squares, no upper bound
    on the numbers, and 3 iterations of mutual "I don't know"'s before
    they both know the numbers.  This one was in the American
    Mathematical Monthly problems section in the early 1980's, and has
    (if memory serves) a unique solution which is more conceptual
    than the one for sum and product.  (I might be wrong about the
    number of iterations; for those who want to look up the precise
    problem statement using the annual indices to AMM, I think the
    problem was proposed and solved by T. Ferguson at UCLA).

2.  V. Austin, "A Calculus for Know/Don't Know Problems", Mathematics
    Magazine, sometime in 1970's.  This article gives a method for
    analyzing this type of puzzle systematically, and uses it on some
    interesting example problems including one by Conway.

-- Tal Kubo <kubo@zariski.harvard.edu>

[ Editor: three further postings: Dave Seaman on the [1,100] variant
and Gardner's version (June 1994), PooSung Park on his "No/Yes" variant
(November 1994), and Jeff Kenton's explanation of the program given
above (April 1997). ]

In article <2ut1vp$f6o@freenet3.scri.fsu.edu> ascoly@freenet3.scri.fsu.edu
(Joe Ascoly) writes:
>This problem was published by Martin Gardner in MATHEMATICAL GAMES
>in Scientific American Dec 1979. He called it the impossible problem
>and in the same issue gave the answers. Mr S has 17 = 4+13, Mr P has
>52=4x13. The range was stated as numbers greater than one, and upper bound
>of 20. [...]

The (4,13) solution is for a different problem, namely the one in which
the numbers are chosen from 2 to 100 inclusive.  Actually, it works for
the case [2,n], where n > 61.  A second solution (4,61) emerges for
n > 865, and there are additional solutions for still larger bounds.

In the stated problem, the case [1,100], it is true that M#1 (knowing
the sum to be 17) would be able to conclude that M#2 does not know the
sum.  However, there is no possible product that M#2 could have that
would allow him to deduce the sum on the basis of that statement.  In
particular, if the product is 52, then for all he knows the sum might
be 1+52 = 53.  This would not be a possibility if the numbers were
constrained to be greater than 1.

There are in fact four possible solutions to the [1,100] case, which
may be easily verified by computer: (1,4), (1,8), (7,8), and (8,11).

Incidentally, the [2,20] case has no solutions at all.  I don't remember
whether this was the version that Martin Gardner analyzed, but I think
he did have to publish a correction when his answer was shown to be
wrong.  In general, the [2,n] case has no solution if n < 62.  In
particular, if M#2 knows that the product is 52 and if he also knows
that the original numbers are between 2 and 20, inclusive, then he can
immediately deduce that the numbers must be 4 and 13.  They can't be
(2,26) or (1,52), because both factors are required to be in the range
[2,20].  Therefore M#1 cannot make the first statement attributed to him
if the sum is 17, and therefore (4,13) is not a solution to the [2,20]
case.

-- Dave Seaman <ags@seaman.cc.purdue.edu>

[ Editor: PooSung Park, replying in a thread "What are two numbers?" to
a posting by the archive maintainer that compared Park's puzzle with
the one above: ]

Alas...  I have known that puzzle which Chris wrote.  But this puzzle
is an invention of mine though it seems similar.  So I have been
concerned about such confusion as Chris'.

The answer for each case of the number of "No" is as following:

    No,  Yes, Yes : 3, 4
    No,  No,  Yes, Yes : 2, 6  <-------------- in my puzzle
    No,  No,  No,  Yes, Yes : 4, 4
    No,  No,  No,  No,  Yes, Yes : 2, 8
    No,  No,  No,  No,  No,  Yes, Yes : 4, 6

But unhappily these variations doesn't advance any more.

Hmmm...

My poor English is an obstacle to the detailed explanation. :-(

By the way, the number of "No" may be up to five, but if the number is
more than five, then they, P and S cannot find two numbers.

But the versions for three numbers which are more than 1 or two numbers
which are more than 2 are also possible.

-- ps park (Seoul Univ.) <surd@apollo.hanyang.ac.kr>

Dev Mukherjee <dev@us.ibm.com> writes:
>OK - I give in.  I can't work through the solution for the Mr.S and Mr.P
>problem from the 'c' code.  Can anyone help?

I wrote the program that's in the FAQ.  Here's what is going on.

First, there are 3 levels of puzzle here.  We need to separate them.

  1. There are P and S, who are given the Product and Sum of two numbers
     in some range (they know what the range is).
  2. There is someone (you?) listening to them who does not know the
     Product or Sum, but can figure out the Product and Sum, and the two
     numbers, by listening to what they say.
  3. There is the larger question of what ranges of numbers are possible
     for the person in 2, above, to discover a unique solution without
     hearing the Product and Sum.

Let's pick a specific range for the numbers, from 2 to 100, and try to
solve the problem without knowing the Product and Sum.

First, we know from the range we chose that the Sum is between 4 and
200, and the Product is between 4 and 10,000 (inclusive).

<<Statement 1>>   Mr. P.:  I do not know the two numbers.
This tells us that the Product can be factored in at least two ways
using numbers from the range 2 - 100.

        for(i = 0; i <= 100 * 100; ++i)
                P[i] = 0;

        for(i = 2; i <= 100; ++i)
                for(j = i; j <= 100; ++j)
                        ++P[i * j];

At this point, each entry in array P will count how many different ways
each possible product (from 4 to 10,000) can be factored by numbers in
our range.

<<2>>   Mr. S.:  I knew that you didn't know the two numbers.
This is a more interesting statement.  This says that for the particular
Sum that S has been told, he has calculated all possible pairs of
numbers in the range that add to his Sum, multiplied each pair, and
determined that, in no case, do any of his pairs produce a product that
can be uniquely factored.

        for(i = 2 + 2; i <= 100 + 100; ++i) {

                for(j = i / 2; j >= 2; --j)
                        if(P[j * (i - j)] < 2)
                                break;

                S[i] = j;
        }

At this point, we have gone through each possible Sum, and all the pairs
of numbers that can produce those sums, and checked to see if there is a
unique factorization for any of those pairs.  If S[i] = j has the value
of 1 for any Sum, then we have checked all pairs for that Sum, and it
satisfies Statement 2.  So, Mr S has one of the numbers for which
S[i] = 1.  It is interesting to have the program print these out at
this point:
         11 17 23 27 29 35 37 41 47 53
are the only possible Sums.

<<3>>   Mr. P.:  Now I know the two numbers.
Mr P has looked at the pairs of factors of his Product and found only
one factorization which adds up to one of the numbers in the list above.

        for(i = 2 + 2; i <= 100 + 100; ++i)
                if(S[i] == 1)
                        for(j = i / 2; j >= 2; --j)
                                if(P[j * (i - j)] > 1)
                                        P[j * (i - j)] += 1000;

We have added 1000 to each possible product whose factors add up to one
of the Sums in the list above.  Any product which has had 1000 added
exactly once could be the Product.

<<4>>   Mr. S.:  Now I know the two numbers.
Finally.  And so will we.  Look through the possible sums in our list,
and see which one can be split into only one pair that satisfied step
3, above.

        for(i = 2 + 2; i <= 100 + 100; ++i)
                if(S[i] == 1)
                        for(j = i / 2; j >= 2; --j)
                                if(P[j * (i - j)] / 1000 == 1)
                                        S[i] += 1000;

If S[i] == 1001, it solves the problem.

-- Jeff Kenton <jkenton@world.std.com>