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.
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 to . Label the handshakes from to (for the appropriate value of ). Consider the sets , where person participated in handshake . We will count the number of in 2 ways. Firstly, since everyone participated in 5 handshakes, there are such values. Secondly, since every handshake involves only 2 people, there are such values. Thus, we must have 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 to . Label the friendships from to . Consider the sets , where person is involved in friendship . Consider a particular person . The number of friends person has is the number of sets of , for some . Hence, the total number of friends that each person has is the total number of .
Consider a particular friendship . Then, since Facebook friendship is mutual, there are exactly 2 copies of , which are associated to the 2 people that form the friendship. Hence, the total number of is , which is even.
This is more commonly known as the Handshake Lemma.
3. In a cricket round-robin tournament with teams, each team plays each other exactly once. In each game, there is a winner and a loser. Let denote the number of wins of team , and denote the number of losses of team . Show that
Solution: We will count the number of games in the tournament in two ways. Let denote a game played between teams and , in which team won. First, we count the number of values of according to the winning teams. Since team wins games, it follows that there are such values of .
Now, we count the number of values of according to the losing teams. Since team lost games, it follows that there are such values of .
Hence, these two sums are equal. Furthermore, this sum is equal the total number of games played, which is .
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 , and denote the pair of row numbers by . We will count the number of , in which the squares in the given rows and columns have the same color.
First, count according to columns . 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, .
Now, count according to row pairs . 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 such pairs. Thus, . Since , we have a contradiction.
Note: We could also solve this problem using the pigeonhole principle. There are 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 ) 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.)
1) Show that .
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 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 ?