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 »

A diagonal through a rectangular grid of squares

August 20th, 2006 admin

Question

Anant asked me this question. He had heard it in a talk by an executive at Cisco Systems.

“There is a rectangular grid composed of 1×1 squares (i.e unit squares). The grid measures m squares by n squares. How many squares will a diagonal pass through?”

There are potentially many ways to compute a solution to this one. A deep dive into discrete mathematics is one way to tackle the problem, but the fact that an executive asked the question made be believe that there had to be a more elegant approach to solving it. The lesson the executive wanted to share with his colleagues was, probably, that a problem may have only one solution, but there may be a more elegant way to get to it and a less elegant way. Elegance of a solution is probably as important an aspect as correctness. Elegance not only saves time, but it also makes the solution easy to implement, understand and sell. I believe elegance should be a criterion to further qualify a solution beyond it’s correctness.

Getting back to the question, here is a figure showing an example scenario where mxn is 5×9.

Each square in the grid is 1×1.Draw a diagonal through the grid, as shown in the next figure.

The diagonal goes through some number of the 1×1 squares. These squares are highlighted in the next figure.

In this example it is easy to count that there are 13 squares that the diagonal goes through. What is the general solution in terms of m and n?

Solution

Read this solution only after you have either solved the problem in your way or have at least given it a good think. Keep an eye on how you approached the problem. The first step in the solution is to realize that the answer is not a trivial answer such as max(m,n), i.e. the bigger of m and n, or a non-integeral sqrt(m*n), or some variation there of. To prove it to youself, draw a 2×3 grid, and see that in this case the diagonal passes through 4 squares. Now draw a 2×4 grid and notice that the diagonal again passes through 4 squares! So the solution, though increasing in general as m and n grow, might sometimes give the same answer for two different mxn values.

I will dive straight into my solution without going into other approaches. I feel that my solution is relatively straightforward, quite thorough and yet, not too hard to explain. The main observation that gets us started is to notice that m and n can have two kinds of relationships. In one case, they might be relatively prime. That means there is no common factor between the two larger than 1. Highest Common Factor of m and n = HCF(m,n) = 1. The other case is that there is a common factor larger than 1. Taking examples, if mxn is 2×3, there is no common factor other than 1. If mxn is 2×4, then 2 is a common factor. The reason this is important is that the diagonal, in its journey from one corner of the rectangular grid to the other, only passes through a grid-point (i.e the corner where 4 1×1 squares meet) if m and n are not relatively prime! Several questions arise here. First is “Why?” and the second is “So what?”. To prove this, let us use a contradiction approach. Say m and n are relatively prime. There is no common factor between m and n other than the obvious 1. Say the diagonal passes through a grid-point. Let’s pick the first grid point it passes through and call it GP. Let C1 be the corner the diagonal “starts” at, and C2 be the corner the diagonal “ends” at. Since the diagonal is a single line and has a constant slope, the slope from C1 to GP is the same as the slope from GP to C2. This implies that, treating GP as C1, the diagonal will meet another grid-point in relatively the same position from GP as GP was from the original C1. Eventually since the diagonal must hit the ending corner C2, C2’s co-ordinates (m,n), must be a multiple of the co-ordinates of the first grid-point GP, say (m’, n’). m is k*m’ and n is k*n’, for some k, which therefore is a factor. This implies that m and n cannot be relatively prime. Putting it another way, if m and n are relatively prime the diagonal cannot pass through grid-points.

Once the effect of relative primality between m and n is established, it is a very easy problem to solve. Say m and n are relatively prime. Then the diagonal never goes through any of the intermediate corners of the 1×1 squares. Only corners it touches are those of the square the diagonal starts from and the square the diagonal ends at. Only way the diagonal enters a new square is from the top or side of a 1×1 square, never from a corner. Another way to say this is, each time the diagonal cuts either a horizontal or vertical grid line it enters a new square. That means to calculate the number of squares the diagonal passes through, the only thing we need to calculate is the number of vertical and horizontal grid lines the diagonal cuts. And that is easy to calculate. Imagine for a second that the horizontal grid lines vanished. The number of vertical lines the diagonal has to cut across to reach the other corner is … well, all the vertical lines there are, which is n - 1. This is shown in the figure. Now, for a second imagine that the horizontal lines are back, but the vertical lines have vanished. The diagonal must cut through the m - 1 horizontal lines.


