Making It Count: Counting the complement « The Mumbling Mathematician

July 23, 2008

Making It Count: Counting the complement

Filed under: Uncategorized — zetahype @ 1:21 am

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 $\leq p^n$ have no factors (other than 1) in common with $p^n$ ?
Solution: For $2^3$ 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 $2^6$ or $3^5$ . Instead, we count the number of integers that do have a factor in common with $p^n$ . Ironically, we can list them out every time! They are just p, 2p, 3p, 4p,…, $p^{n-1}$ p. There are $p^{n-1}$ of them and so, by the principle, exactly $p^n-p^{n-1}=p^{n-1}(p-1)$ non-negative positive integers $\leq p^n$ 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 $\varphi(N)$ for N positive and defined as the number of non-negative integers $\leq$ N and relatively prime to it. The function is multiplicative, which means that if $N=\prod_{i=1}^{k}p_i^{e_i}$ then $\varphi(N) = \varphi(\prod_{i=1}^{k}p_i^{e_i}) = \prod_{i=1}^{k}\varphi(p_i^{e_i}) = \prod_{i=1}^{k}p_i^{e_i-1}(p_i-1)$ from the above computation.