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.