I don’t know. I don’t know. Now I know. Now I know!

September 3rd, 2006 admin Posted in Tidbits |

Question

My friend Srikanth, aka Coffee, sent this question to the egroups after hearing the one Anant had asked me.

A reporter meets two famous mathematicians P1 and P2 in a train and tells them that he is going to whisper the sum of two 2-digit numbers into P1’s ear and their product into P2’s, and then he wants them to guess what those two 2-digit numbers were. After he has whispered the sum and the product to P1 and P2 respectively, the conversation goes as follows:
P1: I don’t know.
P2: I don’t know either.
P1: Now I know.
P2: Now I know too.

What are the two numbers?

Solution

I ended up writing a program for this one too, although if there are paper-pencil or in-the-head kinds of solutions, I’d be happy to hear about those.

Lets take the statements one by one, and see how they reveal more and more detail. Notice that here P1 is the person with the SUM and P2 is the persone with the PRODUCT (other way round compared to the one Anant asked me). Also notice that since the range includes only 2-digit numbers, denoting the two numbers as X and Y, both X and Y lie between 10 and 99.

P1 says: I don’t know.
Deduction: Not very surprising. Unless the sums were 20 , 21, 198 or 197, there are multiple ways to add two numbers to get a SUM in the range 20 to 198.

P2 says: I don’t know either.
Deduction: X and Y are not primes, because if they were, then the product could have given away the factors. In fact, to make it more general, the product P = X*Y is such that there is more than one way to factorize it into valid factors (each factor lying between 10 and 99).

P1 says: Now I know.
Deduction: P1 has a sum S = X+Y such that of all the ways to add up two legal numbers (between 10 and 99) to get S, there is exactly one pair (which P1 could therefore identify), for which the product has more than one valid factorization. If it were any other way of adding up two numbers to add to S, then P2 would have immediately identified the unique factorization.

P2 says: Now I know too.
Deduction: P2 has a product PP = X*Y such that of all the valid (numbers between 10 and 99) ways to factorize it, there is only one pair that adds up to a sum that P1 could have identified. That is, only one factorization of P is such that if the factors were added, that sum could have been reached by only one pair of valid numbers, for the product of which multiple valid factorizations exist.

C Program to solve the same problem (specific to this range, but could be generalized and optimized to save time and space)

    #include <stdlib.h>
    #include <stdio.h>

    main(int argc, char** argv)
    {
      unsigned int i,j,k;

      unsigned int histProducts[10000];
      unsigned int X[10000];
      unsigned int Y[10000];
      unsigned int Z[10000];

      for(i=1;i<10000;i++){
        histProducts[i]=0;
        X[i]=0;
        Y[i]=0;
        Z[i]=0;
      }
      for(i=10;i<100;i++){
        for(j=10;j<100;j++){
          if(i<=j){
            k=i*j;
            histProducts[k]++;
            if(histProducts[k]==1) X[k]=i;
            else if (histProducts[k]==2) Y[k]=i;
            else if (histProducts[k]==3) Z[k]=i;
            //else printf(”%d has more than 3 ways of factorizing”, k);
          }
        }
      }

      unsigned int histNonUniqueProdsOfComponents[200];
      unsigned int A[200];
      unsigned int B[200];
      for(i=1;i<200;i++){
        histNonUniqueProdsOfComponents[i]=0;
        A[i]=0;
        B[i]=0;
      }
      for(i=20;i<197;i++){
        for(j=10;j<=(i>>1);j++){
          if(j>=10 && j<=99 && (i-j)>=10 && (i-j)<=99){
            if(histProducts[j*(i-j)]>1){
              histNonUniqueProdsOfComponents[i]++;
              A[i]=j;
              B[i]=i-j;
            }
          }
        }
      }

      unsigned int foundValidProds;
      for(i=1;i<200;i++){
        if(histNonUniqueProdsOfComponents[i]==1){
          foundValidProds=0;
          k=A[i]*B[i];
          printf(”%d,%d SUM=%d PRODUCT=%d\n”,A[i],B[i],A[i]+B[i],k);
          printf(”For this PRODUCT %d, the following factorizations exist”,k);
          if(histProducts[k]==2){
            printf(” %d*%d,”,X[k], k/X[k]);
            printf(” %d*%d\n”,Y[k], k/Y[k]);
            if(histNonUniqueProdsOfComponents[X[k]+k/X[k]]==1) foundValidProds++;
            if(histNonUniqueProdsOfComponents[Y[k]+k/Y[k]]==1) foundValidProds++;
            if(foundValidProds==1)
              printf(”Of these factorizations only 1 could have been identified by the SUM guy–VALID\n\n”);
            else if (foundValidProds>1)
              printf(”Of these factorizations >1 could have been identified by the SUM guy\n\n”);
            else
              printf(”Something is wrong with this factorizations\n\n”);
          }
          else if(histProducts[k]==3){
            printf(” %d*%d,”,X[k], k/X[k]);
            printf(” %d*%d,”,Y[k], k/Y[k]);
            printf(” %d*%d\n”,Z[k], k/Z[k]);
            if(histNonUniqueProdsOfComponents[X[k]+k/X[k]]==1) foundValidProds++;
            if(histNonUniqueProdsOfComponents[Y[k]+k/Y[k]]==1) foundValidProds++;
            if(histNonUniqueProdsOfComponents[Z[k]+k/Z[k]]==1) foundValidProds++;
            if(foundValidProds==1)
              printf(”Of these factorizations only one could have been identified by the SUM guy–VALID\n\n”);
            else if (foundValidProds>1)
              printf(”And of these factorizations >1 could have been identified by the SUM guy\n\n”);
            else
             printf(”Something is wrong with this factorizations\n\n”);
          }
          else if(histProducts[k]>3){
            printf(” %d*%d,”,X[k], k/X[k]);
            printf(” %d*%d,”,Y[k], k/Y[k]);
            printf(” %d*%d,”,Z[k], k/Z[k]);
            printf(” OTHERS EXIST TOO\n\n”);
          }
        }
      }

    }