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)2N - (4/5)2 - (4/5)
Extending the pattern, when the fourth guy wakes up he sees,
(4/5)3N - (4/5)3 - (4/5)2 - (4/5) peanuts
Extending the pattern, when the fifth guy wakes up he sees,
(4/5)4N - (4/5)4 - (4/5)3 - (4/5)2 - (4/5) peanuts
When they all wake up the next morning, they all see,
(4/5)5N - (4/5)5 - (4/5)4 - (4/5)3 - (4/5)2 - (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)5N - (4/5)5 - (4/5)4 - (4/5)3 - (4/5)2 - (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 »

Bringing beauty back to the eyes of the beholder

April 16th, 2007 admin

Anant sent me a wonderful article from the Washington Post newspaper today. The article, titled “Pearls Before Breakfast”, by Gene Weingarten, appeared on Sunday, April 8th 2007. Here is the link to the article, hoping the link continues to work for a long time.
Pearls Before Breakfast by Gene Weingarten
Reading the article evoked many thoughts which I sent back to Anant in an email, and also present here, hoping that my thoughts might futher thinking on this issue.

Anil: Anant, this is a brilliant cultural and psycological experiment that results in what the author might have found a little baffling, but fails to surprise me as much. That said, I was very happy to have read it, since it confirms my suspicions. My elation in having correctly identified human nature is matched by my disappointment at its meaning. The article distills the theory of three philosophers, regarding beauty, thus - “What is beauty? Is it a measurable fact (Gottfried Leibniz), or merely an opinion (David Hume), or is it a little of each, colored by the immediate state of mind of the observer (Immanuel Kant)?”. Yet another viewpoint, we have all heard of, is “Beauty is in the eye of the beholder.” But I wonder if it really is. Why do people pay hunderds of dollars to go listen to Joshua Bell at a concert? Why do people pay millions for a Van Gogh painting? Are they all acting out of the pure lure of beauty? I sincerely doubt it. Are many a people in the concert audience there because they want to please someone - maybe spouses, maybe bosses, maybe for their own future cocktail discussions? Are many collecters buying paintings to be able to sell it in the future for a higher price, or maybe to appear appropriately dignified and aware in their social circle? Who is judging or defining beauty here? Is it the observer or has the quatification of beauty already been done by a select few; a panel of “experts” who have been given the job of branding, evaluating and weighing beauty of an art-piece? Does their word then percolate down to the ticket costs and price tags? Is this branded beauty making people more aware or less aware of what beauty truly is? Is it training people to not heed to their own sensibilities and evaluations, but rather to always be skeptical of their own belief and to habitually fall in line behind the sensibilities of the masses? This ties in with, and runs against the grain of the overrunning theme in Zen and the Art of Motorcycle Maintenance. “What is good, Phædrus, and what is not good…need we ask anyone to tell us these things?” But is that what is happening? Are we handing over the responsibility, and therefore the return, the true joy, of appreciating what is beautiful, to others? And this ties in with the overriding theme of Ayn Rand’s “The Fountainhead”. The book talks about a world full of second-handers who depend on and imitate, yet resent and try to extinguish the prime movers, the first-handers, the visionaries of this world. This article highlights a subtler expresion of the same distinction; one within a single human being. It points to how, within a single human being, the second-handedness matures and stifles out the primal motivation to be honest, capable judges of beauty that every child is. Thanks for the forward. I hope we can continue to be aware and honest.

The following are a few more thoughts on this issue based on my reply to Anant’s email response, presented as a dialogue (though it was not, Anant’s response came together all at once, not in response to my statements presented below).

Anant: Anil, your analysis was very thought-provoking. I definitely do not think beauty is measurable and even if it is the majority of the people would not have the inclination or time to make that measurement.

Anil: I think beauty is measurable. It is not standardizable. The measure is individual and subjective. The International Standards Organization cannot come up with a “unit” for beauty. However, each one of us, has the capability to distinguish between greater beauty and lesser beauty. Indeed, is that not the resource we tap into when we say “I loved this movie” vs. “It is an Oscar winner, but I did not think it was that great”. What makes me sad is that even though we all have this skill and the sensitivity to appreciate beauty, it is the opposing quality of insensitive honesty that is found lacking. The courage to honestly and individually appraise beauty, rather than meekly submit to others’ appraisals, is what we allow to slip away over time.

Anant: If it is subjective, is there a basic sense of what is beautiful in every person that is built in, like an instinct? Like you said, it is this instinct that is being stifled due to a number of factors: the need to conform, lack of time, wrongly ordered priorities etc.
Another thing that came to my mind was that they really didn’t need Joshua Bell to prove this. For an untrained ear like mine or the majority of people who walked past him, there is no difference between how a world-famous violinist plays and how a merely good violonist would play. But I guess the stamp of “genius” that the experts have put on Bell does make the story more dramatic.

Anil: The whole point of beauty is that even to untrained ears like ours it should still qualify as beautiful! The ear of a child is probably untrained, at least in the sense you probably meant it, yet, if the music conformed to his or her sense of beauty, the child would be attracted to it. It is important to recognize that I am not saying the passers-by were stupid. Maybe the music itself was overrated! Afterall, the music that some Victorian-era musician composed with great elation and suffering, does not automatically qualify to become beautiful. As a slight diversion, my take on the issue of effort is that honest, sincere creative effort more often results in beauty than secondhanded imitation. So, for all the effort the composer and the violinist put in to the performance, the result likely will be quite beautiful. But it does not necessarily have to be. My take on the experiment itself, however, is that things of great beauty might still need time to familiarize themselves to the observer; they might not be beautiful at first sight and might need the “state of mind” that Kant talks about. The results of the experiment were partly sullied by the requirement that music, more than visual art depends on the “state of mind” and time to prove its worth. In any case, my thoughts in the previous mail were more or less independent of this particular experiment, although the article certainly evoked those thoughts.

Posted in Philosophy | No Comments »

Settling into a new year - compilers, coats, cars and cricket

April 1st, 2007 admin

It took me till April Fools’ Day to make my first post this year. Among several reasons and excuses I can come up with the main one is that the compilers’ class I am taking at NCSU. The class kept my weekends busy with all the project work it involved. However, since I am learning a few new things, I guess that’s alright. Another reason, now that I think about it, is that Kavita and I took up the grand challenge of painting our house on the inside. We have as of now only completed painting two rooms, one of which was a half-bath that originally had wall paper. The wall paper had to be removed first, and then the two coats of paint went on the walls. As the compilers’ class picked up steam, the painting adventures subsided. Also, it took a while to get used to our new life, now that Kavita and I are living together for the first time over the last few months. The adjustments, the catching up with life, which does not wait for you, took its toll on my ability to spend time with my webpage. Happy to report that we did accomplish a few minor milestones this year. The big one of course was Kavita getting a job. Then she bought a Pontiac Vibe after much research. We both love that car. Then we sold her old car, the Infinity G20. That took some effort with the repairs, the ads and the title transfer. All in all this post is a testimony to my return to some semblance of normalcy. I sense a brief and temporary settling-down at a phase of our lives where unsettling will likely be the norm.

The Cricket World Cup is going on in the Carribean islands. After almost four years I chanced to watch a couple of cricket matches live on TV a few weeks back when we visited my cousin, Raghu, at New Jersey. He had gotten installed a satellite dish that received live coverage of the Cricket World Cup. The two games I watched were India playing Bangladesh and Pakistan playing Ireland. It was fascinating that the two games I watched in so long, turned out to both be massive upsets. Bangladesh beat India and Ireland beat Pakistan. These games threw the teams’ expectations, betting odds and the statisticians’ calculations into relative disarray, and ended with both the losing teams, two cricketing giants, being eventually eliminated in the opening round of the cup. The defeats brought great outbursts of emotion from the fans (the lights and pretty much everything Indian and Pakistani). Weeks of introspections, evaluations, shock therapy and retirement announcements later, one thing that is clear is that an era of subcontinental cricket, one that I can relate to the most, is over. The defeat and the ouster from the competition, though surprising and disappointing, does not worry me a whole lot. If this provides a dose of practicality to the millions of sports-starved fans for whom the only sport that exists is cricket, it would be a welcome change. Maybe it will bring with it a dose of professionalism into a game. Professionalism into how the players perform indifferent to the pressures and expectations they are subjected to, and, more importantly, professionalism into the spectators and fans who need to realize that it is a game all said and done. The basic problem in a sports-starved country where sports has always taken a back seat to getting through life’s other challenges is that the few sporting events India does participate in take on an intimate and overly emotional dimension that cannot be dissipated easily through other avenues.

Posted in Events, Experiences | No Comments »