Waste less time on Facebook — follow Brilliant.
×

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 ago

No vote yet
1 vote

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? Bhagirath Mehta · 2 years, 9 months ago

Log in to reply

@Bhagirath Mehta 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. \] Calvin Lin Staff · 2 years, 9 months 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\). Abhishek Sinha · 2 years, 9 months ago

Log in to reply

@Abhishek Sinha 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? Siao Chi Mok · 2 years, 9 months ago

Log in to reply

@Abhishek Sinha Of course, it remains to show that 8 is actually achievable, in order to conclude that it is the minimum. Calvin Lin Staff · 2 years, 9 months ago

Log in to reply

@Calvin Lin 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). Abhishek Sinha · 2 years, 9 months 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 Agnishom Chattopadhyay · 2 years, 10 months ago

Log in to reply

@Agnishom Chattopadhyay 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. Abhishek Sinha · 2 years, 9 months ago

Log in to reply

@Abhishek Sinha 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. Sunay Joshi · 2 years, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...