Pigeonhole principle applications

2 King Elyias has been presented with eight flagons of fine wine. Intelligence reports indicate that at least one of the eight flagons has been poisoned. King Elyias will have the wine tasted by the royal wine tasters to establish which flagons are poisoned. Samples for testing are made by using wine from one or more flagons. If a royal wine taster tastes a sample of wine which includes wine from a poisoned flagon, the taster will die. The king has to make a very generous payment for each sample tasted. To minimise payments, the royal mathematicians have devised the following scheme:
Test a sample made by mixing wine from flagons \(1,2,3\) and 4.
If the taster dies, then test a sample made by mixing wine from flagons \(5,6,7\) and 8 .
If the taster lives, then there is no poison in flagons \(1,2,3\) or 4 . So there is poison in at least one of flagons 5, 6, 7 and 8, and there is no need to test a sample made by mixing wine from all four of them. If the sample from flagons \(1,2,3\) and 4 contains poison, then test a fresh sample made by mixing wine from flagons 1 and 2, and proceed similarly, testing a sample from flagons 3 and 4 only if the taster of the sample from flagons 1 and 2 dies. Continue, testing new samples made from wine drawn from half of the flagons corresponding to a poisoned sample, and testing only when necessary.

1. Record what happens using the mathematicians' scheme when flagon number 7 is poisoned, and no others.
2. Record what happens using the mathematicians' scheme when two flagons, numbers 3 and 7, are poisoned.

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.

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

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.