The Pigeonhole Principle

Put more things than boxes into the boxes and some box gets two. That is the whole principle, and the skill is in choosing the boxes. Here are three problems where the boxes are hidden: pick the numbers or colour the links yourself, and the page shows which box overflowed.

Worked example — The Pigeonhole Principle

Numbers against boxes	a collision is forced
Box holding two	5 \| 10
box 9	9
box 11	11
box 13	13
box 15	15

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — The Pigeonhole Principle

The pigeonhole principle: if N things are put into k boxes and N > k, some box holds at least two. More precisely, some box holds at least ⌈N/k⌉, the smallest whole number that is at least N/k.

What each symbol means

N: the number of things placed
k: the number of boxes
⌈N/k⌉: N/k rounded up: the least the fullest box must hold

Where the formula comes from

Why ⌈N/k⌉. If every box held fewer than N/k things, the k boxes together would hold fewer than k × N/k = N, yet they hold all N. So some box holds at least N/k, and since it holds a whole number of things, at least ⌈N/k⌉. Five links in two colours give ⌈5/2⌉ = 3 of one colour; sixteen links in three colours give ⌈16/3⌉ = 6.
Choosing the boxes for the divisors. Every whole number is, in exactly one way, an odd number times a power of 2, m × 2ᵃ; put it in box m. Two numbers in one box are m × 2ᵃ and m × 2ᵇ with a < b, and the first divides the second. The odd numbers from 1 to 2n are 1, 3, …, 2n − 1, which is n boxes, so n + 1 picks force two into one box. The bound is exact: n + 1, …, 2n are n numbers, one per box, and none divides another, because doubling the smallest of them already passes 2n.
From equal sums to disjoint groups. Two different groups A and B with the same sum may share some numbers. Remove the shared numbers from both: each sum drops by the same amount, so the sums stay equal. Neither group becomes empty, because if A sat inside B, B would have the larger sum, all the numbers being positive. What is left is two disjoint, non-empty groups with equal sums, and that is what the page draws.

Nine numbers from 1 to 16: one always divides another 🖖

Write each number as an odd number times a power of 2: 12 = 3 × 4, 10 = 5 × 2. Numbers with the same odd part go in the same box, and the smaller divides the larger, because they differ only by powers of 2. From 1 to 16 there are eight odd numbers, so eight boxes, and nine picks put two in one box. Press 9 to 16 to see eight numbers that escape, one per box: only 10 of the 12,870 eight-number picks do. Then press 9 to 16 and 5. All 11,440 nine-number picks hold a dividing pair, and the boxes prove it without checking a single one.

Among six people, three are mutual friends or three are strangers 🖖

Press Six people and take person 1. Their five links come in two colours, so at least three share one; say they are friends. If any two of those three are friends with each other, they and person 1 are three mutual friends. If none are, those three are mutual strangers. Either way a triangle appears, and the argument never looked at the colouring. Five people can avoid it, with friends round a pentagon and strangers across it. Of the 1,024 ways to colour five people’s links, 12 avoid a one-colour triangle, and each is that pentagon in some arrangement. None of the 32,768 for six does. Greenwood and Gleason gave this argument in 1955.

Ten two-digit numbers always hide two equal sums, and so do nine 🖖

Press Ten numbers. Ten distinct two-digit numbers make 2¹⁰ − 1 = 1,023 non-empty groups, and a group of them can only sum to something from 10 to 90 + 91 + … + 99 = 945, which is 936 values. So two groups share a sum; take away the numbers they have in common and the sums stay equal while the groups become disjoint. This was the first problem of the 1972 International Mathematical Olympiad. With nine distinct numbers it is 511 groups against at most 846 sums, and counting says nothing. The truth goes further than the count: nine numbers with every group sum different need one of them to be at least 161 (J. P. Grossman’s computation), so nine two-digit numbers always collide as well. Eight can escape; press Eight that escape.

Problem solved in full

How many people force a one-colour triangle with three colours? 4 steps
Each pair of people is now friends, strangers or rivals: three colours instead of two. How many people guarantee three who are all linked in a single colour?

Open this problem in the tool
1. With two colours, the page’s argument starts from one person’s links:
  
  $6 people : 5 links, 2 colours \Rightarrow ⌈ \frac{5}{2} ⌉ = 3 share a colour$
2. With three colours, take one person among 17. Their 16 links fall into three colours:
  
  $17 people : 16 links, 3 colours \Rightarrow ⌈ \frac{16}{3} ⌉ = 6 share a colour$
3. If any two of those six are linked in that same colour, they and the first person make a one-colour triangle:
  
  $a link of that colour among the 6 \Rightarrow a triangle through person 1$
4. If none are, the six use only the other two colours, and the page’s six-person party already guarantees a triangle among them:
  
  $no such link \Rightarrow the 6 use 2 colours \Rightarrow a triangle, since R (3, 3) = 6$
Answer

Seventeen people are always enough, and Greenwood and Gleason showed in 1955 that sixteen are not: they coloured sixteen people’s links in three colours with no one-colour triangle. With four colours nobody knows the answer; it lies between 51 and 62.

$R (3, 3, 3) = 17; 51 \leq R (3, 3, 3, 3) \leq 62$

Learning path

Methods of proof

References (5)

The party problem solved exactly as this page solves it, the pentagon with red sides and blue diagonals for five and one person's five links for six, and Theorem 4, three colours need exactly 17 people, which is the worked problem: R. E. Greenwood and A. M. Gleason, "Combinatorial Relations and Chromatic Graphs", Canadian Journal of Mathematics 7, 1–7 (1955).
The equal-sums problem as it was set, ten distinct two-digit numbers, with the count of 1,023 groups against sums of at most 945: 14th International Mathematical Olympiad, 1972, Problem 1; problem and solution in J. Scholes's IMO archive (Kalva).
Why nine two-digit numbers cannot escape either: nine numbers with all their subset sums different need one at least as large as 161: OEIS Foundation, "A276661: Least k such that there is a set S in {1, 2, ..., k} with n elements and the property that each of its subsets has a distinct sum", The On-Line Encyclopedia of Integer Sequences.
Three colours are settled at 17; four are not, and the answer lies between 51 and 62: OEIS Foundation, "A003323: Multicolor Ramsey numbers R(3,3,...,3), where there are n 3's", The On-Line Encyclopedia of Integer Sequences.
The principle stated and used, including its generalised form, ⌈N/k⌉ in some box: E. Lehman, F. T. Leighton and A. R. Meyer, Mathematics for Computer Science, MIT, revised 6 June 2018, §15.8, The Pigeonhole Principle.

By the 42Math team · Reviewed against published sources. Corrections welcome.