Here's someone I'd like you to meet

There's a certain rare breed of species that never fails to impress me - those who combine seemingly incongruous traits in a unique way. For example wit and compassion,  or intelligence and innocence, or humility and confidence.. I've come across a few such folks in my life, and they've let a deep impression on me.

Maths, in a way belongs to that category, though in an inanimate sense. And "how", you ask ? Maths accommodates abstraction while having no tolerance for ambiguity. What this means is that some of the best mathematicians ( atleast the non-reclusive ones) can explain complex ideas with startling clarity.

The construction of a proof is in some ways, not much different from that of an essay. Both require a chain of reasoning where one point leads to the next, without there being excessive repetition. The best proofs and truly well written pieces, in my opinion, again share something in common - Elegance.

Anyway, I write all this after reading a bit of 'Mathematical People - Profiles and Interviews', a collection of interviews with some of the most eminent mathematicians today. I'm sure it wasn't the intention, but this book doubles as a set of brilliant case studies on 'How to be fascinating' ! :)These are men and women with truly original minds and a wide range of interests. Well, it's just the kind of book I love.

Go read it. Even if you don't understand or like math.

The forgotten world of Mental Arithmetic

It has been such a long time since I last posted here that I guess no one reads this blog anymore! In a way, that is nice, since I am under no pressure to post anything useful or engaging, and can ramble on to my heart's content :-)

At roughly around the age of ten, I got drawn into the world of mental arithmetic. I had just been introduced to the world of Srinivasa Ramanujan, the enigmatic genius who tragically passed away at the age of 32 leaving behind thousands of results that researchers study to this day. Of course, I did not get to studying any of Ramanujan's brand of pure math, but I developed a great deal of awe and respect for that kind of thinking - the one that relies on leaps of intuition, and not merely plodding through pages of brute force boredom.

I think what makes people like Ramanujan special is the very thing that most of our schooling strips us of - unstructured thinking.  If I were asked to list the single biggest problem in our methods of schooling, its this - It encourages one to come up with the 'one' right answer. It does not teach the art of approximation. Answers to questions in history exams will fetch one full marks only if the person gets the year exactly right. How does it matter if there is an error of a year or two if the incident occurred a few centuries ago? Students of electrical engineering compute a resistor value to 5 decimal places, without realizing that that kind of precision is impractical, and no one is going to/can manufacture a 121.238763 Ohms resistor for you. I think learning to come up with quick and dirty estimates is just as ( or perhaps more ) important than coming up a precise answer after a few hours of solving simulataneous equations in ten variables.

During those teen years, I picked up math tips from varied sources, built up my own bag of tricks, and had great fun learning to estimate results in my head. I got fairly good at estimating squares, and square roots quickly. For me it was purely a source of amusement, and at that innocent age, I wanted to, in my own humble way, emulate some of those math stars - Hans Bethe, Von Neumann, Enrico Fermi, and many more. To this day, I don't use a calculator unless I really need an exact answer, or if I need to double check a result that is really important. With easy access to calculators, one might argue that it is worthless to learn to calculate mentally. Maybe. But I think it is worth learning it, if for nothing else, then at least for the sense of thrill and challenge that is definitely brings !

I am surprised that this kind of 'math for fun' approach hasn't made it to most schools. Or maybe I just naively, but strongly believe in it. Also, how do we 'systematically' teach 'unstructured thinking' ? I don't know the complete answer, but in my opinion, the secret is to not always be systematic. Life itself is unstructured anyway, and I think its good to introduce youngsters to some of that from an early age :-) And I think it is this kind of unstructured approach that also uncovers latent talents in students. A bright, inventive mind might be lurking behind that dull, bored backbencher , just waiting for that right mind-teaser to wake him up, and spur him into exploring more of the magic on his own ! Students don't need to be 'taught' everything; often, all they need is a trigger to get them going ! Light a spark, and it will develop into a flame on its own.

Curiously, I got into the world of programming in a similar way, but that is a story for another day, or maybe, another blog :-)

How did he think of that ?!

'How did he think of that?' has been one of the major themes in my life. Be it a wonderful Tom and Jerry sequence, just the right line at a poignant scene in a movie, a brilliant chord change in the middle of a song, or a tactful response to a difficult question in an awkward situation, I've always been left marvelling at the ingenuity of the creators. Yes, I seek beauty in everything in life.

To me, the pursuit of developing a brilliant mind is in itself a one dimensional enterprise. Brilliant minds are not always beautiful. To me, it is far more worthwhile to distribute our resources to develop ourselves holistically - intellectually, physically, emotionally, and spiritually in whatever directions we are drawn to. And it is that pursuit which forms one of the cores of my existence.

Coming back to math, I've picked a question here that, to me, dramatically illustrates the power of human thought. There was time when calculus or geometry did not exist, and there was a person who at some point had a thought that, subsequently has changed or touched our lives in intangible, yet important ways. The solution to this problem, to me represents a speck, an important speck just like so many  others, that forms a tiny piece of the infinite shades in the pallette of ideas that humans continually strive to uncover.

