In number theory the boxes are often remainders: among m+1 whole numbers, two have the same remainder on division by m. Prefix sums give a block of numbers with a sum divisible by m. Odd parts show that among n+1 numbers from 1
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
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−1 on division by m. So:
Among any m+1 whole numbers, two have the same remainder on division by m, and their difference is divisible by m.
Here is a strong use of it. Take the numbers 1, 11, 111, 1111, and so on, written only with the digit 1. They are called repunits. Show that some repunit is divisible by 7.
Objects. The first 8 repunits.
Boxes. Their remainders on division by 7, which are 7 boxes.
Two share a box. Their difference is divisible by 7. The difference of two repunits looks like 11…100…0, a repunit times a power of 10.
Remove the zeros. A power of 10 has no factor 7, so the repunit itself is divisible by 7.
Indeed 111111=7×15873.
Prefix sums
Claim. Any list of m whole numbers has a block of one or more neighbours whose sum is divisible by m.
Proof. Let the list be a1,a2,…,am. Form the prefix sumsS0=0, S1=a1, S2=a1+a2, up to Sm. That is m+1 sums and m remainders. Two of them, Si and Sj with i<j, share a remainder. Then Sj−Si=ai+1+⋯+aj is divisible by m.
For the list 3,5,2,7 the prefix sums are 0,3,8,10,17, with remainders 0,3,0,2,1 on division by 4. The sums S0 and S2 share the remainder 0, so the block 3+5=8 is divisible by 4.
Odd parts and divisors
Every whole number can be written as 2t×q with q odd. We call q its odd part. The odd part of 24=23×3 is 3.
Claim. Choose n+1 numbers from {1,2,…,2n}. Then one of them divides another.
Proof. The odd parts of the numbers 1 to 2n lie among the n odd numbers 1,3,…,2n−1. So two chosen numbers share an odd part q. They are 2sq and 2tq, and the smaller divides the larger.
One fewer can fail: the n numbers n+1,…,2n contain no such pair, because twice the smallest is already larger than 2n.
Points in a figure
Five points are placed in a square of side 2 m. Show that two of them are at most 2 m apart.
Cut the square into four squares of side 1 m.
Five points, four squares. Two points lie in the same small square, edges included.
The distance. Two points in a square of side 1 m are at most its diagonal apart, which is 2 m ≈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.
Common mistakes
Forgetting S0=0. Without it there are only m 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 40 is 5, not 1. Divide out every factor 2.
Remember these
Remainders on division by m are m boxes.
Prefix sums S0,S1,…,Sm give a block with a sum divisible by m.
Odd parts: n+1 numbers from 1 to 2n 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.
Prove that some repunit is divisible by 3. Which is the smallest?
For the list 2,6,5,9,4 find a block of neighbours whose sum is divisible by 5.
What is the odd part of 96?
Choose 6 numbers from {1,2,…,10}. Show that one divides another.
Ten points lie in a square of side 3 cm. Show that two are at most 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.