How Infinity Hides Into Your Algorithms: The Power of Pigeonhole Principle
Audience: undergraduate
“You cannot put 10 socks in 9 drawers without something overlapping, obvious right? But this trivial fact lets you prove infinite truths, detect collisions in cryptography, and defeat compression algorithms.” At first glance, the Pigeonhole Principle (PHP)—“if you have more pigeons than holes, at least one hole must contain at least two pigeons”, feels like a Kindergarten observation. But, it is no longer just a drawer problem. This is a gateway to infinity, impossibility, and inevitability- all hidden in a childish fact. Let us unpack how this humble principle sneaks into algorithms and mathematical truths.
Analytics
Comments
The motivation and memorability on this article are pretty good. It’s the clarity that needs some work, and the tone and level feel inconsistent. There are some parts of this where the explanation is very clear, and others where critical information is missing.
Here are some more specific comments. You mention the Birthday paradox in two places, but do not really define it or actually make explicit how it is connected to the story you are trying to tell. In the section on Dirichlet’s theorem, you state the theorem but don’t state its significance until the end of the section, when probably this is what you should lead with. Also for the part about the square root of 2, I am confused how what you’ve got here is unique to the square root of 2… why couldn’t we plug in any value, including a rational value, and reach the same conclusion (which would be incorrect for a rational)? By contrast, your sections 3.1 and 3.2 are wonderfully clear, excellent job here. For the Erdős–Szekeres: Longest Increasing Subsequence visualization, I don’t totally get what I’m looking at because the axes aren’t labeled. Also in this section I’m not totally sure what m.n is – is that m times n? The Ramsey theory interactive visualization is absolutely fantastic, you really get the sense from clicking that for every triangle you destroy you end up creating others. I might suggest making the yellow triangles slightly transparent though, so you can still tell if it’s blue or red underneath. Meanwhile the “Choosing Pigeonholes — Interactive Partitioning” visualization could just be cut I think; it’s trivially simple, and I don’t think it really contributes to the section around it. On the flip side, the “Covering Lattice Points” could use a visual example.
As a formatting note, the text would look cleaner if you stick to always using LaTeX rendering for all variables, rather than plain text for things like 2^n and x1.
This looks more like an encyclopedia of usages of pigeonhole principle. I think I would’ve enjoyed it more if it were focused on only some of the applications, with a bit of development.
Also, you seemed to include some references from ChatGPT. While I’m not against learning math with AI, this might be against the rules of the contest.
Really nice use of interactive elements to demonstrate the theorems and ideas. I also love the variety of topics presented!
The number of examples is impressive, great job showing how relevant PHP is!
This is above my level of understanding but just skimming the content shows a high degree of clarity, great interactive examples, and keeping the explanations as simple as possible. Well done!
The Erdős–Szekeres visualization could have used some more details on what the simulator was interpreting m and n to be, and how that related to the LIS chosen. On the whole, though, the visualizations were helpful ways to illustrate the results of difficulty-worded theorems!
I liked the interactive elements, although I struggled to see how one or two of them aided understanding. Overall I felt like the article was very textbook-like: presenting a bunch of theorems and moving on. I personally prefer to read articles that have clear motivation and direction, that make me really care about the subject, which sadly this article didn’t do for me.
I thought this was a neat idea before using the pigeonhole principle as a method of proof and how it can be extended to other ideas. I’ve found the examples were simple enough to follow along, but yet quite surprising in terms of how elegant it was. Some of the more complex proof near the bottom with some animations could definitely improve the ease of understanding for a wider audience to understand the scope of the PHP.
Nice problems covered, but it reads a bit too much like an LLM for me, and feels like a list of uses rather than a coherent piece.