Question- Prove that for every number 'm' , there exists a number 'n' such that their product , m *n is a number that contains only ones and zeroes.
For example, for the number m=2, there is a number n = 5, for which their product m*n = 10, contains only ones and zeroes.

Solution - The pigeon-hole principle, which mysteriously makes an appearance in the most unlikely of scenarios lies at the heart of the solution to this problem. All it says is this -  If there are 10 holes, and more than 10 pigeons, then atleast one hole must contain more than one pigeon.

Before we proceed, please try this - Pick any six numbers. Divide each one by 5  and note down the remainders. What can we say the remainders ? Well, since we are dividing by five, the remainder must be in the range 0 to 4. Since there are 6 number we started with,  atleast two of the remainders must be same ! This is because we have 6 remainders (pigeons), each of which must take one of the 5 values( holes). Please convince yourself of this.


Now, consider numbers of the form 11, 111, 1111, 1111. Consider 'm + 1' such numbers. Divide each one by 'm'. What can we say ? From the previous idea, we can say that two of the remainders must be same ! Let's write this out for a few numbers -


11      = k1 * m + r1
111    = k2 * m + r2
1111  = k3 * m + r3



Here r1, r2, r3 etc are the remainders obtained by dividing each of the numbers by 'm'. We will have 'm +1 ' such equations written out. From pigeonhole principle, assume r5, and r7 are same. Then we can say

111111    =  k5 *m + r5
11111111 = k7*m  + r5 ( since r5 = r7 )

Now take the difference of the two .

11111100 = ( k7 - k5 ) *m

There we have it ! The Left hand side is a number that contains only ones and zeros, and 'n' = (k7 - k5 ) ! Using this procedure, we can arrive at an 'n' for every 'm'!

The trick of course was to construct this number containing ones and zeros by taking the difference between those 'nice' numbers we started with. In fact we can note that we are not restricted to choosing numbers of the form 11, 111, 1111 etc. We can pick any 'm +1' numbers such that their differences  contain only ones and zeros.

A couple of quickies !

1) A young couple are travelling in a bus, making its way through the mountains. They get off at their stop. A few seconds later, they watch in horror as  a huge boulder rolls down the slope and hits the bus. The man looks at his companion and says ' Wish we were on that bus'. Why ?

Solution - Refer to comments.

2) A clock takes five seconds to strike five ( as in 5 oh clock ). How long does it take to strike seven ? The clock is of the old fasioned kind that makes an appearance in Indian horror movies late at night :-)

Solution - This is similar to asking another question - If you have to take 3 tablets, one every half hour , how long will it take you to have them all ? The answer is not 1.5 hours, but 1 hour. You take one right now, one after half an hour, and another one after an hour.

Similarly, when we say it takes five seconds to strike five, the time count begins at the first strike. So, the next four strikes take 5 seconds, resulting in a spacing of 1.25 ( 5/4) seconds between concecutive strikes. For seven oh clock, there are 6 such spacings, which means it should take 6*1.25 = 7.5 seconds.

Of Kings and prisoners !

A king is gifted thousand barrels of wine by his sadistic arch rival. The rival attaches a note saying that exactly one of them is poisoned. Our king, a connoisseur of fine wines, would hate to throw them all away since there are 999 good barrels of wine.

The king has 10 prisoners to 'experiment' with. So he comes up with a mix of wine from different barrels for each one of them, and simultaneously has all the prisioners drink from their respective glasses. The poison takes effect in 10 minutes. Once that time has passed, the king notes who is alive and who isn't and deduces the barrel that must be poisoned ! Note that there is no second round of experimenting the with prisoners who survive the first round ordeal. So what scheme did he employ ?

Discussion - A simple first thought would be this - Take a small bit of wine from each of the first 100 barrels, mix them, and feed it to the first prisoner. Take a little from the each of the next 100 and feed it to the next prisoner, and so on. Depending on which prisoner dies, we can narrow down to 100 barrels, one of which we know is poisoned. But this is not a very good solution, since those 100 barrels must be thrown away. But our king, a demanding boss, wants the exact barrel to be narrowed down to in one shot. So how can we improve this ?

Actually, I got to know of this question a long time ago through word-of mouth, and I haven't seen a solution. I did come up with a solution that is more likely to be arrived at by electronics or computer science engineers ( Now that's a hint :-) , but I'm curious to see if people have other different schemes .

Solution - We need a solution that can uniquely identify one barrel from 1000, and we have 10 prisoners to experiment with. We note that two raised to the power of 10 is 1024. That is, we can represent 1024 different states using 10 bits ( binary digits ), much like we can represent 100 states using two digits. The motivation for using binary numbers comes from the fact that each bit can take only two values - 0 or 1, which  we can use to neatly encode the states 'alive' or 'dead' respectively.

