×

# 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
3 years, 8 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}$$

Sort by:

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

- 3 years, 6 months ago

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 - 3 years, 6 months ago

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$$.

- 3 years, 6 months ago

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?

- 3 years, 6 months ago

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

Staff - 3 years, 6 months ago

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).

- 3 years, 6 months ago

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

- 3 years, 7 months ago

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.

- 3 years, 6 months ago

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.

- 3 years, 5 months ago