## The Pigeon Hole Principle

Below the cut are some pigeon hole related questions I collected together for a Math Circle at the Fields Institute.

Theorem 1 (Finite Pigeon Hole Principle)If one has pigeons and in holes then there is a hole with at least pigeons in it where is the largest integer greater than

So — If we have 10 pigeons and three holes there are going to be pigeons in one uncomfortable hole. This kind of finite pigeon hole argument is tremendously useful.

The following facts, equivalent to the Pigeon Hole Principle, were noted by Dijkstra in EWD980.

Theorem 2If there are more than pigeons in holes, then there is a hole with more than pigeons.

Theorem 3If each hole as at most one pigeon, then the number of holes is at most the number of pigeons.

Theorem 4The maximum of a finite set of numbers is at least the average.

Many of the exercises below are drawn from Mind Your Decisions and Cut the Knot. Some are original and some are folklore. All the mistakes are my own.

**1. Arithmetic **

Exercise 1Show that there are a lot of people with the same number of strands of hair.

Exercise 2You have a drawer filled with fifty white socks and fifty black socks. How many socks do you need to take from the drawer to make sure that you have a matching pair of socks? (Assume you can’t see the socks in drawer when you pull them out.)

Exercise 3Suppose you have 10 consecutive integers. Show that there have to be: five which are divisible by two, three which are divisible by three, two which are divisible by four, and one which is divisible by five.

Exercise 4If you pick six numbers from there must be a pair that adds up to eleven.

Note that are the only pairs that add up eleven. If you pick six distinct numbers from you must have two in the same pair.

Exercise 5Suppose you pick ten numbers . Show that you can pick two disjoint subsets of with the same sum.

What is the largest a sum of a subset could possibly be?

How many non-empty subsets of are there?

So — There have be two subsets with the same sum.

Exercise 6Suppose there is a large number of people at a math circle. Suppose that “knowing someone” is symmetric (If Alice knows Bob then Bob knows Alice) and irreflexive (No one knows themself.) Show that there are two people know the same number of people.

Suppose there are people. Let denote the th person and denote the number of people that knows. We then have that . These solutions come from Cut The Knot

*Vitaly Bergelson*: Suppose is maximal. If everyone has a distinct number of friends then each friend of has to have more than one friend and fewer than friends.

*Alexander Bogomolny*: If then for any . If then for any . In either case, we have values of from numbers. If we have values of from numbers.

**2. “Chess” **

Exercise 7A seven-by-seven chess board is filled with knights. Is it possible for them to all move at the same time in such a way that they all land on different squares? (A knight moves two spaces horizontally or vertically then makes a left or right turn and moves one more spaces.)

Exercise 8What is the maximum number of rooks that you can place on an eight-by-eight chess board such that no rook is attacking another rook? (A rook attacks everything in the same row or column as it.)

Exercise 9What is the maximum number of pawns that you can place on an eight-by-eight chess board such that no pawn is attacking another pawn? (A pawn attacks the two spaces immediately “north-east” and “north-west” of it.)

**3. Geometry **

Exercise 10 (Putnam, 2002-A2)If you draw more than five points on a sphere then there is a closed hemisphere containing more than four points.

Exercise 11Any set of seven points a circle of unit radius contains a pair which are at most one unit apart?

*Question*: Can you reduce this to six points? What about five?

Exercise 12Any set of five points in an equilateral triangle with side-length one contains a pair of points with distance at most .

Exercise 13Any set of points in the unit square contains a pair of points that are at most apart.

Exercise 14A convex pentagon with vertices on integer lattice points contains a lattice point. (A polygon is convex if the line joining any two points in the polygon is contained within the polygon.)

Mike Pawliuk: It is surprising that this also holds if we remove convexity but allow the point we’re interested in to lie on the boundary of the pentagon.

**4. Ramsey **

Exercise 15If six people all talk to each other (in pairs) about two topics then there three people who all talked to each other about the same topic.

The pencil and paper game Sim, due to Gustavus Simmons, is based off the exercise above. Draw six dots on a piece of paper. Two players, Red and Blue, alternate drawing lines of their colour joining pairs of points which have not already been joined together. A player loses if they create a triangle all of whose sides are their colour. The exercise above shows that this game cannot end in a stalemate.

Exercise 16If seventeen people all talk to each other (in pairs) about three topics then there three people who all talked to each other about the same topic.

Joseph Nebussaid, on 2012/11/19 at 23:53Reblogged this on nebusresearch and commented:

Parker Glynn-Adey here speaks some about the Pigeon Hole Principle, which is one of those little corners of mathematics whose name alone brings a smile to people’s faces. There are a couple of ways of stating the principle. The version I remember from time immemorial is that if one has N pigeons and a smaller number M of pigeon-holes, then if we’ve put all the pigeons somewhere, there must be at least one pigeon-hole with more than one pigeon. Glynn-Adey starts from a more general way of describing this situation, and goes through a couple of equivalent versions of the idea, before launching into some of the neat little puzzles that follow directly from this idea. Some of them are nicely surprising and I recommend any of the exercises as a fun pastime.