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

Note by Calvin Lin
5 years, 3 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $ ... $ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

## Comments

Sort by:

Top Newest

For number 3, wouldn't the formula for the sum of the total number of games played be n*(n-1)/2?

- 5 years, 1 month ago

Log in to reply

Thanks. I've updated that typo.

Given the setup, show that

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

Staff - 5 years, 1 month ago

Log in to reply

Problem (3). Assume that there are $n$ participants. Consider a table with rows indexed by triples of distinct participants $(P_i,P_j,P_k)$ and Columns indexed by the languages. An entry in the table is 1 if the corresponding row triples speak the common language specified by the column and is zero otherwise. Now count total number of ones $S$ in the table. Since there is at least a single one per row, we have $S\geq \binom{n}{3}$. On the other hand, since at most $\frac{n}{2}$ participants speak in any language, number of ones in each column is upper bounded by $\binom{n/2}{3}$. Since there are 14 columns, we have $S\leq 14 \binom{n/2}{3}$. Combining the above upper and lower bound, we conclude $n\geq 8$.

- 5 years, 1 month ago

Log in to reply

Sorry, I don't understand why there is at least a single one per row. I thought it's strictly one per row, since any 3 participants speak a common language. Does that mean at least one common language?

- 5 years, 1 month ago

Log in to reply

Of course, it remains to show that 8 is actually achievable, in order to conclude that it is the minimum.

Staff - 5 years, 1 month ago

Log in to reply

That should not be difficult. We have $\binom{8}{3}=56$ triples and $14$ languages. We evenly assign each triple to all languages in a such a way that a given language is assigned to four triples consisting of four different participants (there are $\binom{4}{3}=4$ such available triples, and hence this is possible).

- 5 years, 1 month ago

Log in to reply

By the way, The Handshake Lemma is proved easily by induction.

Let m be the number of Friendships on Facebook

For m = 1, Clearly the total number of everyone's friends is 2.

Let it be true that for some n, and m=n, the total number of friends are even.

When one more friendship is made: The two persons involved in it gain a friend each. Hence the total gain is two friends and the total number of friends is again even.

Hence, it is true for n+1

Thus, for any countable natural number of frienships, the Handshake Lemma has been proved

Staff - 5 years, 2 months ago

Log in to reply

Can you prove it more visually, e.g., counting the number of edges in a graph and relating it to the sum of degrees of nodes ? It is a basic result from Graph theory.

- 5 years, 1 month ago

Log in to reply

Yes; essentially all of these are equivalent to the well-known theorem $2E=\sum d$, or the sum of the degrees of each vertex is two times the number of edges.

- 5 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...