To do this, write down the binary equivalent for all numbers from 1 to 1000. I have shown this in the table below for a few numbers. The 10 bit-positions correspond to the 10 prisoners. Look at any one column, say for prisoner p2 ( in blue ). We note all the entries in that column which contain a '1'. We note all the corresponding barrel numbers, mix up their contents and feed it to prisoner p2. This includes barrels 2, 3 and 991 besides many others that are not shown in the figure. Do this separately for each prisoner. You should find that all prisoners drink from roughly 500 barrels ( though the combination is unique for each prisoner). I say roughly because, it would be exactly 512 if there were 1024 prisoners. Here, since we have only 1000 barrels, we are operating in the truncated part of the set, and we'll see some artifacts.

Now, we will construct the binary number whose decimal equivalent will reveal the poisoned barrel. To do this , note the state of each of the prisoners. If they are alive, set the bit position to '0' , else set it to '1'. For example , we construct the binary number 1111100000 if prisoner p1 to p5 are alive, and the rest aren't. Now, just find the decimal equivalent of this - for this example, it would be 992. Essentially, we are using each prisoner's state to extract one bit of information that will point us to the right barrel. Do let me know if somebody has a different solution.

When the bulb glows ! 

1)Here is a rather well known one ! We have a bulb in a room. There are three switches outside the room, one of which controls the bulb. We need to determine which of the three switches it is. We can configure the three swiches in any state we wish. ( without being able to look at the bulb of course:-) We then enter the room, and after examining the bulb's status, need to give our answer.  Any ideas?


2) Knight on a chessboard - We have a lone knight( horse ) on one corner(where two sides meet) square of a chessboard. Can the knight get to the diagonally opposite corner square after traversing through all other squares on the chessboard exactly once ? If so, propose the route it would need to take. You only need the knowledge of how a knight moves on a chessboard to solve this one.

Hint - If at all it were possible , I believe there should be atleast two routes since the chessboard is symmetric about the starting and the ending positions. But in any case, there are a mindboggling number of possibilities to consider if there did exist a route ; so perhaps it is reasonable to expect that it is not possible. But we need to prove that :-)

An exercise with bottles

One last question before I take a break from this flurry of posts  - You are hired by a bottle manufacturing plant, and inducted into its testing department, which happens to be a 55 floor building. Your manager gives you the unenviable task of determining the lowest floor from which if dropped, a bottle would break.  He gives you two identical bottles to expriment with. Devise an optimal scheme which needs you to drop the bottle fewest number of times before determining the lowest floor from which it would break .

I have a few hints here. Please use them wisely, and refer to them only if you need to -

Hint 1 - The brute force method would involve using only one bottle . Drop it from each floor starting from the first. As soon as it breaks when dropped from a certain floor, you have the answer. However, whenever it does not break, you have to go back to the ground floor to fetch the bottle , and repeat the experiment from the next floor. This is the reason your manager, a benevolent man, has given you an extra bottle to play with.  Note that if you were to use only a single bottle , the worst case scenario would be when it breaks when dropped from the 55th floor.

Hint 2 - One way of using the second botttle is this - Drop the first bottle from the odd numbered floors - 1, 3, 5, 7 etc... Assume it does not break when dropped from the 29th floor, but does break when dropped from the 31st floor. Now,  you can use the second bottle and drop it from the 30th floor. It if breaks, 30 is your answer, else 31 it is ! Note that the worst case scenario here is when 54th floor is the lowest one from which it breaks.  But , you now have to drop the bottle roughly only half the number of times (compared to the previous case)  before arriving at the solution for the worst case scenario. But can you improve on this scheme ?

Hint 3 - What if we dropped the first bottle from every third floor - 1, 4, 7, 10 ... etc ?

Hint 4 - Last hint ! A good solution would involve multiple worst case scenarios instead of just one !  Do share your ideas !

Note - Apparently blogger has some issues, which have caused some comments to disappear ! Hopefully, in time they will reappear.

Solution - The idea is to systematically 'construct ' multiple worst case scenarios. This can be done as follows -

Drop the first bottle from the 10th floor. It is breaks, we need to start dropping the second bottle from the 1st floor to determine the lowest floor from which it breaks. The worst case scenario would be when that happens to be floor 9. In that case, we have dropped bottles a total of ten times - The first bottle was dropped once, and the second one was dropped nine times.

If the first bottle does not break when dropped from the 10th floor, drop it from the 19th floor. If it breaks, start dropping the second bottle from the 11th floor. In the worst  case scenario, which is Floor 18 in this case, you would have dropped the first bottle twice, and the second bottle 8 times - Again totalling to dropping the bottles 10 times.

Proceeding in this way, if the first bottle does not break when dropped from the 19th floor, try floor 27 next. The key idea is this - To arrive at another worst case scenario, we are dropping the first bottle one extra time, so the second one should be dropped one less time.  So the first one needs to be dropped on floors 10, 19, 27, 34 etc....

The first 10 numbers adds to 55, so I chose the building to have 55 floors. I haven't check the corner case to see if it works for 55. Else , solution would change to 11, 21, 30, 38 etc.... In that case the solution can 'support' a larger number of floors in the building.

Do let me know if you have other/better solutions..