Much of information and coding theory involves counting and combinatorial reasoning. For example how many non-touching balls of unit radius can fit in an n-dimensional space ${\mathcal{F}_2}^n$. Combinatorial arguments come in very handy in these situations. The probabilistic method is another example of the kind of arguments I came across in information theory literature. One good non-technical example that changed the way I count is -
Q. Consider a group of $2^6 = 64$ tennis players. These players are now matched pairwise and the losers are eliminated from the pool. From the remaining pool of victors, players are paired again and the process is continued. How many games are required to find a single winner?
A. 63
Method 1. One way (the straightforward method atleast before reading the alternate way) to compute the answer is to count the number of matches in each round i.e. 32 + 16 + 8 + 4 + 2 + 1 = 63.
Method 2. Realize that each match eliminates 1 player, hence to eliminate 63 players you need 63 matches.
Q. Consider a group of $2^6 = 64$ tennis players. These players are now matched pairwise and the losers are eliminated from the pool. From the remaining pool of victors, players are paired again and the process is continued. How many games are required to find a single winner?
A. 63
Method 1. One way (the straightforward method atleast before reading the alternate way) to compute the answer is to count the number of matches in each round i.e. 32 + 16 + 8 + 4 + 2 + 1 = 63.
Method 2. Realize that each match eliminates 1 player, hence to eliminate 63 players you need 63 matches.
No comments:
Post a Comment