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.

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: