Mau’s Question

May 24th, 2008 admin

There is a matrix of numbers with n rows and m columns. The matrix consists of integers taking the value 1 through n. That is, at any given cell in the matrix the value is 1 or 2 or 3 or … or n. We want to find out how many such matrices exist in which you can always find n cells, one per row, that together have all the n unique integers in them.

Here is my approach and my solution to the problem. This solution has not been verified by Mau or anyone else, and there is a chance that I am missing some aspect of rigor required to make the proof watertight and, thus, self-verifying.

Approach

The space of all nxm matrices can be divided into a disjoint set of matrices that completely span the space. This disjoint set comprises
- matrices which have no row with all n numbers
- matrices which have exactly one row that contains all n numbers
- matrices which have exactly two rows that contain all the n numbers
… so on till
- matrices which have exactly n-1 rows that contain all the n numbers
- matrices which have each of the n rows containing all the n numbers

Now we can solve the problem for each subset that makes up the disjoint set that spans the space of mxn matrices, and add up the individual results. Interestingly, working backwards makes more sense to me. So let’s look at the subset of matrices which have all the n numbers in each of the n nows. There is no candidate matrix here that fails our criterion. All matrices will satisfy the criterion. Let’s call the set of matrices that satisfy the criterion, the set S and those that fail the criterion the set F. Therefore no matrix in this subset adds to F.

Next, let’s look at the subset of matrices which have all the n numbers in exactly n-1 rows. The remaining row, whatever be the number or numbers it carries, will cause the matrix to satisfy the criterion. Therefore no matrix in this subset adds to F.

Next, let’s look at the subset of matrices which have all the n numbers in exactly n-2 rows. The remaining 2 rows, will cause the overall matrix to fail, if they have no more than 1 number in them. That is they remaining two rows must be full of only one number. If a second number exists in either of the two rows, the matrix satisfies our criterion.

And so on.

So, the number of matrices in F is a sum of the following product over all values of i:
(how many ways can we select n-i rows)(how many ways can all n unique numbers show up in each of those selected rows)(how many ways can the remaining i rows contain, at most, i-1 unique numbers)

Solution

Basically, out of all possible matrices with n rows and m cols such that each element is an integer between 1 and n (both included), I try to figure out the number of matrices which do NOT satisfy the condition we are after, i.e., for these matrices you CANNOT select n elements, one on each row, such that the n elements are the n unique numbers, 1 through n. Call this set of matrices, which fail the condition, F (for fail). We are trying to find how many elements are in the set F.

The final answer for the number of matrices the satisfy the criteion, therefore, will be n^(n.m) - |F|, where |F| represents the cardinality of F, that is, the number of elements in set F.

To get to |F|, my line of thinking was:

F =
matrices for which there are, at most, n-1 unique numbers in the n rows
+ matrices for which there are, at most, n-2 unique numbers in n-1 rows and all n numbers in the remaining 1 row
+ matrices for which there are n-3 unique numbers in n-2 rows and all n numbers in the remaining 2 rows + … etc.

By ensuring that all the n numbers show up in the remaining x rows we are making sure that the matrix that satisfies a given term in the above summation does not satisfy the the previous term, and thus avoids being double counted.

Substituting terms,

As a summation, this can be written as

Here is how to understand each term in the summation above:
is the number ways can you choose n-i rows
is the number ways can you choose the n-i-1 numbers that will go into the selected n-i rows
is the number of ways can those (n-i).m elements in those n-i rows be filled with the chosen (n-i-1) numbers
is the number of ways we can guarantee that the remaining i rows each contain all the n elements.

Posted in Tidbits | No Comments »

A puzzled family

April 22nd, 2007 admin

This year started with several of my family members contributing several puzzles. I decided to compile them here since the puzzles were, firstly, interesting and secondly tell you a little bit about the people who asked them. Anant, my brother, sent the following in an email to me and my family. He said he found it on an IBM puzzler website. He, however, modified it a bit to make it more interesting to us all. Here’s Anant’s puzzle.

Anant’s Party Puzzle

