What is it?

The pigeonhole principle is deceptively simple: if you have more pigeons than holes, at least two pigeons must share a hole. In mathematical terms: if N items are placed into M containers and N > M, at least one container must contain multiple items.

In this cipher, you're given N+1 points placed in an N×N grid. Since there are N+1 points but only N rows (and N columns), by the pigeonhole principle at least two points must share a row or a column. You just need to find which row or column is shared — that index mod 26 (A=0) gives the secret letter.

Concrete Example

Consider a 4×4 grid (N=4) with 5 points placed at:

(0, 1), (1, 3), (2, 0), (2, 2), (3, 1)

Let's check each row for multiple points:

Row 0: (0,1) — 1 point
Row 1: (1,3) — 1 point
Row 2: (2,0), (2,2) — 2 points! ✦
Row 3: (3,1) — 1 point

Row 2 (index 2) has two points. 2 mod 26 = 2 → C (since A=0, B=1, C=2).

Alternatively, if no row had duplicates, we'd check columns. With 5 points in a 4-column grid, at least one column must have duplicates by the same principle.

The answer for this example would be "c".

Why It Works

The pigeonhole principle is a fundamental counting argument. In an N×N grid, there are exactly N rows. Placing N+1 points means at least one row has 2+ points (by the pigeonhole principle with N+1 pigeons and N holes). Similarly, there are N columns. The puzzle always picks a grid where N+1 points are placed, so a collision is guaranteed. You just need to find it — the shared row or column index is the key to the letter.

Solving Tips

• List all the points given in the grid
• Check each row index (x-coordinate) for multiple points
• If no row has duplicates, check each column index (y-coordinate)
• The shared index mod 26 gives the answer letter (A=0)
• This is the simplest puzzle — just counting and matching

Real-World Applications

• Birthday paradox: With 367 people in a room, two must share a birthday — a direct application of the pigeonhole principle
• Data compression: The pigeonhole principle proves that lossless compression can't compress all inputs (there are more inputs than outputs)
• Hash collisions: Any hash function with more inputs than outputs must have collisions — fundamental to understanding hash table performance and security
• Scheduling: If you have more tasks than time slots, at least one slot must handle multiple tasks
• Ramsey theory: The pigeonhole principle is the simplest case of Ramsey theory — the study of unavoidable patterns in large sets