I don’t know. I know that. Now I know. I know too!
August 24th, 2006 admin
Question
Anant asked me this question. He had heard it in a talk by an executive at Cisco Systems.
There are 2 numbers X and Y (integers).
2<= X < Y <= 100
Person 1, P1, knows X * Y (product).
Person 2, P2, knows X + Y (sum).
P1 knows that P2 knows the sum, P2 knows that P1 knows the product.
They have this conversation:
P1: I do not know what X and Y are.
P2: I knew you would not know.
P1: Now I know what X and Y are.
P2: Now I too know what X and Y are.
What are X and Y?
Solution
This is not an easy one. At least not as easy as the previous puzzle Anant had asked. I will provide a brief commentary on the approach and then present a C program that solves the problem. The comments in the program may also be of some help, although there is probably no alternative to going through the process yourself.
Lets take the statements one by one, and see how they reveal more and more detail, thereby narrowing our choice of potential answers until we are left with one. Of course we were lucky to be left with exactly one. We could, with a larger range for X and Y, end up with more than one pair for answers. Before evaluating the statements I think there are some key things to realize. The problem is easier to solve if you were either P1 or P2. But you are not. You are relying on reducing a set of candidates such that what P1 and P2 could do at a given step and no earlier, makes sense. So other than P1’s and P2’s deductions YOUR deductions play a role. The second realization is that you might have to use a computer to help you out, for the set of possible pairs is quite big to start with. Without loss of generality I choose both P1 and P2 to be male and use “he”,”his” or “him” to refer to them.
P1 says: I do not know what X and Y are.
P2’s deduction: NOTHING, as his next statement shall reveal.
YOUR deduction: Aha! X and Y are not prime, else X and Y would be the only non-trivial factors in a factorization of X*Y.
P2 says: I knew you would not know.
P1’s deduction: I see. So P2 knew that X and Y are not both prime. This is only possible if X+Y is a sum that two prime numbers in the range from 2 to 100 cannot ever add up to.
YOUR deduction: Exactly same as P1’s deduction.
P1 says: Now I know what X and Y are.
P2’s deduction: I see. So P1 has a product X*Y such that he could calculate the correct factors, i.e. X and Y, out of all possible factors of X*Y. That means there is only one factorization of X*Y, such that the two factors X and Y satisfy the condition that X+Y is a sum that cannot be reached by adding two primes.
YOUR deduction: Exactly same as P2’s deduction.
P2 says: Now I too know what X and Y are.
P1’s deduction: NOTHING, he has solved the problem already, and has stopped listening to P2.
YOUR deduction: Aha! P2 has been able to solve the problem. P2 knew what X+Y was. P2 also knew that P1, who knew X*Y, figured it out. So P2 knew that X*Y is such that there is only factorization that when added leads to a sum that cannot be reached by adding two primes. So P2 now looks at X+Y that he knows and figures out all possible pairs that add up the sum X+Y. These are pairs such as (2,(X+Y-2)), (3,(X+Y-3)) etc.. The fact that P2 was able to pick the correct one from these possible pairs implies that there is only one pair that satisfies the property that if multiplied, the product has only one factorization (say X*Y) such that the two factors satisfy the condition that X+Y is a sum that cannot be reached by adding two primes. But we do not know X+Y. So we will have to choose all possible candidates for X+Y. Of course, we need to restrict the search to summations that cannot be reached by adding any primes (to honour P2’s first observation). So we will try to find the pair that P2 could have identified had that sum been what he was handed.
Luckily, we find only one sum that satisfies the property that P2 could have solved the problem. So we have the solution that way. If there were two such pairs, as indeed there could be with a larger set of choices for X and Y, P2 might have been able to solve it but not us.
Upon researching further on the net, I found this link to how the famous computer scientist and mathematician Edsgar W. Dijkstra’s solved it without the help of a computer and with hardly any help from paper and pencil. A couple of more interesting observations are revealed than I did above. He makes a note, in his own handwriting, at the end of the paper that he learnt that his nearly-blind sister had solved the very same problem in the sixties.
C Program to solve the same problem (specific to this range, but could be generalized and optimized to save space)
#include <stdlib.h>
#include <stdio.h>
const unsigned int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
unsigned int numOfPrimes =sizeof(primes)/sizeof(primes[0]);
main(int argc, char** argv)
{
unsigned int i,j;
/*=============================================
* P1 does not know what X & Y are from XY
* X, Y are not both prime
==============================================*/
/*=============================================
* P2 already knows the above fact.
* => X+Y cannot be a sum that can ever be
gotten by adding two primes in the given range
* histSumOfPrimes[200] is an indicator of which
X+Y sums could not be gotten by adding primes
* if histSumOfPrimes[i] == 0, that implies that
i is a sum of two numbers, that could not be
both prime. In other words i is a candidate
for what P2 has been given
==============================================*/
unsigned int histSumOfPrimes[200];
for(i=0;i<200;i++)
histSumOfPrimes[i]=0;
for(i=0;i<numOfPrimes;i++)
for(j=0;j<numOfPrimes;j++)
histSumOfPrimes[primes[i]+primes[j]]++;
/*=============================================
* P1 is now able to figure out X and Y from XY
* So of all the ways to factorize XY into a*b,
there is exactly one such that
histSumOfPrimes[a+b]==0
* We as the third person also know that we only
need to consider as the potential product P1
has, only those XY products for which
histSumOfPrimes[X+Y]==0
* histValidProds[10000] is a histogram that
keeps track of how many ways there are to
get a product XY from X and Y that satisfy
histSumOfPrimes[X+Y]==0
==============================================*/
unsigned int histValidProds[10000];
for(i=0;i<10000;i++)
histValidProds[i]=0;
for(i=2;i<=100;i++)
for(j=2;j<=100;j++)
if(i<=j) //to avoid double counting
if(histSumOfPrimes[i+j]==0)
histValidProds[i*j]++;
/*=============================================
* P2 is now also able to figure out X and Y from
X + Y.
* There are several potential break-ups P2 must
consider. Starting from 2+(X+Y-2), 3+(X+Y-3)
etc.
* From these, for him to be sure he knows which
is the pair a,b such that a+b = X+Y, he needs
to be sure that a,b are such that
histValidProds[a*b]==1, that is, there is
only one way to get a factorization of a*b
such that histSumOfPrimes[a'+b']==0 (where
a'*b' = a*b)
* Since we as the third person do not know which
X+Y P2 is starting from, we consider all
potential sums, i.e sums such that
histSumOfPrimes[X+Y]==0
==============================================*/
unsigned int histValidSums[200], X[200], Y[200];
for(i=0;i<200;i++){
histValidSums[i]=0;
X[i]=0;
Y[i]=0;
}
for(i=4;i<=200;i++){
for(j=2;j<=(i>>1);j++){ //to avoid double counting
if(histSumOfPrimes[i]==0 && histValidProds[j*(i-j)]==1)
if(histValidSums[i]==0){
histValidSums[i]=1;
X[i]=i-j;
Y[i]=j;
}
else
histValidSums[i]=2; //some invalid count
}
}
/*=============================================
* All potential X,Y values are now printed
* There is no reason to expect there to be only
1 pair. If it is 1 pair, we as the third
person, should consider ourselves lucky.
==============================================*/
for(i=0;i<200;i++)
if(histValidSums[i]==1)
printf("%d,%d\n",X[i],Y[i]);
}
Posted in Tidbits | No Comments »