Anil and Kavita attend a party with 3 other couples,including Srini and Shyamala (a couple). During the party everyone shakes hands with a certain number of other people that doesn’t include oneself and one’s spouse. At the end of the party Anil asks each person (apart from himself) how many people they shook hands with. He finds that each person answered truthfully and each one gave a different number. Anil did shake hands with Srini. From this information find out
1: Did Kavita shake hands with Srini?
2: Did Kavita shake hands with Shyamala?
Adapted from a puzzle found here (the last but one puzzle June 1998): http://www.research.ibm.com/ponder/

Solution:

Anil asks 7 people and gets 7 different handshake counts. The maximum count can be 6, since a person does not shake his own hand or his spouse’s. The 7 non-negative numbers (there cannot be negative counts) with a maximum of 6 are 0, 1, 2, 3, 4, 5, 6. Whoever has a count of 6 shakes hands with all the other people (other than his or her spouse, of course). Therefore, only that spouse can be the one with the 0 count. If Kavita were the person with the count of 6, no one but Anil could have had the count of 0. But Anil did hear someone else say 0. If Kavita were the person with a count of 0, no one else could have claimed 6. However, someone did. So Kavita does not have a count of 0 either. There is some couple with counts of 0 and 6. If that couple is removed from contention, everyone reduces in count by 1, the 1 coming from their handshake with the person with count 6. Anil and Kavita shook hands with one person in that couple (the one with the count 6). The remaining counts become 0, 1, 2, 3, 4. Whoever has the count of 4, partners the spouse with count of 0, using logic similar to above. Also, this couple cannot be Anil and Kavita. If Kavita had a count of 4, no one could have claimed a count of 0. If Kavita had a count of 0, no one could have claimed a 4. Therefore, the 4-0 pair is not Anil-Kavita. Again, Anil and Kavita shook hands with one person in that couple (the one with the count 4). Removing the 4-0 pair (originally the 5-1 pair) from contention, we have the counts of 0, 1, 2.
Using similar logic as above, the 2-0 pair is not Anil-Kavita. Removing them (original pair 4-2), leaves Kavita alone with the count of 0. Bumping it back to the original count gives us 3. Kavita and Anil shook hands with one person in each couple, and, Anil and Kavita shook hands with the exact same people. So, to answer the specific questions - Yes, Kavita shook hands with Srini, and, No, Kavita did not shake hands with Shyamala.

Raghu’s Peanuts Puzzle

Later, when we visited my cousin and his family in New Jersey, he asked me and Anant a high protein mathematical puzzle laden with peanuts. I will recreate the puzzle from memory here.
There are 5 friends and a pet monkey. They also have a bag of peanuts. The are travelling through a tropical jungle in southern India when they decide to stop for the night in a clearing. They pitch the tent and go to sleep. One of the 5 friend wakes up in the middle of the night, a little hungry. He remembers the peanuts. He steps out quietly, careful not to wake anyone up, with the peanuts bag, divides up the peanuts into 5 even parts. He finds one extra peanut remains after the division. He feeds the remaining peanut to the monkey, eats his share and goes back to sleep. The other 4 friends wake up one after the other also and do the exact same thing as the first guy. Then, morning comes. Everyone wakes up refreshed and, unsurprisingly, a little hungry. They divide up the peanuts in the clearly smaller looking bag. And again just like each of them had found in the night, they find one peanut remaining. They feed that to the monkey, taking the monkey’s total intake to 6 peanuts, and eat the remaining peanuts. How many peanuts were in the bag when they pitched the tent?

Solution:

Raghu had asked me this puzzle about 4 years ago, when I had visited them in Alpharetta (near Atlanta), Georgia. I am not sure if my then recent exposure to discrete mathematics at Purdue University helped, or, as might be more likely, my mathematical intuition worked better then. I was actually able to solve the puzzle without resorting to a spreadsheet or a computer! This time around I found it harder to imagine up a way to solve it without a computer. I did find the answer with a spreadsheet program, but that was hardly consequential. More than getting the answer, this exercise was, for me, a journey in figuring out how to solve it without a computer. And in doing so I learnt something about what such problems are called and a generic way to solve them. This problem appears in several places in the web with coconuts in place of peanuts. The solution also appears in several places. I will try to recreate my approach.

