WACEhub

ACARA

The pigeon-hole principle:

solve problems and prove results using the pigeon-hole principle. (ACMSM006)

The pigeon-hole principle:

If we have n+1 or more objects placed in n boxes then there must be at least two objects in one box.

Pigeon nesting holes in Spain

http://en.wikipedia.org/wiki/File:Palomares_7.jpghttp://www.youtube.com/watch?v=DBLiH3jgrI8

For example if you have 7 pigeons to go in 6 boxes then there must two pigeons in one box.

Example 1

How many people do you have to have in a room to ensure at least two of the people were born on the same day of the week?

The worst case scenario is that the first seven people were each born on a different day of the week. Therefore you need 8 people, as the 8th person will have to be born on the same day as one of the other seven. If the seven were not born on different days, then you have at least two people born on the same day of the week.

Example 2

How many times would you need to roll a die before the number on the upper face is repeated?

There are six possibilities. The “pigeon-holes” are {1, 2, 3, 4, 5, 6}.

If the first roll resulted in say a 4, then the next five rolls could all be different. You would need to roll the dice 7 times to guarantee a repeated number. i.e. seven “pigeons”.

Example 3

Explain why there are at least two students at your school with the same birthday (assuming the school has more than 365 students!)

The “worst” case scenario is that the first 365 students were born on different days.The “pigeon-holes” are the 365 students with different birthdays.

If there are 366 students, then two of them must share a birthday. (It is actually more likely that several of them share birthdays.)

If there are more than 365 students, then several of them must share a birthday (unless it is a leap year!).

Example 4

Explain why the local council library most likely will have at least two books with the same number of pages.

Assume the local council library has at least 2000 books. If each of the books has 1, 2, 3, … or 2000 pages,it is highly likely that another book at the library will have less than 2000 pages, so there will be two books with the same number of pages. The “pigeon-holes” are 1, 2, 3, …2000.

Example 5

(a) How many people do you need if it can guarantee that at least two of them have a birthday in the same month?

(b) How many people do you need if it can guarantee that at least two of them have a birthday on the same day?

(a) There are 12 months in a year. It is possible for 12 people to have a birthday in each of the different months. If there are 13 people, then at least two have a birthday in the same month.

(b) 366 (unless it is a leap year and then you need 367).

Example 6

(a) Ten schools each send two representatives to represent them in a leadership camp. How many of the representatives need to be chosen for one of the activities to guarantee that at least two of them come from the same school?

(b) Five married couples have been friends for years. They go out to a revolving restaurant which is on the top of a tall building. How many people need to go into the elevator together to ensure there is at least one married couple in the group?

(a) The worst case scenario is that there is exactly one representative from each school in a group of 10. If one more person joins them, then at least one school is represented by two people. Therefore you 11 representatives to be chosen for the activity to ensure you have two representatives from the one school.

(b) If one person from is couple is in the group, then it is possible for five people to go into the elevator with no couple being present. If six people go together in the elevator, then there must be amongst them at least one married couple. (There could be three married couples!)

Therefore to ensure there is at least one married couple in the elevator, you need six people.

Example 7

There are six people in a room. Some know each other, some do not. Show that there are at least two people who know the same number of people.(It is assumed that is Anne knows Jim, then Jim knows Anne.)

If each of the six knows a different number of people, then there is one person who knows all five others and one person who knows no-one. This is a contradiction (if the one who knows everyone, John, knows the one who knows no-one, Bill, then Bill does NOT know no-one as if John knows Bill, then Bill knows John.)

Therefore, the six do not know a different number of people.i.e. there are at least two people who know the same number of people.

Challenge

There are n people in a room. Some know each other, some do not. Show that there are at least two people who know the same number of people.

as above: if among n, John & Bill contradiction

Example 8

There are 2 children in the Smith family, 3 in the Lee family and 5 in the James family.

(a) How many children must be chosen at random from the families to ensure that there is at

least one pair of siblings?

(b) How many children must be chosen at random from the families to ensure that

all the children from at least one family are chosen?

(a) Worst case: You have one child from each family i.e. three children. If another child is

chosen, he will have to belong to one of the families, so you have a pair of siblings.

This means you need 4 children to be chosen.

(It is possible to have a pair of siblings choosing just two children, but not guaranteed.)

