Double Counting

The principle of Double Counting is to first count a set of objects one way, then count another way. This is best explained by looking at several examples, since there are many different ways to count.

Worked Example

1. At a party of 11 people, every person claims that they shook hands with exactly 5 other people. Show that someone is lying.

Solution: Give each person a label from $1$ to $11$. Label the handshakes from $1$ to $n$ (for the appropriate value of $n$). Consider the sets $H(i,j)$, where person $i$ participated in handshake $j$. We will count the number of $H (i,j)$ in 2 ways. Firstly, since everyone participated in 5 handshakes, there are $11 \times 5 = 55$ such values. Secondly, since every handshake involves only 2 people, there are $n \times 2 = 2n$ such values. Thus, we must have $55 = 2n,$ which is a contradiction. Thus, someone was lying.

2. Show that if we total up the number of friends that each person has on Facebook, the result is an even number.

Solution: Label the people from $1$ to $n$. Label the friendships from $1$ to $m$. Consider the sets $F(i,j)$, where person $i$ is involved in friendship $j$. Consider a particular person $I$. The number of friends person $I$ has is the number of sets of $F(I, j)$, for some $j$. Hence, the total number of friends that each person has is the total number of $F(i, j)$.

Consider a particular friendship $J$. Then, since Facebook friendship is mutual, there are exactly 2 copies of $F(i, J)$, which are associated to the 2 people that form the friendship. Hence, the total number of $F(i, j)$ is $2m$, which is even.

This is more commonly known as the Handshake Lemma.

3. In a cricket round-robin tournament with $n$ teams, each team plays each other exactly once. In each game, there is a winner and a loser. Let $W_i$ denote the number of wins of team $i$, and $L_i$ denote the number of losses of team $i$. Show that

$W_1 + W_2 + \ldots + W_n = L_1 + L_2 + \ldots L_n.$

Solution: We will count the number of games in the tournament in two ways. Let $G(i,j)$ denote a game played between teams $i$ and $j$, in which team $i$ won. First, we count the number of values of $G(i,j)$ according to the winning teams. Since team $i$ wins $W_i$ games, it follows that there are $W_1 + W_2 + \ldots + W_n$ such values of $G(i,j)$.

Now, we count the number of values of $G(i,j)$ according to the losing teams. Since team $i$ lost $L_i$ games, it follows that there are $L_1 + L_2 + \ldots + L_n$ such values of $G(i,j)$.

Hence, these two sums are equal. Furthermore, this sum is equal the total number of games played, which is $\frac {n (n-1)}{2}$.

4. Consider a 3 by 9 board, in which each square is colored either red or blue. Show that there exists 2 (not necessarily consecutive) rows and 2 (not necessarily consecutive) columns, whose intersection gives 4 squares of the same color.

Solution: Proof by contradiction. Denote the column number by $j$, and denote the pair of row numbers by $I = \{ r_1, r_2\}$. We will count the number of $X ( I, j)$, in which the squares in the given rows and columns have the same color.

First, count according to columns $(j)$. Since there are three squares in each column, the pigeonhole principle implies at least two of the squares must have the same color. Since there are nine columns, $| X(I, j)| \geq 9$.

Now, count according to row pairs $(I)$. By assumption, no two rows and two columns give four squares of the same color. Thus, each pair of rows has at most one pair of red-red squares in the same column, and at most one pair of blue-blue squares in the same column. Since there are three pairs of rows, there are at most $3 \times 2 = 6$ such pairs. Thus, $| X(I, j)| \leq 6$. Since $|X(I,j)| \leq 6 < 9 \leq |X(I,j)|$, we have a contradiction.

Note: We could also solve this problem using the pigeonhole principle. There are $2^3 = 8$ different ways to color a column of 3 squares with red and blue. Hence, there must be 2 columns with the same color configuration. By the pigeonhole principle, at least 2 squares in this column are the same color. Hence, this gives us the 2 rows that we want. We can tighten this to a 3 by 7 board (since $6 \not \geq 7$) using the double counting argument, and the pigeonhole argument would no longer be applicable. This is the best bound, as we can create a 3 by 6 board where the squares are colored with 2 colors, and no such configuration of rows and columns exist (Out of the 8 possible combinations, take the 6 which have only 2 squares colored with the same color.)

Test Yourself

1) Show that $2^n = { n \choose 0} + {n \choose 1} + {n \choose 2} + \ldots + { n \choose n }$.

2) Show that the number of people who have an odd number of friends on Facebook must be even.

3)* [France] In an international meeting of $n \geq 3$ participants, 14 languages are spoken. We know that any 3 participants speak a common language, and no language is spoken by more than half of the participants. What is the least value of $n$?