Say, the initial number of peanuts is N.
When the first guy wakes up he sees N peanuts. When he is done eating there are (4/5)(N-1) peanuts.
When the second guy wakes up he sees (4/5)(N-1) peanuts, which is
(4/5)N - (4/5).
Similarly, when the third guy wakes up he sees, (4/5)[(4/5)N - (4/5) - 1] peanuts, which is
(4/5)²N - (4/5)² - (4/5)
Extending the pattern, when the fourth guy wakes up he sees,
(4/5)³N - (4/5)³ - (4/5)² - (4/5) peanuts
Extending the pattern, when the fifth guy wakes up he sees,
(4/5)⁴N - (4/5)⁴ - (4/5)³ - (4/5)² - (4/5) peanuts
When they all wake up the next morning, they all see,
(4/5)⁵N - (4/5)⁵ - (4/5)⁴ - (4/5)³ - (4/5)² - (4/5) peanuts
This, is again divided evenly amongst the 5, after a peanut is given to the monkey. That implies that the above count of peanuts is precisely 5k + 1, where k is some integer.
The final equation looks like,
(4/5)⁵N - (4/5)⁵ - (4/5)⁴ - (4/5)³ - (4/5)² - (4/5) = 5k + 1

This reduces to,
(1024/3125)N-(1024/3125)-(256/625)-(64/125)-(16/25)-(4/5) = 5k+1
=> (1024/3125)N-(1024/3125)-(256/625)-(64/125)-(16/25)-(4/5)-1 = 5k
=> (1024/3125)(1/5)N-(1024/3125)(1/5)-(256/625)(1/5)-(64/125)(1/5)-(16/25)(1/5)-(4/5)(1/5)-1(1/5) = k
=> (1024/15625)N-(1024/15625)-(1280/15625)-(1600/15625)-(2000/15625)-(2500/15625)-(3125/15625) = k
=> (1024/15625)N-(11529/15625) = k
=> 1024N-11529 = 15625k
=> 1024N-15625k = 11529

Finally, we got the equation we were after. But wait a second, there are two variables(N and k) and only one equation! That is the equation of a line. You choose any value of N and you can always find a k. How are we to solve that for a single solution or a set of solutions?
Aha! Integers. N and k can take only integral values. So, even though this is the equation for a line, we are trying to find out if this line passes through the lattice points. Such equations have a special name - Diophantine equations. The one at hand, specifically, is a Diophantine equation of the first order, in two variables. These equations have been studied and solved in texts written between 800 BC and 500 BC in India. Aryabhatta and Brahmagupta (around 400AD to 650AD) gave general solutions to such equations and extended the study to higher order Diophantine equations and ones with more variables.
A generic Diophantine equation looks like ax + by = c, where x and y are the variables that must take integer values. a,b,c are integer constants. A equation of this type may have no solutions or infinitely many solutions. An example of an equation with no solutions is
2x + 2y = 5 (No Solution!)
The above equations has no solution because whatever the values of integral x and y, the left hand side is even and right hand side is odd.
A way to think of it is, you can draw a line on a graph paper such that it neatly avoids all the lattice points. I am not sure about this, but intuition tells me that if a line does cross through one lattice point, it will cross through infinitely many. That is, in other words, there are are either no solutions or infinitely many for a given Diophanine equation of the above form.

Now, coming back to the equation at hand, it is easy to see why a spreadsheet is a tempting approach. You vary N from 1 through a big number. You write k in terms of N, and visually inspect if K ever takes an integer value. Though this approach is what I tried at first, it is both ugly, unsatisfactory and unbounded. There might be no way to figure out if there exists no solution!
The solution that follows is based on the approach shown at this BBC webpage about Diophantine equations.

