## The Pigeon Hole Principle

Posted in Uncategorized by pgadey on 2012/11/17

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 ${n}$ pigeons and in ${k}$ holes then there is a hole with at least ${\lceil n/k \rceil}$ pigeons in it where ${\lceil x \rceil}$ is the largest integer greater than ${x}$

So — If we have 10 pigeons and three holes there are going to be ${\lceil 10/3 \rceil = 4}$ 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 2 If there are more than ${nk}$ pigeons in ${n}$ holes, then there is a hole with more than ${k}$ pigeons.

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

Theorem 4 The 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 1 Show that there are a lot of people with the same number of strands of hair.

Exercise 2 You 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 3 Suppose 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 4 If you pick six numbers from ${\{1, 2, \dots, 10\}}$ there must be a pair that adds up to eleven.

Note that ${\{1,10\}, \{2,9\}, \{3,8\}, \{4,7\}, \{5,6\}}$ are the only pairs that add up eleven. If you pick six distinct numbers from ${\{1., \dots, 10\}}$ you must have two in the same pair.

Exercise 5 Suppose you pick ten numbers ${S \subset \{1, \dots, 100\}}$. Show that you can pick two disjoint subsets of ${S}$ with the same sum.

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

$\displaystyle 90 + 91 + \dots + 100 < 1000$

How many non-empty subsets of ${S}$ are there?

$\displaystyle 2^{|S|} - 1 = 1023$

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

Exercise 6 Suppose 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 ${N}$ people. Let ${P_i}$ denote the ${i}$th person and ${n_i}$ denote the number of people that ${P_i}$ knows. We then have that ${0 \leq n_i \leq N-1}$. These solutions come from Cut The Knot

Vitaly Bergelson: Suppose ${n_i = K}$ is maximal. If everyone has a distinct number of friends then each friend of ${P_i}$ has to have more than one friend and fewer than ${K}$ friends.

Alexander Bogomolny: If ${n_1 = 0}$ then ${n_i \neq N-1}$ for any ${i}$. If ${n_1 = N-1}$ then ${n_i \neq N-1}$ for any ${i}$. In either case, we have ${N-1}$ values of ${n_i}$ from ${N-2}$ numbers. If ${n_1 \neq 0, N-1}$ we have ${N-1}$ values of ${n_i}$ from ${N-2}$ numbers.

2. “Chess”

Exercise 7 A 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 8 What 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 9 What 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 11 Any 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 12 Any set of five points in an equilateral triangle with side-length one contains a pair of points with distance at most ${1/2}$.

Exercise 13 Any set of ${n^2 + 1}$ points in the unit square contains a pair of points that are at most ${\sqrt{2}/n}$ apart.

Exercise 14 A 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 15 If 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 16 If 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.

Tagged with: , , ,