Four different integers from 1 to 10 are chosen. Sam is given the sum and Pat is given the product. Sam and Pat take turns stating how many of the four numbers they can deduce:

Sam: I don't know any
Pat: I know one
Sam: I now know two
Pat: I now know all four

What could the four numbers be?

Tip: A spreadsheet is very useful in solving this problem.

The solutions proposed until now doesn't fill the restrictions imposed by the problem; If it was:
1,10,5,2: the product is 100, and the only four different number with this product is 10,5,2,1. So, in the beginning Pat would know the 4 numbers. The same applies to 1, 10, 5, 4; 
1, 10, 5, 6: We have only two possibilities with the same product: 10,6,5,1 or 10, 5, 3, 2. In this case, Pat would know 2 number from beginning: 10 and 5.
A similar reasoning applies to 1, 10, 5, 8.

If it were 2, 8, 9, 10 with product 1440, the only possibilities are 10*9*8*2 or 9*8*5*4. In this case, Pat would know 2 numbers: 8 and 9.
The same reasoning applies to 4, 6, 9, 10.

Well, the solution:
1. We must consider that Sam is not capable to deduce the numbers from scratch, so, the sum cannot be the following values: 34 (10+9+8+7), 33 (10+9+8+6), 32 (10+9+*), 31 (10+*). Nothing more can we deduce at this point.

2. If Pat knows 1 number, it means that the factoring of the her product contains 7. If the greatest prime were 5, and we also have 2 in the factors, we could have 2 possible combinations containing 5: 5 and 10. The presence of 2 in the factors can be verified considering that the only 2 combinations without 2 are 7,5,3,1 and 9,7,5,1. In this cases Pat would know the solution in the first step. So, again, one number is surely 7.

3. Ok, the third step is a little tricky: Sam, from the Pat sentence knows that they have the number 7. And since she only knows 1 number, it means that the factoring of the number don't identify any other number. The combination 10,9,7,6 for example is not possible. The other important fact in the third sentence is that Sam is not capable to deduce all four numbers knowing that 7 is present. 

Well, we can make the procedure inverse of factoring and try to deduce combinations of numbers that would lead to doubts in the second and third step. One remarkable point is that this doubt could only arise for combination of little primes. Pairs of 5 (5*5) for example cannot appear. So, we can construct sequences like (1*2*2, 1*2*3, 1*2*2*2, 1*2*2*3, 1*2*2*5, 1*2*3*5, 1*2*2*2*2, 1*2*2*2*3, 1*2*2*2*5, etc). We can generate a list of possibilities, and this list is not to big. In this point is important the spreadsheet, since it will help us to discover the sum and product of possible combinations.
Well, after this list, considering the presence of 7, Sam have the possible sums:
15: the only possible doubt for Pat is 7*3*2*2*1 (generating numbers 7,6,2,1 or 7,4,3,1). In this case Pat would know 2 numbers (7 and 1) and Sam would know the 4 numbers in step 3.
16: With numbers 7,4,3,2 or 7,6,2,1. Let's us analyse:
7*4*3*2=168 that can also be 7,6,4,1 or 7,8,3,1.
7+4+3+2=16 and we have several possible combinations.
So, Sam is unable to know any number. But by factoring Pat know the presence of 7. And nothing more she can deduce based in the factoring.
Based in the sum 17, the presence of 7 and knowing that Pat knows only 1 factor, this is not the solutions, since she would know 2 numbers (1 and 7)....

17: only 1 possibility to Sam in step 3: 7,5,4,1.

and goes on....

But 20: Sam can deduce the following possible values based in Pat statement:
7,8,3,2 or 7,6,5,2. The factoring of this numbers cannot define any number besides 7:
7*8*3*2=336 that can also be 7,8,6,1 or 7,6,4,2
7*6*5*2=420 that can also be 10,7,6,1 or 7,6,5,2 or 10,7,3,2 or 7,5,4,3.
Based on this, Sam knows that they have the numbers 7 and 2.

Knowing this fact, Pat can deduce that Sam was between 7,8,3,2 or 7,6,5,2, and since she know the product, she will knows the 4 numbers.

So, the solutions is 7,8,3,2 or 7,6,5,2.

Posted by Rogerio on 2006-01-06 15:44:07