HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
The Pigeonhole Principle
  1. 1The pigeonhole principle
  2. 2The generalised pigeonhole principle
  3. 3Pigeonholes in numbers and geometry
  1. Mathematics
  2. /The Pigeonhole Principle
  3. /Pigeonholes in numbers and geometry

Course 30.1·Lesson 3 of 3

Pigeonholes in numbers and geometry

In number theory the boxes are often remainders: among m+1m + 1m+1 whole numbers, two have the same remainder on division by mmm. Prefix sums give a block of numbers with a sum divisible by mmm. Odd parts show that among n+1n + 1n+1 numbers from 111

about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

Lesson 3 of 3Show all lessonsHide
The Pigeonhole Principle
  1. 1The pigeonhole principle
  2. 2The generalised pigeonhole principle
  3. 3Pigeonholes in numbers and geometry

Try the code and the simulations beside the lesson.

What you will be able to do

  • use remainders and prefix sums as pigeonholes;
  • use odd parts and pairs to prove divisibility results;
  • cut a figure into pieces to show that two points are close.

Remainders

Every whole number leaves one of the remainders 0,1,…,m−10, 1, \dots, m - 10,1,…,m−1 on division by mmm. So:

Among any m+1m + 1m+1 whole numbers, two have the same remainder on division by mmm, and their difference is divisible by mmm.

Here is a strong use of it. Take the numbers 111, 111111, 111111111, 111111111111, and so on, written only with the digit 111. They are called repunits. Show that some repunit is divisible by 777.

  1. Objects. The first 888 repunits.
  2. Boxes. Their remainders on division by 777, which are 777 boxes.
  3. Two share a box. Their difference is divisible by 777. The difference of two repunits looks like 11…100…011\dots100\dots011…100…0, a repunit times a power of 101010.
  4. Remove the zeros. A power of 101010 has no factor 777, so the repunit itself is divisible by 777.

Indeed 111111=7×15873111111 = 7 \times 15873111111=7×15873.

Prefix sums

Claim. Any list of mmm whole numbers has a block of one or more neighbours whose sum is divisible by mmm.

Proof. Let the list be a1,a2,…,ama_1, a_2, \dots, a_ma1​,a2​,…,am​. Form the prefix sums S0=0S_0 = 0S0​=0, S1=a1S_1 = a_1S1​=a1​, S2=a1+a2S_2 = a_1 + a_2S2​=a1​+a2​, up to SmS_mSm​. That is m+1m + 1m+1 sums and mmm remainders. Two of them, SiS_iSi​ and SjS_jSj​ with i<ji < ji<j, share a remainder. Then Sj−Si=ai+1+⋯+ajS_j - S_i = a_{i+1} + \dots + a_jSj​−Si​=ai+1​+⋯+aj​ is divisible by mmm.

For the list 3,5,2,73, 5, 2, 73,5,2,7 the prefix sums are 0,3,8,10,170, 3, 8, 10, 170,3,8,10,17, with remainders 0,3,0,2,10, 3, 0, 2, 10,3,0,2,1 on division by 444. The sums S0S_0S0​ and S2S_2S2​ share the remainder 000, so the block 3+5=83 + 5 = 83+5=8 is divisible by 444.

Odd parts and divisors

Every whole number can be written as 2t×q2^t \times q2t×q with qqq odd. We call qqq its odd part. The odd part of 24=23×324 = 2^3 \times 324=23×3 is 333.

Claim. Choose n+1n + 1n+1 numbers from {1,2,…,2n}\{1, 2, \dots, 2n\}{1,2,…,2n}. Then one of them divides another.

Proof. The odd parts of the numbers 111 to 2n2n2n lie among the nnn odd numbers 1,3,…,2n−11, 3, \dots, 2n - 11,3,…,2n−1. So two chosen numbers share an odd part qqq. They are 2sq2^s q2sq and 2tq2^t q2tq, and the smaller divides the larger.

One fewer can fail: the nnn numbers n+1,…,2nn + 1, \dots, 2nn+1,…,2n contain no such pair, because twice the smallest is already larger than 2n2n2n.

