Knoji’s Equation Station – Your November Maths Challenge

The specific concept we are exploring this month is the pigeonhole concept.

The pigeonhole principle is one of those ideas that sounds almost too obvious, but turns out to be surprisingly powerful. If you put more objects than boxes into those boxes, then at least one box must contain at least two objects.

That is all. That is the whole principle.
A very simple example

Imagine you have 5 pigeons and 4 pigeonholes.

If every pigeon goes into a hole, what must be true?

Since there are more pigeons than holes, at least one hole must contain at least two pigeons. There is no way to avoid it.

Real life applications

Quality Control & Auditing. By drawing from the pigeonhole principle, auditors can check if their unique ID systems or barcode systems are adequate for the volume of product output. If there are more “pigeons” – products – than “holes” – IDs, then the risk of duplication is high.

Computer Science. A hash function is a rule that turns some data into a shorter code.

• For example, a password might be turned into a long string of bits like 1010... using a hash.
• The important point: there are huge numbers of possible passwords, but only a limited number of possible hash outputs.

So by the pigeonhole principle:

• There are more possible inputs (passwords) than outputs (hash codes).
• So it is impossible for every input to get its own unique output.
• So some different inputs must share the same hash.
  This is called a collision.

You cannot completely avoid collisions. You can only choose hash functions that make collisions very rare and hard to find.

Maths challenge question

• 🔍
• Hint 1
• Hint 2
• Solution

Click “Solution!” to check your answers!