Discovering Hamming Codes

July 18th, 2010 admin

Digital data, transmitted over a communication medium (wireless, optical fiber, copper wire), or stored in some storage medium (such as computer memory or hard disk), is prone to bit-flips and errors. For example, if the message “10110101000101010″ means “BILL JOHN” and communication channel noise flips a bit, the message received may be “10010101000101010″, meaning, “KILL JOHN”. Now, that could create a problem. The problem also exists in data that is sitting untouched on a digital storage medium. Have you ever noticed that if you open some photo file on your computer, after years of storage, they develop strange colors and often do not display fully? This could be due to some bit errors in the stored 1s and 0s that represent the image file data. Read the rest of this entry »

Posted in Information, Tidbits, Tutorials, Uncategorized | No Comments »

Fascinating course on Justice by Michael Sandel

June 20th, 2010 admin

Here is a link to video lectures from Harvard University’s course on Justice, taught by Professor Michael Sandel. (Watch the introductory video which should start automatically, and then look for the Episode list to the bottom right of the page. 12 hour long lectures – but worth the time.)

http://www.justiceharvard.org/

It contains some fascinating discussions on morals, philosophy, rights and justice. Professor Sandel has a very interesting teaching style, where he almost helps the students discover right vs. wrong, rather than just teaching it to them. Also, he has an extraordinary delivery style – careful and sincere. It is clear that he is actively participating in the discussion himself; he tailors the material such that it conveys all the crucial points while at the same time allowing the journey to these crucial points to be shaped by the students in the classroom. The class itself is comprised of over a thousand students, hanging on to every word from the teacher, and is a sight to behold.

A must watch. More accurately, a must think.

Posted in Information, Philosophy, Tidbits | No Comments »

Thoughts on the mathematical constant e

May 16th, 2010 admin

e for exponential

The mathematical constant shows up in strange places. Moreover, its significance is not as easy to grasp as that of the other famous constant, , because there is no easy physical object in whose context to imagine it. For example, is the ratio of the circumference to the diameter of a circle. Yes, it is irrational, but if you can get over that mystery (or ignore it for the time being), it is straightforward to imagine what is. Every circle does seem to have a certain circleness, which makes them all look the same. It is intuitively not hard to agree with the hunch that every circle has an unchanging ratio between the circumference and the diameter; and it makes sense to keep that ratio handy and give it a name.

The constant is considerably more elusive. It appears, at first, to be a number you would not go hunting after. You just happen to stumble upon in during one of your mathematical excursions; it seems interesting enough that you then pick it up and put in in your pocket for some potential use later. After stumbling upon the same thing along other mathematical excursions, in hindsight, it does seem to be something rather useful. Something you should have gone looking for. Read the rest of this entry »

Posted in Information, Tidbits, Tutorials | No Comments »

We, the people …

May 2nd, 2010 admin

There are about 6.7 billion people in the world today. If you got them all together and made them stand in a square grid on a square field such that each person is a meter away from his or her 4 neighbors, the field needs to be about 51 miles x 51 miles – about the size of the red square in the illustration.

Reference for the population figure: http://www.google.com/publicdata?ds=wb-wdi&met=sp_pop_totl&tdim=true&dl=en&hl=en&q=world+population

Posted in Information, Tidbits | No Comments »

The 4 squares problem – extended

May 1st, 2010 admin

A “4 Squares Puzzle” is doing the rounds over the internet nowadays. here are the original Microsoft Powerpoint slides which I received via email from my father. (Not sure who the original author of these slides is, but the slides report the author to be Nakit Yonetimi.) It may be useful to look over the pdf file once before proceeding. The question posted in the slides is different from the one I am going to pose, but going through the slides helps build context and helps get mentally warmed up.

The question I posed to myself after thinking through the puzzle was, “How can we divide a square into 7 equal parts with only a straight edge and a compass available?” Note that the question implies that we do not have a ruler or a scale. We have a straight edge, but without any markings on it to indicate inches or centimeters. Even if it did have the markings, such markings can only measure accurately up to a certain level. For example, say you have a scale with markings at the granularity of a millimeter. Say the square had a side equal to some irrational number, say or , or, even a simple integer which is not a multiple of 7, such as, 8 millimeters. There is no way to measure or or millimeters using such a scale.

There are at least 2 approaches to dividing this square into 7 parts. The first is a simpler approach and the second is slightly more involved. Let me talk about the second one first. The first one will then become easy to see. The main intuition behind the first idea is that a triangle’s area depends only on its base and height. If we can mark out 7 equidistant points along the square’s border, thus creating 7 equal bases, we can join the bases to the center of the square to create 7 regions with equal areas. The heights of these shapes will be equal, and the bases are equal by construction. Read the rest of this entry »

Posted in Family, Tidbits | No Comments »

Cool Gate-Level Logic Simulation Tool

November 14th, 2009 admin

Dr. Mark Hill of University of Wisconsin Madison pointed out the existence of this really cool learning aid to his class Logic Design class in October 2009. He also provides some guidelines about how to use the tool. Give it a shot if you like to play around with AND, OR, NOT gates and build logic. You can build “memory” structures too, something that can remember state. The following text is from Dr. Hill’s email. Enjoy. Read the rest of this entry »

Posted in Tidbits, Tutorials | No Comments »

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 »