Two Examples For The Box Principle – Mattia Giuri's bizarre blog

The box principle is a pretty simple yet so useful mathematical principle which asserts:

If there are n+1 objects to put into n boxes, then 2 objects must be in the same box.

This makes us think that usually we just have to divide our set of possibilities in mutually exclusive boxes and prove that there are actually more objects than boxes.

Diagonals In Polygons

Prove that in any convex 2n-gon there is always a diagonal not parallel to any side.

Let’s count the diagonals in a 2n-gon. They are

$\frac{2n(2n-3)}{2} = n(2n-3)$

On the other hand, for each of the sides 2n-gon, at most n-2 diagonals are parallel to it (imagine a regular polygon to understand why).

So there are at most 2n(n-2) diagonals parallel to the sides in total.

But since $n(2n-3) > 2n(n-2)$ at least one diagonal is not parallel to any of the sides.

Choosing Some Integers

Prove that the minimum number n of integers you have to get so that however n integers there are two whose difference is a multiple of 100 is 52.

At first we see that for n = 51 we have the counterexample 1,2,3,…,50,100.

Then we build 51 boxes: numbers ending in 00, numbers ending in 01 or 99, numbers ending in 02 or 98, numbers ending in 03 or 97, …, numbers ending in 50.

However you choose 52 integers, two must be in the same box for the box principle, hence 52 is the smallest n with the desired property.