1024N-15625k = 11529
Now pay careful attention. The right hand side (11529) is odd. The first term on the left hand side (1024N) will always be even, whatever the value of N. The second term on the left hand side (15625k) will be even if k is even, and odd if k is odd. If k is even, the whole left hand side will be even. But since the right hand side is odd, this can’t be. Therefore k must be odd. We can, therefore write k is 2a+1. And the equation becomes,
1024N-15625(2a+1) = 11529
1024N-2(15625)a - 15625 = 11529
1024N-2(15625)a = 27154
Now notice that all the terms have a common factor of 2, which when cancelled out, leaves
512N-15625a = 13577, where k=2a+1
Continuing the above logic, and successively substitution 2b+1 for a, 2c+1 for b etc, when a or b should be odd and 2b for a, 2c for b etc. when a or b should be even, we get the following equations.
256N-15625b = 14601, where a=2b+1
128N-15625c = 15113, where b=2c+1
64N-15625d = 15369, where c=2d+1
32N-15625e = 15497, where d=2e+1
16N-15625f = 15561, where e=2f+1
8N-15625g = 15593, where f=2g+1
4N-15625h = 15609, where g=2h+1
2N-15625i = 15617, where h=2i+1
N-15625j = 15621, where i=2j+1
The final equation gives us,
N = 15621+15625j

The smallest positive solution therefore is N = 15621, when j = 0. This is one valid solution. Substituting N in the original Diophantine equation gives us k = 1023. So the 5 friends could have started with 15621 peanuts and had 1023 peanuts the next morning. Of course, they could have also started with 15625 + 15621 = 31246 peanuts (j=1 case) or even more.
I vaguely remember that this is how I had solved it in Alpharetta, GA, four years ago, without knowing anything about Diophantine equations and Brahmagupta or relying on spreadsheets.

My father’s Walkers Puzzle

Then, a few days back, my father, who loves his daily hour-long walks sent us this walking related puzzle. Later, when I wanted to confirm my answer, he informed me that he made the problem up but had not been able to solve it yet! The fact that he was able to think this up is by itself impressive considering the solution is not straightforward, yet, involves elegant abstraction. Since he thought this up when walking with his good friend who I call Subbanna Uncle, I will recreate the puzzle with my father, Kishore, and Subbanna Uncle participating in the activity.
ABCD is a rectangular park with a walking trail on all four sides. The rectangle is of dimensions a units by b units.
Two walking enthusiasts, Subbanna and Kishore, start walking around the park’s trail with same speed, S units per hour.
Subbanna starts at A and goes around the park covering all 4 sides each time repetedly, AD->DC->CB->BA->AD->DC… and so on.
Kishore starts at the same time as Subbanna but starts at B and walks around the park covering 3 sides repeatedly, BC->CD->DA then he turns back to trace AD->DC->CB, turns back again and so on.
1: How many times do Subbanna and Kishore cross each other while walking for a time period of t hours?
2: How many times do Subbanna and Kishore walk side by side in the same direction?
3: What is the time period before the two walking routines repeat an earlier pattern?

Solution:

The park is a rectangle with sides measuring a units and b units as shown.

The pattern that Subbanna follows is shown with a yellow/orange line and the pattern that Kishore follows is shown with a green line.

The beauty of this problem is that it is easier to solve the puzzle by opening up the paths. Both the paths taken by the two walkers are repetitive. What we need is a repetitive representation that would show intersections of the paths accurately, while clearly laying out the paths in time, so that a repetition does not overlap a previous representation. I chose to keep time on the x-axis and label the corners A,B,C,D on the y axis. The speed being constant keeps the path traced by the walkers straight lines on this graph, and also helps assign a scale for the x-axis.
Subbanna’s pattern repeats every (2b+2a)/S hours, while Kishore’s repeats every 2(2b+a)/S hours, as is clear from the graph. While Kishore is going in the BC->CD->DA direction (downward) he intersects Subbanna’s path once or twice. He cannot avoid intersecting because the distance between two parallel orange lines is less than the length of Kishore’s downward path. If Subbanna’s orange line intersects Kishore’s upward path (AD->DC->CB), that has to be the time they walk together.

