This bio-recipe shows how to solve a puzzle in which certain pieces of information are given from which the reader has to discern two numbers. In solving the problem below, it is assumed that the people in the puzzle (Simona, Peter and Danielle) can solve any solvable problem instantaneously. The problem was originally found on the website Onlinewahn and is translated here into English. This solution was found by Gaston Gonnet, the biorecipe is from Gina Cannarozzi.
Peter, Simona and Danielle have to find out two numbers. They have the following information: both numbers are integers between 1 and 1000 and it is also possible that both numbers are identical. Peter knows only the product of the numbers, Simona the sum, and Danielle the difference of the two numbers. The following sequence of statements passes between them.
Peter: I don't know the numbers.
Simona: You didn't need to tell me that, I knew you didn't know the numbers.
Peter: Now I know the numbers then.
Simona: Now I also know them too.
Danielle: I don't know the numbers. I can only guess one number that is probably there but I don't know for certain.
Peter: I know what number you are thinking but it is wrong.
Danielle: OK, then now I also know both numbers.
The puzzle is: What are the two numbers?
The first piece of information is that Peter, who knows only the product, does not know the numbers. That means that any pair of numbers who have a unique product will be eliminated. In what cases will the product of two numbers be unique? 1) In the case that the numbers have a unique factorization i.e. the two numbers are 1 and a prime number. 2) It can be seen that with two numbers between 1 and 1000 there is only one way to have the product 1,000,000. Thus there are other numbers with a non-unique factorization that can be eliminated because some of the factors fall out of the range. It should also be noted that we only need to look at half of the pairs of this matrix i.e. There is no difference between the numbers being (i,j) vs being (j,i).
To avoid factoring 1,000,000 numbers we will build a table called 'factors' which will contain all of the ways to make each product for each pair of numbers. This table will contain a set of pairs which multiple to give the argument.
# Table of possible factors to avoid factoring
factors := table({}):
for n1 to 1000 do
for n2 from n1 to 1000 do
factors[n1*n2] := factors[n1*n2] union {[n1,n2]}
od;
od:
There are 1,000,000 possible products. We will start by enumerating all possible products and eliminating those products who can only be produced by one pair of numbers. We will use a boolean matrix p where p[i,j] is true if this combination is a candidate and false otherwise.
# p[n1,n2]=true means this combination is possible for Peter
p := CreateArray(1..1000,1..1000,false):
t1 := 0:
for n1 to 1000 do
for n2 from n1 to 1000 do
# Peter: I don't know the numbers.
if length(factors[n1*n2]) > 1 then
p[n1,n2] := true; t1 := t1+1
fi
od;
od:
We count the number of products that are not unique. These are the candidate pairs of numbers given the information that Peter does not know what the numbers are from their product. This number is held in the variable t1 and is 355777. With so many possible combinations, we can not examine them by hand. So we continue to the information that Simona gives us. If we take an example of factors[27720], we can see that there could be many combinations of two numbers which will have a given product.
factors[27720];
{[28, 990],[30, 924],[33, 840],[35, 792],[36, 770],[40, 693],[42, 660],[44, 630]
,[45, 616],[55, 504],[56, 495],[60, 462],[63, 440],[66, 420],[70, 396],[72, 385]
,[77, 360],[84, 330],[88, 315],[90, 308],[99, 280],[105, 264],[110, 252],[120,
231],[126, 220],[132, 210],[140, 198],[154, 180],[165, 168]}
In addition, 936,000 is the largest number for which the product is not unique. In summary, the first statement by Peter leaves a lot of ambiguity.
factors[936000];
{[936, 1000],[960, 975]}
Any product higher than 936000 has only 1 allowable set of factors and thus is eliminated.
Simona knows the sum of the two numbers. This sum must be between 2 and 2000. Simona says "You didn't need to tell me that, I knew you didn't know the numbers." From knowing the sum, Simona knows that Peter does not know the numbers from the product. This is a very strong statement. Peter can not have a product that has the possibility of a unique solution. For this to be true, there *has* to be ambiguity in every possible product of a given sum. This can not happen if the sum of the numbers is greater than 503, the first prime number after 500. In other words, this statement reduces the search to n1+n2 <= 503 as for any larger number, n1*503 (or a suitable prime larger than 503) will have a unique decomposition with the restrictions. Take for example, the case in which the sum of the numbers were 700. If the sum were 700, there is the possibility to choose 2 numbers with a factorization that is unambiguous-- 691 (the closest prime number below 700) and 9. 691 * 9 is the only possible decomposition of 6219 for which the numbers are in the range of 1 to 1000. Thus if these were the two numbers, there is no way to make the factorizaton unambiguous. Since Simona says she knows without doubt that Peter doesn't know the two numbers, the sum of 700 is not possible.
Here we make an array s that will be true if the sum is a possibility and false otherwise. It is not possible to have two integers between 1 and 1000 that sum to one so this element is false.
s := CreateArray(1..2000,true): s[1] := false:
For each sum we loop over the possible pairs of numbers that could form that sum. If any of these pairs is not a possibility for Peter, then the sum is excluded. Otherwise, Simona could not say with certainty that she knows that Peter does not know the numbers. In other words, we can strike from the solutions any sum for which one or more combinations of summands exist that would allow Peter to know the two numbers from the product. For example, if Simona sees a 20, it could be that Peter sees 19 which is the product of 1 and 19 (sum 20). In this case, Peter would know unambiguously the numbers and Simona could not know for certain that Peter did not know the numbers. Thus 20 is not a possibility.
for n1n2 from 2 to 2000 do
for n1 from max(1,n1n2-1000) to min(1000,n1n2/2) do
if not p[n1,n1n2-n1] then s[n1n2] := false; break fi
od
od:
Now we can count the possibilities after this step
t2 := sum( If(s[i],1,0), i=1..2000 );
t2 := 235
We see that the number of possible sums after this step is 235.
for i from 2000 by -1 to 1 while not s[i] do od: print(i);
503
If we then look backward from 2000, we see that indeed the largest sum that is a possible solution is 503, just as we anticipated.
Peter then says "Now I know the numbers." Peter knows the answer now (but we do not). We do know that any product with more than one possibility is out because Peter sees only one possibility.
for n1 to 1000 do
for n2 from n1 to 1000 do
if not p[n1,n2] then next fi; # if p[n1,n2] is false then skip
if sum( If(s[z[1]+z[2]],1,0), z=factors[n1*n2] ) <> 1 then
p[n1,n2] := false
fi;
od
od:
sum( sum( If(p[n1,n2],1,0), n2=n1..1000), n1=1..1000 );
26192
We have now eliminated more products. After this step, there are 26192 products that are still possible. This will also eliminate more possibilities for the possible sums.
Simona says "Now I know them too". Simona knows the numbers (but we do not). We can eliminate all sums that could come from more than one pair of numbers. If the pair comes from more than one pair of numbers, Simona would not know it.
# Simona: Now I know them too
for n1n2 from 2 to 2000 do
if sum( If(p[n1,n1n2-n1],1,0),
n1=max(1,n1n2-1000)..min(1000,n1n2/2) ) <> 1
then s[n1n2] := false fi
od:
t2 := sum( If(s[i],1,0), i=1..2000 );
t2 := 27
After this elimination there are 27 possible sums. We can use this reduction in the number of sums to reduce the number of products.
# This info is also useful for Peter
for n1 to 1000 do
for n2 from n1 to 1000 do
if not p[n1,n2] then next fi;
if sum( If(s[z[1]+z[2]],1,0), z=factors[n1*n2] ) <> 1 then
p[n1,n2] := false
fi;
od
od:
sum( sum( If(p[n1,n2],1,0), n2=n1..1000), n1=1..1000 );
116
Now there are only 116 possible products. We can run through this loop again to see if we eliminate more possibilities but at the end of this code, one can see that the number of possible sums and products is no longer reduced. This means that all possibilities satisfy all statements so far. We enumerate the possible products for Peter in p2, look at the factors for each of those products, see if the sum of any of the factors is a possibility for Simona.
# p2: set of possible products for Peter
p2 := []:
for n1 to 1000 do for n2 from n1 to 1000 do
if p[n1,n2] then p2 := append(p2,n1*n2) fi
od od:
length(p2); p2 := {op(p2)}: length(p2);
116 27
Then make a list of the candidate pairs.
cand := {}:
for pr in p2 do
c := {seq( If(s[z[1]+z[2]], z, NULL), z=factors[pr] )};
if length(c) <> 1 then error(failure) fi;
cand := cand union c
od:
At the end of this step there are 27 candidate pairs and they are:
length(cand); cand;
27
{[1, 4],[1, 8],[1, 9],[1, 15],[1, 32],[8, 31],[8, 89],[8, 101],[11, 16],[13, 32]
,[16, 37],[16, 43],[16, 61],[16, 73],[16, 97],[16, 103],[23, 32],[29, 32],[32,
41],[32, 53],[32, 71],[32, 101],[37, 64],[40, 109],[43, 64],[56, 71],[64, 73]}
If the selection was, for example:
z := cand[24];
z := [40, 109]
Peter does not know the numbers since he has these possibilities:
factors[z[1]*z[2]];
{[5, 872],[8, 545],[10, 436],[20, 218],[40, 109]}
With that sum i.e. 149, all choices have ambiguous products. This is what Simona knew. We find the minimum number of choices for every possible pair.
min( seq( length(factors[i*(z[1]+z[2]-i)]), i=1..z[1]+z[2]-1 ));
2
Now Danielle says, "I do not know the numbers. I can only guess one number that probably is there but I do not know for certain."
d2 := sort([ seq( z[2]-z[1], z=cand )]);
d2 := [3, 3, 5, 7, 8, 9, 9, 9, 14, 15, 19, 21, 21, 21, 23, 27, 27, 31, 39, 45, 57, 69, 69, 81, 81, 87, 93]
This set is small enough that we can print the candidate differences that Danielle might see. Since Danielle does not know the answer, only differences which appear many times should be kept.
d2 := { seq( If(d2[i-1]=d2[i], d2[i], NULL), i=2..length(d2) )};
for d in d2 do
w := { seq( If(z[2]-z[1]=d,z,NULL), z=cand) };
lprint( d, w, sort( [seq(op(z),z=w)] ))
od:
d2 := {3,9,21,27,69,81}
3 {[1, 4],[29, 32]} [1, 4, 29, 32]
9 {[23, 32],[32, 41],[64, 73]} [23, 32, 32, 41, 64, 73]
21 {[16, 37],[32, 53],[43, 64]} [16, 32, 37, 43, 53, 64]
27 {[16, 43],[37, 64]} [16, 37, 43, 64]
69 {[32, 101],[40, 109]} [32, 40, 101, 109]
81 {[8, 89],[16, 97]} [8, 16, 89, 97]
Only one difference has a candidate number with a higher probability of occurrences and that is the difference of 9. If the difference is 9, there is a 2/3 chance that one of the numbers is 32. So Danielle sees a 9. Peter then says he knows what she is thinking but this is wrong then Danielle knows that 32 is not a candidate so the the numbers must be 64 and 73.
The computation speed can more than likely be improved with some improvements to the algorithm. Here we concentrated on finding a solution.
© 2007 by Gaston Gonnet, Gina Cannarozzi, Informatik, ETH Zurich
Last updated on Mon Nov 19 16:26:34 2007 by gmc