(b) The worst case scenario is if you chose one child from the Smith family, 2 from the Lee family and 4 from the James family, i.e. you have 7 children and still do not have all the children from one family. Choose one more child. The 8th child will ensure that at least all the children from one family were chosen.

Remember it is possible to obtain your objective of all the children of one family being chosen in less choices, but not guaranteed. eg You only need two choices if both are from the Smith family!

2 3 5

Method 1: SS LLL JJJJJ

selections (worst case until assured)

S L J L J J J one more and one family is complete

need (at least) 8 choices

Method 2:

Largest family 5 – 1 = 4

Middle size family 3 – 1 = 2

Smallest family 2 – 1 = 2

7 choices before all of one family is complete

need (at least) 8 choices

Example 9

If six different numbers are chosen from the integers {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} prove that two of them add to 11.

There are five pairs of numbers that add to 11, 1 + 10, 2 + 9,….., 5 + 6.

It is possible to select two that immediately add to 11, but the worst case is if you pick five where you have one of each pair that add to 11.

If you chose one more number, then is must be the other half of one of the pairs.

Therefore two of the numbers add to 11.

Therefore, if six different numbers are chosen, two of them will add to 11.

Challenge

If n+1 distinct numbers are selected from the integers {1, 2, 3, 4, ….., 2n}, show that there is (at least) one pair of them that must add to 2n+1.

Example 9 – Challenge

If n + 1 distinct integers are chosen from {1, 2, 3, …,n, n + 1, …, 2n} show that there are at least one pair of them whose sum is 2n + 1.

Solution:

There are n pairs which Σ to 2n + 1.

worst case scenario: could choose n integers (one from each pair that adds to 2n+1)

so that none (no pair) Σ to 2n + 1.

but, 1 more choice will give a matching pair such that they Σ to 2n + 1 (one of ‘n’ possible pairs from the original set).

Therefore if n + 1 distinct integers are chosen from 1 to 2n, then there are at least one pair of them whose sum is 2n + 1.

Example 10

If there are five points inside or on a unit square (sides equal to 1), prove that there are two of them that are or less apart.

Split the square into four equal parts.

Worst case: Put one point in each of the smaller squares. The fifth point must go into one of the four small squares.

The maximum distance apart of any two points in the same square

is the diagonal length

i.e.

Therefore the maximum distance apart is .i.e. two of the points must be or less apart.

Solution:

If four points are selected within or on a unit circle, then there are two points whose distance apart is less than or equal to .

Challenge

Given an equilateral triangle of side two, how many points within the triangle must be selected so that the distance between two of them is less than one?

Solution to Challenge 10: Choose the vertices A, B, C. These are two units apart.

Choose the intersection point of the medians O.

The longest distance from O to any point in the triangle is the distance from O to to a vertex say A i.e. because the length of the median is and medians trisect each other.

The shortest distance to another point from O or A is SO where S is on the perpendicular bisector of A and AS = OS.

.

Then, given an equilateral triangle of side two, five within the triangle must be selected so that the distance between two of them is less than one.

Example 11

If 7 integers are selected from {1, 2, 3, 4,….., 10}, then the selection contains two integers a and b such that a – b = 2.

The numbers that have this property are {3, 1},{4, 2}, {5, 3}, {6, 4}, {7, 5}, {8, 6}, {9, 7} and {10, 8}.

The “pigeons” are {1, 2, 3, 4, ….., 10}

The“pigeon-holes”are {1, 2, 5, 6, 9, 10}

When selecting the 7 integers, the worst case is when the set {1, 2, 5, 6, 9, 10} is chosen first.

Only one of the remaining pigeons, i.e. 3, 4, 7 or 8 needs to be chosen. It will fit in one of the pigeon holes so that the two elements have a difference of two.

Therefore if 7 integers are selected from {1, 2, 3, 4,….., 10}, then the selection contains two integers a and b such that a – b = 2.

Exercise

Show that if 7 integers are selected from among {1, 2, 3, …..12} then the selection includes two integers a and b such that b = a + 1.

Solution:

The worst scenario is first selecting the numbers 1, 3, 5, 7, 9 and 11 (or the numbers 2, 4, 6, 8, 10 and 12). The next number to be selected is an even number so that the relationship

b = a + 1 applies.

Challenge

Show that if n+1 integers are selected from among {1, 2, 3, …..2n} then the selection includes two integers a and b such that b - a =1.

