puzzle of sum and product
Kermit Rose
comprehensive article on the following puzzle.
Mr S knows the sum of two positive integers.
Mr P knows the product of two positive integers.
Both S and P know that both integers are greater than 1, and not greater
than 100.
The following conversation takes place between S and P.
P: I do not know what the two numbers are.
S: I already knew that you did not.
P: Aha! Now I know what they are.
S: So! Now I know what they are also.
We would appreciate any info anyone has on this puzzle so that we may
consider it in our article.
Please reply directly to me as I do not get to this newsgroup very often.
Thank you.
ro...@garnet.acns.fsu.edu To be sure I see your response, use e-mail.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
You may post, repost, or publish ANY communication received from me.
Chris Cole
>Hello everyone. An internet friend (David Snook) and I wish to make a
>comprehensive article on the following puzzle.
>
>Mr S knows the sum of two positive integers.
>Mr P knows the product of two positive integers.
>
>Both S and P know that both integers are greater than 1, and not greater
>than 100.
>The following conversation takes place between S and P.
>
>P: I do not know what the two numbers are.
>S: I already knew that you did not.
>P: Aha! Now I know what they are.
>S: So! Now I know what they are also.
>
>We would appreciate any info anyone has on this puzzle so that we may
>consider it in our article.
>
>Please reply directly to me as I do not get to this newsgroup very often.
>
==> logic/number.p <==
Mr. S. and Mr. P. are both perfect logicians, being able to correctly deduce
any truth from any set of axioms. Two integers (not necessarily unique) are
somehow chosen such that each is within some specified range. Mr. S.
is given the sum of these two integers; Mr. P. is given the product of these
two integers. After receiving these numbers, the two logicians do not
have any communication at all except the following dialogue:
<<1>> Mr. P.: I do not know the two numbers.
<<2>> Mr. S.: I knew that you didn't know the two numbers.
<<3>> Mr. P.: Now I know the two numbers.
<<4>> Mr. S.: Now I know the two numbers.
Given that the above statements are absolutely truthful, what are the two
numbers?
==> logic/number.s <==
The answer depends upon the ranges from which the numbers are chosen.
The unique solution for the ranges [2,62] through [2,500+] is:
SUM PRODUCT X Y
17 52 4 13
The unique solution for the ranges [3,94] through [3,500+] is:
SUM PRODUCT X Y
29 208 13 16
There are no unique solutions for the ranges starting with 1,
and there are no solutions for ranges starting with numbers above 3.
A program to compute the possible pairs is included below.
#include <stdio.h>
/*
BEGINNING OF PROBLEM STATEMENT:
Mr. S. and Mr. P. are both perfect logicians, being able to correctly deduce
any truth from any set of axioms. Two integers (not necessarily unique) are
somehow chosen such that each is within some specified range. Mr. S.
is given the sum of these two integers; Mr. P. is given the product of these
two integers. After receiving these numbers, the two logicians do not
have any communication at all except the following dialogue:
<<1>> Mr. P.: I do not know the two numbers.
<<2>> Mr. S.: I knew that you didn't know the two numbers.
<<3>> Mr. P.: Now I know the two numbers.
<<4>> Mr. S.: Now I know the two numbers.
Given that the above statements are absolutely truthful, what are the two
numbers?
END OF PROBLEM STATEMENT
*/
#define SMALLEST_MIN 1
#define LARGEST_MIN 10
#define SMALLEST_MAX 50
#define LARGEST_MAX 500
long P[(LARGEST_MAX + 1) * (LARGEST_MAX + 1)]; /* products */
long S[(LARGEST_MAX + 1) + (LARGEST_MAX + 1)]; /* sums */
find(long min, long max)
{
long i, j;
/*
* count factorizations in P[]
* all P[n] > 1 satisfy <<1>>.
*/
for(i = 0; i <= max * max; ++i)
P[i] = 0;
for(i = min; i <= max; ++i)
for(j = i; j <= max; ++j)
++P[i * j];
/*
* decompose possible SUMs and check factorizations
* all S[n] == min - 1 satisfy <<2>>.
*/
for(i = min + min; i <= max + max; ++i) {
for(j = i / 2; j >= min; --j)
if(P[j * (i - j)] < 2)
break;
S[i] = j;
}
/*
* decompose SUMs which satisfy <<2>> and see which products
* they produce. All (P[n] / 1000 == 1) satisfy <<3>>.
*/
for(i = min + min; i <= max + max; ++i)
if(S[i] == min - 1)
for(j = i / 2; j >= min; --j)
if(P[j * (i - j)] > 1)
P[j * (i - j)] += 1000;
/*
* decompose SUMs which satisfy <<2>> again and see which products
* satisfy <<3>>. Any (S[n] == 999 + min) satisfies <<4>>
*/
for(i = min + min; i <= max + max; ++i)
if(S[i] == min - 1)
for(j = i / 2; j >= min; --j)
if(P[j * (i - j)] / 1000 == 1)
S[i] += 1000;
/*
* find the answer(s) and print them
*/
printf("[%d,%d]\n",min,max);
for(i = min + min; i <= max + max; ++i)
if(S[i] == 999 + min)
for(j = i / 2; j >= min; --j)
if(P[j * (i - j)] / 1000 == 1)
printf("{ %d %d }: S = %d, P = %d\n",
i - j, j, i, (i - j) * j);
}
main()
{
long min, max;
for (min = SMALLEST_MIN; min <= LARGEST_MIN; min ++)
for (max = SMALLEST_MAX; max <= LARGEST_MAX; max++)
find(min,max);
}
-------------------------------------------------------------------------
= Jeff Kenton (617) 894-4508 =
= jke...@world.std.com =
-------------------------------------------------------------------------
********************************************
Instructions for Accessing the rec.puzzles Archive
INTRODUCTION
The rec.puzzles Archive is a list of puzzles, categorized by subject
area. Each puzzle includes a solution, compiled from various sources,
which is supposed to be definitive.
To request a puzzle, send a message to archive...@questrel.com like:
return_address your_name@your_site.your_domain
send requested_puzzle_name
For example, if your net address is "mic...@disneyland.com", to request
"decision/allais.p", send the message:
return_address mic...@disneyland.com
send allais
To request the index, use:
send index
To request multiple puzzles, use several "send" lines in a message.
Please refrain from requesting the entire archive via email. Use FTP.
FTP
The entire archive is also accessible via anonymous FTP, from any site
which maintains archives of the newsgroups news.answers or
rec.answers. One such site is rtfm.mit.edu, where the archive is in
the directory /pub/usenet/news.answers/puzzles/archive. The file
part01 contains the index. The remaining files contain alternating
problem text and solution text for all the puzzles.
Some other anonymous FTP archives are:
Site IP address Directory Notes
---------------------------------------------------------------------
ftp.cs.ruu.nl 131.211.80.17 /pub/NEWS.ANSWERS [1]
ftp.uu.net 137.39.1.9 /usenet/news.answers
or 192.48.96.9
ftp.win.tue.nl 131.155.70.100 /pub/usenet/news.answers
grasp1.univ-lyon1.fr 134.214.100.25 /pub/faq [2]
---------------------------------------------------------------------
[1] Also accessible via mail server requests to mail-...@cs.ruu.nl.
[2] Also accessible via mail server requests to
list...@grasp1.univ-lyon1.fr. Best used by EASInet sites.
Note that the periodic posting archives on rtfm.mit.edu are also
accessible via Prospero and WAIS (the database name is "usenet" on
port 210).
THE rec.puzzles ORACLE
This is a group of rec.puzzles regulars, who are familiar with the
rec.puzzles archive, and who will find your answer there if it exists,
or maybe compose an original answer if they are interested enough!
At any rate, they promise to respond to your question within two days,
and perhaps save you the embarrassment of posting a well-worn
question. They will respond within two days even if they do not know
the answer to your question.
To query the rec.puzzles oracle, send email containing your question
to the following address:
Allan Adler
The form in which I heard and solved the problem was that S knew the
sum of the numbers and P knew the product. Also both numbers were
bigger than 1. The dialogue was:
Mr.S: I don't know the numbers.
Mr.P: I don't know either.
Mr.S: Oh, then I know.
Mr.P: Oh, then I know too.
The numbers are 3 and 4. Their sum is 7 = 3+4 = 2+5. So S doesn't
know the numbers. So he says, "I don't know".
The product is 12, which is also 2 x 6, so
P doesn't know the numbers. Furthermore, the fact that S doesn't
know the numbers contains no information for P, since both 3+4=7
and 2+6=8 would be numbers that would cause S to say he didn't know.
So P says, "I don't know".
However, S realizes that if the numbers were 2 and 5, then their product would
have only one possible factorization and S would not say he didn't know. So
S now knows that the numbers are 3 and 4. So he says, "Oh, now I know."
P on the other hand knows that if the numbers were 2 and 6 then
their sum would be 8 = 2+6 = 3+5 = 4+4. If S had the number 8, however,
S would know that the possible values of P would be 12, 15, 16, only
one of which has a unique factorization into numbers >1. So P knows that
if S had the number 8 and if S knew that P's number had nonunique
factorization, then S would not know whether P had the number 12 or 16,
hence S would not know the numbers and would not say that he did.
So the wily P concludes that the numbers are not 2 and 6, hence that
they are 3 and 4. So P says, "Oh, I know too".
Proving that this is the only solution took more work but turned out
to be a lot of fun in the end. I have the notes of my solution in
storage in the US, but I am sure the clever people on this group can
produce the proof right away.
Allan Adler
a...@altdorf.ai.mit.edu