7.01c Pigeonhole principle

1 Alfred, Ben, Charles and David meet, and some handshaking takes place.

• Alfred shakes hands with David.
• Ben shakes hands with Charles and David.
• Charles shakes hands with Ben and David.
  1. Complete the bipartite graph in your answer book showing A (Alfred), B (Ben), C (Charles) and D (David), and the number of people each shakes hands with.
  2. Explain why, whatever handshaking takes place, the resulting bipartite graph cannot contain both an arc terminating at 0 and another arc terminating at 3 .
  3. Explain why, whatever number of people meet, and whatever handshaking takes place, there must always be two people who shake hands with the same number of people.

2 Mo eats exactly 6 doughnuts in 4 days.

1. What does the pigeonhole principle tell you about the number of doughnuts Mo eats in a day? Mo eats exactly 6 doughnuts in 4 days, eating at least 1 doughnut each day.
2. Show that there must be either two consecutive days or three consecutive days on which Mo eats a total of exactly 4 doughnuts. Mo eats exactly 3 identical jam doughnuts and exactly 3 identical iced doughnuts over the 4 days.
   The number of jam doughnuts eaten on the four days is recorded as a list, for example \(1,0,2,0\). The number of iced doughnuts eaten is not recorded.
3. Show that 20 different such lists are possible.

4 The first 20 consecutive positive integers include the 8 prime numbers \(2,3,5,7,11,13,17\) and 19. Emma randomly chooses 5 distinct numbers from the first 20 consecutive positive integers. The order in which Emma chooses the numbers does not matter.

1. Calculate the number of possibilities in which Emma's 5 numbers include exactly 2 prime numbers and 3 non-prime numbers.
2. Calculate the number of possibilities in which Emma's 5 numbers include at least 2 prime numbers. The pairs \(\{ 3,13 \}\) and \(\{ 7,17 \}\) each consist of numbers with a difference of exactly 10 .
3. Calculate the number of possibilities in which Emma's 5 numbers include at least one pair of prime numbers in which the difference between them is exactly 10 . A new set of 20 consecutive positive integers, each with at least two digits, is chosen. This set of 20 numbers contains 5 prime numbers.
4. Use the pigeonhole principle to show that there is at least one pair of these prime numbers for which the difference between them is exactly 10 .

1 Sam is packing for a holiday. The table shows the mass of each item to be packed. Sam's bags can each carry 10 kg , but no more.

1. Use first-fit to show a possible packing that Sam could use. Indicate the items by using the letters \(A , B , \ldots\) rather than their masses. The total mass of the 8 items is 39.5 kg . Sam says that this means they can be packed using just 4 bags.
2. Explain why Sam cannot pack the items using just 4 bags. Sam is only allowed to take 4 bags. Each item is given a value out of 20 representing how important it is to Sam.

   Item	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)	\(H\)
   Mass (kg)	3	4	3.5	2.5	6	7.5	8	5
   Value	6	10	12	10	16	12	20	14

3. Sam wishes to pack items with a large total value.

3 Six people play a game with 150 cards. Each player has a stack of cards in front of them and the remainder of the cards are in another stack on the table.

1. Use the pigeonhole principle to explain why at least one of the stacks must have at least 22 cards in it. The set of cards is numbered from 1 to 150 . Each digit '2', '3' and '5', whether as a units digit or a tens digit, is coloured red.
   So, for example
   The cards are put into a Venn diagram with three intersecting sets: \(\mathrm { A } = \{\) cards with a number that is a multiple of \(2 \}\) \(\mathrm { B } = \{\) cards with a number that is a multiple of \(3 \}\) \(\mathrm { C } = \{\) cards with a number that is a multiple of \(5 \}\) For example

5

1. How many arcs does the complete bipartite graph \(K _ { 5,5 }\) have? A subgraph of \(K _ { 5,5 }\) contains 5 arcs joining each of the elements of the set \(\{ 1,2,3,4,5 \}\) to an element in a permutation of the set \(\{ 1,2,3,4,5 \}\). Suppose that \(r\) is connected to \(p ( r )\) for \(r = 1,2,3,4,5\).
2. How many permutations would have \(p ( 1 ) \neq 1\) ?
3. Using the pigeonhole principle, show that for every permutation of \(\{ 1,2,3,4,5 \}\), the product \(\Pi _ { r = 1 } ^ { 5 } ( r - p ( r ) )\) is even (i.e. an integer multiple of 2, including 0 ).
4. Is the result in part (iii) true when the permutation is of the set \(\{ 1,2,3,4,5,6 \}\) ? Give a reason for your answer.

1 A set consists of five distinct non-integer values, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E . The set is partitioned into non-empty subsets and there are at least two subsets in each partition.

1. Show that there are 15 different partitions into two subsets.
2. Show that there are 25 different partitions into three subsets.
3. Calculate the total number of different partitions. The numbers 12, 24, 36, 48, 60, 72, 84 and 96 are marked on a number line. The number line is then cut into pieces by making cuts at \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E , where \(0 < \mathrm { A } < \mathrm { B } < \mathrm { C } < \mathrm { D } < \mathrm { E } < 100\).
4. Explain why there must be at least one piece with two or more of the numbers 12, 24, 36, 48, 60, 72, 84 and 96.

50 people are at a TV game show. 21 of the 50 are there to take part in the game show and the others are friends who are in the audience, 22 are women and 20 are from London, 2 are women from London who are there to take part in the game show and 15 are men who are not from London and are friends who are in the audience.

1. Deduce how many of the 50 people are in two of the categories 'there to take part in the game show', 'is a woman' and 'is from London', but are not in all three categories. [3]

The 21 people who are there to take part in the game show are moved to the stage where they are seated in two rows of seats with 20 seats in each row. Some of the seats are empty.

1. Show how the pigeonhole principle can be used to show that there must be at least one pair of these 21 people with no empty chair between them. [2]

The 21 people are split into three sets of 7. In each round of the game show, three of the people are chosen. The three people must all be from the same set of 7 but once two people have played in the same round they cannot play together in another round. For example, if A plays with B and C in round 1 then A cannot play with B or with C in any other round.

1. By first considering how many different rounds can be formed using the first set of seven people, deduce how many rounds there can be altogether. [3]