Counting

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.

Interesting Arguments

An interesting line of reasoning that I came across in my Combinatorial Theory  course is
the minimal element method.

The general outline of a proof using this method is as follows : Suppose you want to prove that a given set of elements satisfy a given property $P$. Let the set of bad elements not satisfying that property be denoted by $\mathcal{B}$. Assume that $b$ is the minimal element of $\mathcal{B}$ in some sense. Then using the assumptions of the claim, show that there exists  another element $b^\prime \in \mathcal{B}$ such that $b^\prime < b$.

Another interesting style of argumentation which is generally seen in information theoretic arguments is the probabilistic method in which a deterministic solution to a given problem is shown to exist by constructing a random candidate for a solution, and showing that this candidate solves all the requirements of the problem with positive probability.