Any one have some good examples of the pigeon-hole principle being used to prove something that seems surprising?
For example:
Theorem: For every positive integer N, there is a multiple kN such that the decimal representation of kN consists of only 0s and 1s.
Examples:
13 -> 1001
There is an elegant proof of that theorem that uses the pigeon-hole principle, and yet I find the result ... charming.
It can also be generalised to other bases, etc. There's more going on.
But this question is not about this. This question is about other examples of the PHP giving a nice, clean, elegant proof of a non-obvious statement.
Oct 8, 2026, 5:53 PM@ColinTheMathmo I have a feeling you've asked this before and if you did it's possible that I gave this answer when you did, but:
Theorem: a sequence (of, say, real numbers) of length bigger than MN contains either M elements that form an increasing subsequence or N elements that form a decreasing subsequence.
Proof: for each element in the sequence, find the longest increasing and decreasing subsequences ending there; call them m,n; label that element with (m,n).
No two elements can have the same label because if x has label (m,n) and comes before y, then if x<y then the first component of y's label is at least m+1 and if x>y then the second component of y's label is at least n+1. (Because you can just extend one of the sequences ending at x by adding y to it.)
So, by the pigeonhole principle, it is impossible for all the labels to be in [1,M] x [1,N], because then there would be more elements than labels but all labels unique.
Which, by the definition of the labels, is just another way of saying: there's either an increasing sequence of length > M or a decreasing sequence of length > N, qed.
@gjm I have asked this question before, but I have more (and different) followers now, so I thought I might get some new answers.
And I really like this result ... I have it in my collection. I was just wondering about more.
The one about numbers having a multiple that's comprised only of 1s and 0s is a nice "starter for ten" ... this one about sequences is deeper, and unsurprisingly harder.
Oct 8, 2026, 6:14 PM@ColinTheMathmo Well, my first choice of an easier example would be ... the one I gave the last time you asked this question. (I just checked: yes, you've asked the question before, and yes, I gave Erdos-Szekeres as an example before. But I also said:) If you write down any n numbers, then there's some consecutive block of them whose sum is a multiple of n.
Obviously I am not contributing anything new to your knowledge by giving answers I've given before, and also the simpler one in this toot maybe _too obviously_ calls for the pigeonhole principle, but if you go through whatever answers you get then they might as well include both of these :-).
@gjm ... and absolutely I'm grateful for the answers and your attention. I especially like the range of examples.
Thank you.
Do you like the one about there always being a multiple consisting of 0s and 1s? It's very much a matter of taste ... it may be *too* simple to appeal to you.
Oct 8, 2026, 9:03 PM@ColinTheMathmo Nah, I like it. It has rather the same feel as the "consecutive block that's a multiple of n" thing, no?
@gjm When you've asked enough questions, you're bound to ask a question you've asked already. AI is the pigeonhole principle. @ColinTheMathmo
Oct 8, 2026, 9:47 PM@pigworker @ColinTheMathmo This is why AI systems have proven unable to solve any problem not already solved by humans, such as proving that solutions to the Navier-Stokes equations can become singular or that there are no zeros of the Riemann zeta function with real part > 7/8.
I vigorously endorse[1] disapproving of AI systems because you disapprove of how they were trained, or because you fear they will cause mass unemployment, or because you think their net effect will be to concentrate power in the hands of billionaires even more than at present, or because you think using them will inevitably be bad for one's brain, or because you think they might wipe out the human race. But I see too many otherwise-extremely-smart people who have nailed their colours to the mast of the good ship Stochastic Parrot and proclaim confidently that AI systems cannot do things that they demonstrably can do[2], and I think it's better not to do that.
[1] I am not sure all those things are _right_ but they are for sure things that a reasonable person can disapprove of AI for.
[2] Some other people make the opposite mistake, but I don't see many of them here.
@gjm For sure, burning the world (I note no remark from you about environmental impact) makes this form of AI a better integrator of efforts from diverse humans than any individual human has the attention span to be. Is it that the nearly-there low-hanging fruit are being gobbled up? @ColinTheMathmo
Oct 8, 2026, 10:26 PM@pigworker @ColinTheMathmo I listed a bunch of things reasonable people could object to; I wasn't trying to make a complete list of everything any reasonable person could object to.
But, since you bring it up, I am somewhat persuaded that the environmental impact is not as bad as it's often made out to be. It's substantial, but only in the same way as any new major industry's environmental impact is substantial. It seems likely to me that the net benefit or, more likely, harm of AI systems will come from other places.
I do think it's possible that the mathematical results OpenAI has been dumping on the world are "only" a matter of "filling in the convex hull of human knowledge", so to speak[1]. But that's not the same thing as only answering "a question you've asked already". I'm pretty sure the _huge majority_ of academic research, industrial R&D, artistic creation, etc., is also "filling in the convex hull", and that doesn't stop it being valuable and important and in some cases beautiful. "These AIs can only do 99% of the things top creative humans can do" really isn't that much of a dunk.
[1] I didn't come up with the metaphor; I believe it originates at https://birdsnfrogs.github.io/2026/09/12/Felix_qui_potuit_rerum_cognoscere_causas.html.
For the avoidance of doubt: If indeed the AIs can't do more than "filling in the convex hull" and will never go beyond that, that's a super-important limitation. But (1) I don't think we actually know even the first half, never mind the second, and (2) "they can only do things derived from what humans have already done" is very much not the same as "they can only do the same things as humans have already done".
Oct 8, 2026, 10:41 PM@pigworker @ColinTheMathmo BTW, "I note no remark from you about environmental impact" reads to me as "I have identified you as The Enemy and, gotcha, you have revealed your true colours by trying to downplay this crucial weakness" and that makes me sad.
I very much hope I am reading way too much into that "I note + observed deficiency" locution, but I don't think I've ever seen it used without that sort of subtext. (Well, it's not always very sub.)
@gjm You are not the enemy. But environmental impact is important. Even if this technology were good at what it purports to do, we should pay attention to what it costs the world we live in. @ColinTheMathmo
Oct 8, 2026, 11:07 PM@pigworker @ColinTheMathmo We very very much should, I agree. (And also if it were _bad_ at what it purports to do.) But it doesn't look to me as if "burn the world" is at all a reasonable summary of the impact of AI systems to date, or in the foreseeable future if the more extreme-doomerish scenarios don't come to pass.
For instance, see https://andymasley.com/visuals/ai-prompt-footprint/ which purports to estimate the carbon-emissions impact of an individual's AI-model use, and https://blog.andymasley.com/p/training-ai-models-doesnt-emit-that arguing that the cost of _training_ the models isn't that large given that it's a cost shared across all users. I do not claim that all his numbers are correct or that he hasn't missed anything, but it looks to me like he's making an honest and reasonably thorough attempt at quantifying these things.
Again, I am not particularly wedded to these opinions and would expect to be persuadable by good arguments/evidence in the opposite direction.
@gjm These things cash out on the ground as "data centers" which have horrifying environmental impacts on their surroundings, and which are due to mushroom in response to demand. This is not a sustainably efficient technology, even if it is a capable technology. @ColinTheMathmo
Oct 8, 2026, 11:45 PM@pigworker @ColinTheMathmo Same guy as before claims the actual impact of data centres is not nearly as horrifying as often claimed: https://blog.andymasley.com/p/why-i-think-panic-about-local-impacts
He makes an interesting point about the "due to mushroom in response to demand" thing: if he's right about the current state of play then for AI data centres to become a really big deal environmentally it would be necessary for there to be a huge amount more AI use, which will only happen if AI is utterly transforming the economy, in which case the _other_ impacts (for good or ill or both, and he and I both think "much more ill than good" is extremely plausible) will be a much bigger deal.
Same disclaimer as usual: I am very not an expert on the environmental impacts of AI; maybe Masley is all wrong (maybe he's an industry shill! but the evidence available to me is strongly against that); I am very willing to be persuaded by contrary evidence and arguments.
@gjm It's late and I have an early start, so let me bookmark a place for finding evidence that things are already bad in the present, let alone what your guy is saying is not scary about the scary future.
In the meantime, I'm just one of those old-timers who still knows how to use the back of an envelope. And the slide rule I keep in my handbag.
Oct 8, 2026, 11:55 PM@pigworker @ColinTheMathmo Sleep well, and may your envelopes never tear and your slide rule never slip.
@gjm Obvs, I am careful enough to tear the envelopes in such a way that enables me to read their contents, but still leaves the envelopes themselves as a suitable substrate for calculation. @ColinTheMathmo