Making It Count: Counting the complement

Here’s the much delayed second part of the Making It Count series which was launched with much fanfare a month ago. The counting technique I will present is simple and powerful:

Counting the complement: Let X be a set whose cardinality is known and Y be a subset of X whose cardinality we must find. We can do this by determining the cardinality of the complement of Y (all the elements which are in X but not in Y) and `subtracting’ it from the cardinality of X.
…A couple of clarifications before I apply this rather innocuous principle to some problems:
If X is finite then the cardinality is just the number of elements in X. But I use a fancy word to include the cases when X is infinite. Note, also that subtracting cardinalities doesn’t always make sense in the infinite case. It depends on the `size’ of the infinity.

Problem 1: There are 128 players in a tennis tournament. Assuming it is a typical knockout tournament, how many matches are played before a winner emerges?
(Lazy solution): This is how most people would solve it. The `shape’ of the number 128 allows them to get away with this solution:
Pair them up. 64 matches are played initially; 64 players progress to play 32 matches and so on.The number of matches played is 64+32+16+8+4+2+1 = 127! Very good, but what about when 125 players start the tournament? One doesn’t have the comfort of repeated division by 2 anymore.
(Proper solution): Use the above counting principle! Being a knockout, a player can lose only once before he is out. So, number of matches played before winner emerges = number of matches lost = number of players who lost. Well, there is 1 winner so 128 -1 =127 players lose and so 127 matches are played. The argument works for any number other than 128. But how can 125 players be paired up in a sensible way? Well they can’t. Either the organisers add 3 players to the draw or they give a whole bunch of players a free passage into the second round, which is what a lot of the smaller tournaments do!

Problem 2: Let p be a prime and n be a non-negative integer. How many non-zero positive integers have no factors (other than 1) in common with ?
Solution: For we can just list these numbers: 1,3,5,7 have no factors in common with 8 so the answer is 4. But this method of listing is rather naive and quickly gets out of hand for even small numbers like or . Instead, we count the number of integers that do have a factor in common with . Ironically, we can list them out every time! They are just p, 2p, 3p, 4p,…,p. There are of them and so, by the principle, exactly non-negative positive integers are relatively prime to it. I haven’t contrived this problem to glorify the virtues of the counting argument. This computation is infact, one of the most fundamental in number theory and leads us to the “Euler phi-function,” denoted for N positive and defined as the number of non-negative integers N and relatively prime to it. The function is multiplicative, which means that if then from the above computation.

For instance,

The power of armchair physics

Mathematics has a well-deserved reputation of being an armchair endeavour. You sit down armed with some concepts and wander off into many wonderful directions by just digging deeper into these concepts. Physics on the other hand has traditionally been a laboratory science. One tried to understand the physical universe with experiments and codified the results with the help of mathematical tools. Einstein however came along and blurred this distinction. He changed the way we view the universe `simply by thinking about it.’ I will, in one of my next posts, show how the postulates of special relativity can be derived in a purely mathematical way in much the same way Einstein might have done. Newtonian physics recognised gravity as one of the fundamental forces that shapes our universe but was unsuccessful in explaining how and why objects attract other objects. Einstein, armchair and all, unraveled this mystery in his theory of general relativity. He visualised space-time as a fabric that stretched and curled through the universe. An object that is plonked on this fabric creates a deformity or depression that sucks in objects around it. The heavier the object, the bigger the depression and greater its powers of attraction. Simple and profound. Einstein was nothing if not that! Armed with this model, it is but natural to conclude that objects which are so plonked onto this fabric create waves that ripple across the fabric. These are the gravitational waves that EInstein’s General Relativity predicts and which are yet to be observed experimentally.

It was under this mathematical framework of general relativity that Stephen’s Hawking made his celebrated conclusion that black holes emit radiation. Whilst being a tour de force in mathematical reasoning, it hasn’t won him a Nobel prize because it hasn’t being verified experimentally! And then along came Edward Witten and others and the traditional barriers between mathematics and physics have all but dissolved.