The diagonal, even before it starts cutting any of the horizontal or vertical lines, must start from the first square, so it touched that one square without cutting any grid lines. So we add 1 to the total count of grid lines cut by the diagonal. This gives us,

The number of squares the diagonal passes through when m and n are relatively prime is
= (n-1) + (m-1) + 1
= m+n-1 : let’s call this Equation 1

So that brings us back to the case where m and n have a common factor. The largest common factor is HCF(m,n). If you look at the mxn grid, it is basically a replication of the problem k times where k is the HCF(m,n). This is shown in the figure. Therefore the answer is to solve the problem for the smallest relatively prime grid of size m/k x n/k and just multiply that answer by k, since the problem repeats k times across the length of the diagonal, as shown in the next figure.

This gives us the final solution to this problem.
Solution for the m/k x n/k grid
= m/k + n/k - 1 (from Equation 1)

Solution for the m x n grid
= k*(m/k + n/k -1)
= m + n - k
= m + n - HCF(m,n) : let us call this Equation 2

Equation 2 is the final answer.

Posted in Tidbits | No Comments »

A House for Mr. Biswas by V. S. Naipaul

August 5th, 2006 admin

My friends Ashwin and Tania recommended this book and the following is from an email I wrote to them after reading the book.How goes life? Or in Mohun Biswas’s words, “How life, maan?”. I am still struggling to figure out the book. The tragi-comic look at the entire life of a man, leaves you wondering if it is a happy ending, a sad ending or the less categorizable, yet more recognizable ending. Endings as they typically are in real life, sadly abrupt in a way, never having achieved life’s true potential, yet satisfyingly complete, having achieved the one goal in his life. The beautiful and believable sense of humour, never taking life too seriously, is the only way he gets through life, which is otherwise overwhelmingly complicated, sad and painful.

When I was about a third of my way into the book, I was not sure why I was reading it. It seemed to have no tangible theme, too many characters and a primarily depressing story (if you could call it a story). It was as if the author picked up reams of paper and just wrote what came to his mind, letting the events and narrative flow which ever way they chose to. It was not until Mr. Biswas started tasting “victories” that I got hooked. Victories is a big word, for what were primarily small satisfactions in life - a small job, a good comeback, an occasional acknowledgement, an intelligent son, temporary privacy. These inconsequential satisfactions, in an intricate net of inconsequential emotions from inconsequential people in an elaborate yet equally inconsequential family define the few moments of joy in Mr. Biswas’ life. And the theme of the book seemed to emerge.

Mr. Biswas lives his short life, struggling for a sense of self and place. He is constantly being pulled down, not by an evil villain, not by a calamity of nature, not by a debilitating disease. He struggles against the real horrors of life, its inconsequential realness, its uncontrollable meandering, its invincible boredom. He fights. The fights he puts up are spirited. He loses some. He wins some. He laughs, he cries, he is elated, he is depressed, and yet he never gives in. He is a hero who fought grinding, never-ending battles which really did not win him anything, but at the same time won him the only thing he could hope for in his condition. A purpose. A goal. Something to look forward to. Something to live for. The beauty of the story and the writing is its truthfulness. It brings out the extraordinary in ordinary man’s ordinary life. One puts down the book with a sense of calm and understanding that is comparable to one you draw from a book on philosophy. “A House for Mr Biswas” is a strangely satisfying read that grows on you as you delve deeper into Mohun Biswas’s travails, and leaves you with an almost involved attachment to him, his family and his life.

V. S. Naipaul writes with a thin layer of believable humour protecting the characters and the readers from the insane helplessness of certain situations. The descriptions of the various regions of the J-shaped tiny island of Trinidad that Mr. Biswas spends his entire life in, the dialect, the social structure, the family structure and the life of a Hindu family Mr. Biswas marries into is expertly intertwined with the story. The strength of this book is the author’s ability to truthfully represent the seemingly purposeless life of a man, and yet bring out the the purpose in his life and that of every human being.

Posted in Reviews | No Comments »