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.
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 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.
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 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.
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
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 .
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 , 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.)
Show that .
We will count the number of ways of putting distinct objects into distinct boxes.
First, we label the boxes as and .
The first way to count is to consider object-by-object: each object can be put into either box or box .
Since there are objects, total number of ways . The second way to count is to consider the number of objects put into box .
There is ways to put objects into box , ways to put object, ..., and ways to put objects.
Total number of ways .
Show that the number of people who have an odd number of friends on Facebook must be even.
[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 ?
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 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.