339 logic/number.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
339 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 =
= jkenton@world.std.com =
-------------------------------------------------------------------------
Continue to:
My Books