After time t, the projection of time on to an axis parallel to Kishore’s downward path, is t*S distance units. This is shown as T is the figure, however, to avoid confusion let us continue to use S*t for that distance. In this time, every orange line (Subbanna’s one loop) causes an intersection with Kishore, except if they overlap. Put mathematically,
the total number of intersections = total number of orange lines - number of times orange line and upward green line coincide
total number of orange lines = (t*S - (2b+a)/2)/(b+a) + 1
“number of times orange line and upward green line coincide” is a little more involved. The first time they coincide, (2b+a)/2+n*(b+a)=m*(2b+a), where m and n are integers. This implies,
n*(b+a)=(m-1/2)*(2b+a)
Multiplying by 2 on either side,
2n*(b+a)=(2m-1)*(2b+a)
If (b+a) and (2b+a) are integers,this will happen if 2b+a is even. If 2b+a is odd, this will never happen and Kishore and Subbanna’s paths never coincide. If (a+b) and (2b+a) are not integers, then I am not sure what the condition is for the paths to not coincide. I assume they will always coincide.
From them on they coincide when k*(b+a)=l*(2b+a), which is every LCM(b+a, 2b+a) units.
Therefore, “number of times orange line and upward green line coincide” = (0 or 1)+(S*t)/(LCM(b+a,2b+a))
Here are the final answers:
1: How many times do Subbanna and Kishore cross each other while walking for a time period of t hours?
(t*S - (2b+a)/2)/(b+a) + 1 - (0 or 1) + (S*t)/(LCM(b+a,2b+a))
2: How many times do Subbanna and Kishore walk side by side in the same direction?
(0 or 1)+(S*t)/(LCM(b+a,2b+a))
3: What is the time period before the two walking routines repeat an earlier pattern?
The time period is when the original situation repeats. That is Kishore is at B and Subbanna is at A.
LCM(2*(2b+a)/S, (2b+2a)/S)
Note: I have used LCM for Least Common Multiple, and I do not restrict it to integers alone.

Posted in Tidbits | No Comments »

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

September 3rd, 2006 admin

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”);
          }
        }
      }

    }

Posted in Tidbits | 1 Comment »

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 »

Poisoned Wine

June 4th, 2006 admin

You are the Monarch of an Island and are about to have a festival tomorrow. The festival is the most important one you have ever had. You’ve got 1000 bottles of wine you were planning to open for the fiesta, but you find out that one of them is poisoned by some evil scoundrel. The actual poison exhibits no symptoms until somewhere around the 23rd hour, then results in sudden death. You have thousands of prisoners at your disposal.

1. What is the smallest number of prisoners you must have to drink from the bottles to find the poisoned bottle?
2. What is the smallest number of prisoners that you must sacrifice?
3. For the strong minded, what is the smallest number of prisoners if more than one bottle (say 2) is poisoned? Read More (pdf file)

Posted in Tidbits | No Comments »

Send More Money

October 19th, 2005 admin

My father asked me this question over the phone this weekend.

“A college going kid’s father, tired of his sons repeated requests for money throws him a challenge. He asks the son to solve a math puzzle, before expecting any more money from the dad. SEND + MORE = MONEY is a mathematical equality, where each letter is a unique numeral. What is the equality in numbers?”.

It turned out to be an immensely interesting puzzle. It has a unique solutions, the solution can be logically deduced, and it makes a sensible English phrase! That third point is something I am still not sure whether to be amazed by or not.

Here is a sequence of steps I followed in my deduction of the solution

  S E N D
+ M O R E
---------
M O N E Y

The M has to be a 1, since the carry from adding S of SEND and M of MORE can be either a 0 or a 1, and in this case it is a 1 since we have M in MONEY to represent it. Another way to say the same thing is adding two numbers in the thousands can not give you twenty thousand or more. even 9999 + 9999 falls short of 20000 by 2.

  S E N D
+ 1 O R E
---------
1 O N E Y

S in SEND and 1 from 1ORE have to add to result in a carry since the whole existance of the 1 in 1ONEY depends on it. That is possible only if S is 9, there is no carry from the hundreds’ place (and therefore the O in MONEY is 0) or S is 8 and there is a carry of 1 from the hundreds’ place (in which case the O in MONEY is 0 again) or indeed the case that S is 9, and there is a carry of 1 from the hundreds’ place (and here the O in MONEY is 1). Since O can’t be 1, as M has wrested that privilege, the only two plausible choice is that S in SEND is 8 with a carry from the hundreds’ place or the S is 9 with no carry from the hundreds’ place. So, are we stuck? Which of these two to choose? Well, time to look a little into the future, by which I mean the hundreds place. One thing is certain, whether S is 9 with no carry or 8 with carry, the O in MONEY is 0. Therefore the O in MORE is 0 too! So looking at the hundreds’ place, E + 0 = N. That can’t be. There must be a carry from the tens’ place! So the hundreds’ place equation now reads, 1 + E + 0 = N. The question we are after is does 1+E give rise to a carry or not. Only way it can give rise to a carry is if E = 9. But then 1+E =10 and that means N = 0. That can’t be. O has gotten that privilege. So we do not know what E is but is certainly is not 9 (and not 0 or 1). So that means, since there is no carry over from the hundreds place S is 9.

  0 1
  9 E N D