Solution:

The worst scenario is first selecting the numbers 1, 3, 5, 7, 9,... and 2n - 1 (or the numbers 2, 4, 6, 8, 10, ... and 2n). The next number to be selected is an even number so that the relationship

b = a + 1 applies.

http://www.math.uvic.ca/faculty/gmacgill/guide/pigeonhole.pdf

Example 13

In a class of 25 people, what is the biggest number you can be sure of that have a birthday on the same weekday?

Solution :

The “pigeon-holes” are Monday, Tuesday, Wednesday, Thursday, Friday, Saturday and Sunday.

It is possible that the whole 25 people have their birthday on the same day of the week, but not guaranteed.

Take the average (i.e. the worst possible spread of birthdays) =

If some days had less people having birthdays on that day, then other days had more.

The biggest number you can guarantee, out of a class of 25, having a birthday on the same day is 4, as there is a remainder when finding the average some must have more than 3. (If there happen to be 5, then there are still 4 people with a birthday on that day.)

Example 14

At a Junior Soccer Club caters for 10, 11, 12, 13 or 14 years olds. The club has 40 members. What is the biggest number of members you can be sure of that can

(a) have their first names starting with the same letter.

(b) have their birthdays in the same month of the year.

(c) be the same age.

(d) have the same hair colour given their hair is black, brown or blonde.

Solution :

(a)

(b)

(c)

(d)

Exercises

1. In a year group of 200, what is the biggest number you can be sure of that have a birthday

in the same month?

2. How many words must be chosen from a random page of a novel to ensure your selection

contains two words that start with the same letter?

3. Perth Concert Hall has seating for 1729 patrons. Show that in a full Concert Hall, there must be at least two people that have the same initials for both surname and first name.

4. How many cards do you have to select from a pack of cards to ensure you have

(a) two cards of the same suit?

(b) two cards with the same number (or two jacks, queens or kings)?

5. Little Nicky sneaks out at night to the pantry to take two cakes – one for herself and one for her little brother who wants to eat exactly the same as her. If there are 5 chocolates cakes and 7 raspberry cakes, how many does Nicky have to take to guarantee she has two the same?

6. If 2500 fans attend a football match, what is the least number of fans that can be guaranteed to share a birthday?

7. Consider the integers {1, 2, 3, ……14}. If eight of the numbers are chosen at random, show that two of them must add to 15.

8. A box of toys contains 3 dolls, 4 trains and 2 teddy bears. A selection of all the toys of one type is required. How many toys need to be selected (at random) before it is ensured that all of one type is selected?

Solutions:

1. so 17

2. The worst case is when you have 26 words each starting with the same letter, so 27.

3. The number of different combinations for two letters is 2626 = 676.

If there are 677 people in the Perth Concert Hall, then at least two of them have the same initials for both surname and first name.

4. (a) 5

(b) 14

5. 3

6. 366

7. Given {1, 2, 3, ……14}, the numbers that add to 15 are

1 + 14, 2 + 13, 3 + 12, 4 + 11, 5 + 10, 6 + 9, 7 + 8.

The worst case scenario is one number taken from each pair. This uses7 number. The eighth number must have
“its partner” to add to 15, already selected.

Therefore, if eight of the numbers are chosen at random, then two of them must add to 15.

8. The worst case is where 2 dolls, 3 trains and 1 teddy bear is chosen. If one more toy is selected, then you can be ensured that all of one type is selected. i.e. need to select 6 toys.

There are some very nasty questions at http://www.cut-the-knot.org/do_you_know/pigeon.shtml

An excellent site for background (and test questions) at

http://www.jamestanton.com/wp-content/uploads/2013/01/Microsoft-Word-UNIT-20_Pigeonhole-Principle.pdf

Other sites:

http://www.jamestanton.com/?cat=6

This is an encyclopedia of Maths at a high enough level for Specialist Maths!!! This site has a wealth of very useful stuff. His videos are very clear and voice pleasant and easy to understand. Try this one …easy, brilliant and brief. Medians of a Triangle

http://mindyourdecisions.com/blog/2008/11/25/16-fun-applications-of-the-pigeonhole-principle/#.Un7qYCdi3pc

Kindly proofed and extra suggestions by Dr Dennis Ireland and his staff at MLC.