Points in a figure

Five points are placed in a square of side 222 m. Show that two of them are at most 2\sqrt{2}2​ m apart.

  1. Cut the square into four squares of side 111 m.
  2. Five points, four squares. Two points lie in the same small square, edges included.
  3. The distance. Two points in a square of side 111 m are at most its diagonal apart, which is 2\sqrt{2}2​ m ≈1.414\approx 1.414≈1.414 m.
A square of side 2 m divided by dashed lines into four squares of side 1 m. Five dots lie in the big square, and two of them are in the same small square at the top right. A red segment joins those two dots, and the diagonal of that small square is marked as square root of 2 m, about 1.414 m.

The pieces may be any shape that fits the question: strips, triangles or slices of a circle. The size of each piece sets the distance you can promise.

Practise with new numbers

Try it in Python

The program forms the prefix sums of a list, finds two with the same remainder and prints the block between them.

Read it first. Then run it. Add up the block it prints and divide by the length of the list.

1. Change the list to [4, 9, 6, 1, 8, 2]. Which block does it find?

2. Change the line m = len(numbers) to m = 7. Does the program still always find a block? Why might it not?

Common mistakes

  • Forgetting S0=0S_0 = 0S0​=0. Without it there are only mmm prefix sums, one too few for the principle.
  • Mixing up the claim. Prefix sums give a block of neighbours. Any subset is a different question.
  • Pieces that are too big. Two points in one piece are only as close as the widest distance in that piece.
  • Odd parts. The odd part of 404040 is 555, not 111. Divide out every factor 222.

Remember these

  • Remainders on division by mmm are mmm boxes.
  • Prefix sums S0,S1,…,SmS_0, S_1, \dots, S_mS0​,S1​,…,Sm​ give a block with a sum divisible by mmm.
  • Odd parts: n+1n + 1n+1 numbers from 111 to 2n2n2n include a divisor pair.
  • Cut a figure into pieces. Two points in one piece are close.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. Prove that some repunit is divisible by 333. Which is the smallest?
  1. For the list 2,6,5,9,42, 6, 5, 9, 42,6,5,9,4 find a block of neighbours whose sum is divisible by 555.
  1. What is the odd part of 969696?
  1. Choose 666 numbers from {1,2,…,10}\{1, 2, \dots, 10\}{1,2,…,10}. Show that one divides another.
  1. Ten points lie in a square of side 333 cm. Show that two are at most 2\sqrt{2}2​ cm apart.

References

  • A. Engel, Problem-Solving Strategies, Chapter 4, the box principle in number theory and geometry.
  • R. A. Brualdi, Introductory Combinatorics, Chapter 3.

Enroll free in The Pigeonhole Principle

Every lesson is open to read. Enrolling also lets you:

  • Mark lessons done and carry on where you stopped.
  • Take the tests of this lesson and its course.
  • Count the course towards the certificate for its chapter.
No payment. You can leave at any time.

Problems (4)

A metal plate is an equilateral triangle with sides of 4 cm…Hard · High School (11–12) · by StemPy Lab
A set of whole numbers is chosen from 1 to 100…Advanced · High School (11–12) · by StemPy Lab
Ravi notices that 3⁴ = 81 ends in 1 and 3²⁰ = 3486784401 ends in 01…Advanced · High School (11–12) · by StemPy Lab
That was the last lessonBack to the course: take the test
← The Pigeonhole Principle
← The generalised pigeonhole principleNext →

Discussion (0)

Log in to join the discussion.

Loading…

to
2n2n2n
, one divides another. In geometry the boxes are pieces of a figure, so points that share a piece are close together.
Ten different two-digit numbers are written on cards, for example 13, 27, 31, 44, 52, 68, 70, 85…
Advanced · High School (11–12) · by StemPy Lab

Python Labs (1)

Blocks and odd partsPython Lab · by StemPy Lab

Question Sets (1)

The Pigeonhole Principle: Check Your Understanding10 questions · by StemPy Lab

Notes (1)

The Pigeonhole Principle: Quick RevisionNote · by StemPy Lab