+ 1 0 R E
---------
1 0 N E Y

N is one more than E. At first glance the values E can take are 2,3,4,5,6,7,8. Of these, 8 has to be ignored since then N would be 9. But 9 has already been assigned to another letter. Still the choices for E are too many. Looking at the tens’ place, N + R = E + 10 or 1 + N + R = E + 10 (if there is a carry from the ones’ place). The 10 in the above equation comes in because there is a carry from the tens’ to the hundres’ place for sure. Substituting E+1 for N, we get either E + 1 + R = E + 10, which implies R = 9 which is not possible, or that, 1 + E + 1 + R = E + 10, which leaves us with the information that R = 8 and equally importantly, that there is a carry from the ones’ to the tens’ place.

  0 1 1
  9 E N D
+ 1 0 8 E
---------
1 0 N E Y

Now we look at the ones’ place. D, E and Y have to be three amongst 2,3,4,5,6,7 since the others have been taken. The information that the ones’ place lends a carry to the tens’ place means D + E = Y + 10. Note than the ones’ place cannot have a carry from the tenths’ place. This implies that D and E have to add up to at least 12, since Y is, at a minimum, 2. The only ways of adding a pair from the remaining numbers to get 12 or more are 5+7 or 6+7. E is either 5,6 or 7. Now we fall back upon the hundreds’ place to bail us out of the dilemma. The hundreds’ place tells us that E + 1 = N. Therefore E cannot be 7, since then N would be 8. N cannot be 8 since 8 is taken by R. Since E cannot be 7, E is either 5 or 6. Either way, D is 7. Now, if E were 6, N, which is E + 1, would be 7. That is not possible since we just allocated 7 to D. So E is 5 and N is 6.

  0 1 1
  9 5 6 7
+ 1 0 8 5
---------
1 0 6 5 Y

Y is therefore 2. And the final solution is 9567 + 1085 = 10652

Posted in Tidbits | No Comments »

Crossword Clues

August 28th, 2005 admin

Kavita and I sometimes play this game over the phone, where I give Kavita a clue and she has to figure out the word. The clue is usually simpler than a cryptic clue in a crossword puzzle, bit I would still categorize it as a cryptic clue because there are two parts to the clue. Either both buttress the reason for the clue’s solution being what it is, or one provides the solution while the other part of the clue confirms it. In general I prefer cryptic clue crossword puzzles over easy clues, because with cryptic clues, each clue is a puzzle in its own right, and the crossword puzzle fills itself once you get the answer.

Syhamala and Srini also enjoy participating in this kind of a cryptic clue session. Lot of times, since the clues are created on the fly and are not “solidified” yet, they are twisted and mangled as the game proceeds leading to strange guesses and a hearty laugh. Shyamala suggested that I should atleast keep track of these, and therefore I am putting them together here.

Hereditary Clothing
Aim to shop at this store
Mated domesticated
Spherical dance
Direction I threw the stew in
India grows teas in this direction
Direction of old “you”s
Direction prickly things go
Mites multiplication factor
He levitated like this flower
Sue it’s for blowing your nose

Posted in Family, Tidbits | No Comments »

Binary vs ASCII Files

July 17th, 2005 admin

How are they generated?

The difference in how a file is written into memory is crucial in knowing how to read it. If a file is written using fprintf, then the data in the file is stored as a sequnce of ASCII characters. This creates a file in the ASCII format. If the was written using fwrite, then the data would be stored as one of many data types depending on what the fwrite is writing. For example, if the fwrite is writing an int (32 bit quantity), then the 32 bits are written to the memory as is. This creates a binary format file.

Example

