# 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

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$

## Test Yourself

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

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$.Show that the number of people who have an odd number of friends on Facebook must be even.

[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$?

## Double Counting - Problem Solving

At a party, each person brings 1 packet of sweets and 1 chocolate bar. The packets of sweets and the chocolate bars have to be shared out among the people at the party such that each person gets one (whole) packet of sweets and one (whole) chocolate bar, but no one gets the sweets or chocolate that they brought with them. If there are 7 people at the party, how many ways are there to do this?

**Details and Assumptions:**

- The sweets and chocolate bar that each person brings is different from the sweets and chocolate bar that anyone else brings.

###### Image Credit: Wikimedia Candies

Your math professor shows you 100 coins placed on his desk with their heads up.

He says to you, "Each time, you choose exactly 93 coins and flip them, turning heads to tails or vice versa."

What is the least number of times that you need to do this in order to get all 100 coins tails up?

###### Image credit: Wikipedia KamTANGO

Find the largest number of rooks that can be placed in a $3000 \times 3000$ chessboard in such a way that each rook is threatened by no more than one rook.

**Details and Assumptions:**

- Rooks can attack in any range but can only attack in a horizontal or vertical direction.
- A rook is considered to be "threatened" if another rook can attack it.

**Cite as:**Double Counting.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/double-counting-definition/