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.

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

---

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. \(_\square\)

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

---

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. \(_\square\)

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 + \cdots + W_n = L_1 + L_2 + \cdots+ L_n.\]

---

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 + \cdots + 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 + \cdots + 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} \). \(_\square\)

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.

---

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. \(_\square\)

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.) \(_\square\)

1. Show that \( 2^n = \dbinom{n}{0} +\dbinom{n}{1} + \dbinom{n}{2} + \cdots + \dbinom{n}{n} \).

   Solution

   We will count the number of ways of putting \(n\) distinct objects into \(2\) distinct boxes.
   First, we label the boxes as \(1\) and \(2\).
   The first way to count is to consider object-by-object: each object can be put into either box \(1\) or box \(2\).
   Since there are \(n\) objects, total number of ways \(=2^n\). The second way to count is to consider the number of objects put into box \(1\).
   There is \(\dbinom n0\) ways to put \(0\) objects into box \(1\), \(\dbinom n1\) ways to put \(1\) object, ..., and \(\dbinom nr\) ways to put \(r\) objects.
   Total number of ways \(=\dbinom n0 + \dbinom n1 + \dbinom n2 + \cdots + \dbinom nn\).

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\)?