Aug
30
Here is an interesting puzzle that was posted to one of the discussion groups at work.
A teacher tells two students that he is thinking of two natural numbers greater than 1. He tells the first student the product of the two numbers and the second one their sum. The students then have the following dialog:
First: I do not know their sum.
Second: I knew that. Their sum is less than 14.
First: I knew that, and now I know the numbers.
Second: So do I.
What were the numbers and how did they figure them out?
Solution
Let’s say that the two numbers that the teacher is thinking of are a and b. Lets say that the product a*b = n and the sum a+b = m.
When the first student gets the product n, it is fair to assume that he tries to factor n to find out the two numbers. There may be multiple ways of factoring n into two integers greater than 1 so we can assume he finds all such pairs.
When the second student gets the sum m, he tries to find all integer pairs {i,j} such that i+j = m.
Both students have their lists of candidate pairs before they start their conversation. We can now step through their statements.
First student says: ” I do not know their sum”
Remember that the first student has the product n and has determined all pairs {i,j} such that i*j=n. If he cannot find the sum, this implies that there are multiple ways of factoring n into two integers. Otherwise, if there was only one way of factoring n into two, he would have a single pair {i,j} and would be able to determine the sum.
If n cannot be factored uniquely into two numbers, then the target numbers a and b cannot both be prime (maybe one or zero of them is prime). Otherwise, if a and b were both prime, then there would only be one way of factoring n into two.
Second student says: “I knew that the first student could not know the sum”
Recall that second student has the sum m and has enumerated all pairs {i,j} such that i+j = m. Since he has these pairs, he can calculate all the possible products of i*j and this will help him know what kind of info the first student has.
When the first student says that he cannot uniquely determine the sum, it confirms what second knew. In second student’s list of pairs {i,j} , there is no pair such that, given the product, you can uniquely identify the sum.
The only way that second student could have known for sure that the first student could not determine the sum is if on the list of pairs that second student has, there is no pair {i,j} such that both i and j are prime.
In other words, m is an integer that cannot be created by adding two primes.
Second student says: The sum is less than 14
This tells us that 1 < m < 14. From the previous section , we also know that m cannot be created by adding two primes. This tells us that m = 11.
The derivation is as follows:
m is in the set {2,3,4,5,6,7,8,9,10,11,12,13}
2 is out because the only {i,j} such that i+j = 2 is {1,1} and we know that both candidate numbers are greater than 1.
3 is out because the only {i,j} s.t. i+j=3 is {1,2}
4 is out because it can be created by 2+2 where 2 is prime
5 is out. It can be created by 2+3
6 is out. It can be created by 3+3
7 is out. It can be created by 2+5
8 is out. It can be created by 3+5
9 is out. It can be created by 2+7
10 is out. It can be created by 3+7
12 is out. It can be created by 5+7
13 is out. It can be created by 2+11
First student says: “I knew that the sum m < 14”
Remember that the first student has the product n and has determined all pairs {i,j} such that i*j=n. Since he has the pairs, he has also summed them and he knows for sure that for all {i,j}, i+j <14.
In other words, n is an integer that can be factored into two in multiple ways but however you do it, the two numbers you end up with always add up to less than 14.
This is the final piece. The final derivation is as follows:
We know that i and j are both numbers in {2,3,4,5,6,7,8,9,10,11,12,13} (i.e. neither i nor j can be greater than 14)
We can enumerate all pairs {i,j} such that i+j < 14
{22,3,4,5,6,7,8,9,10,11}
{33,4,5,6,7,8,9,10}
{44,5,6,7,8,9}
{55,6,7,8}
{66,7}
Where the notation {xy,z} is shorthand for the pairs “the pairs where the smaller number is x and the larger is either y or z” (i.e. {x,y} and {x,z})
We can then eliminate all pairs where i and j are both prime. This leaves.
{24,6,8,9,10}
{34,6,8,9,10}
{44,5,6,7,8,9}
{56,8}
{66,7}
Consider the products of pairs i*j

4 
5 
6 
7 
8 
9 
10 
2 
8 

12 

16 
18 
20 
3 
12 

18 

24 
27 
30 
4 
16 
20 
24 
28 
32 
36 

5 


30 

40 


6 


36 
42 



Eliminate all products that can be created by multiplying numbers that add up to >=14. This eliminates 24, 28, 30, 32, 36, 40 and 42 because :
36 = 18*2, and 18+2>14
30 = 15*2, and 15+2 > 14
24 = 12*2, and 12+2 = 14
28 = 14*2
42=21*2
32=16*2
40=20*2
This gives us the grid:

4 
5 
6 
8 
9 
10 
2 
8 

12 
16 
18 
20 
3 
12 

18 

27 

4 
16 
20 




Which gives the pairs
{24,6,8,9,10}
{34,6,9}
{44,5}
We already know that i+j = 11. Looking at our pairs, we determine that the answer is {2,9}