If you write 12345678 to a file using fprintf, the file will actually have the ASCII codes for the symbols ‘1′, ‘2′, ‘3′ and so on, a total of 8 bytes. If you write 12345678 to a file using fwrite and the pointer to the source is an int*, then the 32 bit (4 byte int) binary corresponding to 12345678 will be directly written to 32 bits in memory.

How does it matter?

ASCII, being a byte by byte storage format, is not affected by big-endian/little-endian storage issues. Since the bits in a byte are not affected by little or big endian storage scheme, only problem arises if the datum being stored as a single-entity crosses the byte boundary. And that happens with something like storing a 32 bit quantity as is (in binary). Therefore, when reading an int from a binary file using fread, one should be careful to flip the bytes in case the machine that is reading the binary file uses a different endian scheme than the machine that had written the file. I faced a problme recently where a trace file feeding one of our performance models was in big-endian binary format in memory. I had to read one instruction (32 bits) at a time and flip the bytes, before I could use the trace when the model was running on a little endian machine.

Posted in Tidbits | No Comments »

A puzzling weekend

April 3rd, 2005 admin

The puzzler went something like this “There is a famous person in history, with 5 lettered first name and 4 lettered last name. Rearrange the first name to make a term used in a certain game and rearrange the lastname to make the name of that game!”

I thought about it for a few seconds and realized that finding the names of games that are only 4 letters long might be worth it. Golf and polo came to mind. But I could not think of many 5 lettered terms used in those games. I was listening to the National Public Radio’s Weekend Edition Sunday on the radio, brushing my teeth. Soon I went down to the kitchen to preparing my usual weekend morning tea. I started heating water on the range when I called Kavita. She woke up sleepy eyed and after a few initial words I threw at her this problem. Upon hearing that I was thinking about polo as an option, she just said “Marco Polo”. She said it as a joke, almost as a rebuttal that if I thought of Polo, she actually though of a famous person with that for a last name. Maybe she did not realize that the problem had the added twist of rearranging the letters. Almost immediately a light bulb went off in my head. That could be it. “Pool is also a game and is a rearrangement of Polo!” AND more importantly, Carom, is a term used in pool! I was amazed at how she got the answer almost without realizing she had! It was a good start to the day. I sent in the solution to puzzle@npr.org today.

Yesterday I was at Srini’s place and Shyamala and I were playing wordgames like taboo (Shyamala had sometime ago written up with the word being guessed and the tabooed words that should not be used while trying to describe the word), twenty questions etc. One of the games was about thinking of something or somebody and giving indirect clues about it. She asked me a question, “I am thinking about something which cries when used, makes our lives brighter and comes in many colours. What is it?” I thought for about 5 minutes…while watching the Illinois Fighting Illini and the Louisville Cardinals fight it out in the NCAA mens basketball semifinals…I had no clue. I asked for one more clue. She said “Some of these smell nice”. I continued being clueless. Then after a few more minutes of contemplation, I asked, “Can I see it from where I am sitting?”, and she, after a few moments of thought and with a hint of uncertaininty said, “You should be able to see if from where you are sitting”. I started looking for things not in direct sight, but at the edges of my vision. Shyamala had said I “should” be able to see it. And she had taken a few moments calculating the answer given my position in the room. So it had to be something not in direct sight. Still no clue. Then my phone rang and Kavita was on the other side. After a few initial pleasantaries, I asked her this question. I even told her that I should be able to see it where I was. She might have thought for a total of 5 seconds and said candles in a tone suggestive of “Aaaawbviously”. And then the big bulb went on in my head. Every thing made sense. Every clue. And it was right in front of me all the while…sitting on the mantlepiece of Srini’s woodburning fireplace in his Brook Arbor apartment!

My comeback to Shyamala was a question about somebody famous (or infamous) and went something like - “More like a shrub, less like grass or a tree, donkey among elephants but not a donkey!

And talking of puzzles, there was this one on ThinkGeek.com. If you bought anything over $10 you were supposedly getting this T-shirt which said “Fake Ghostlike Photons”. I was wondering what satirical message could this be. The website, upon closer insoection revealed a clue that this was an anagram of some sort. Unable to solve it and unable to contain my curiosity, I googled for it and found on Slashdot, the message, in accordance with it being April Fools day recently, was, “Fools shop at ThinkGeek!”.

Posted in Tidbits | No Comments »