3 ms·
Whenever the pigeon-hole principle is name dropped, we should also drop Dijkstra's commentary The undeserved status of the pigeon-hole principle. https://www.c
by emil-lp 11mo ago
Whenever the pigeon-hole principle is name dropped, we should also drop Dijkstra's commentary The undeserved status of the pigeon-hole principle.
https://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD1094.html https://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD109...
- peacebeard 11mo agoWow. I thought the metaphor was stupid when I was taught this in college, and only now, decades later, I find out Dijkstra agreed.
- badmonster 11mo agoInteresting! Were there other examples from your course that had similar delays in insight? What changed your perspective?
- paulddraper 11mo agoThe first time I saw the Pigeonhole Principle was in the following: Problem: A plane has every point colored red, blue, or yellow. Prove that there exists a rectangle whose vertices are the same color. Solution: Consider a grid of points, 4 rows by 82 columns. There are 3^4=81 possible color patterns of columns, so by the Pigeonhole Principle, at least two columns have the same color pattern. Also by the Pigeonhole Principle, each column of 4 points must have at least two points of the same color. The two repeated points in the two repeated columns form a rectangle of the same color. QED. The Pigeonhole Principle is very neat. It would be hard not to use it for the proof. Partly that article argues against proof by contradiction which does seem to be overused.
- moi2388 11mo agoUnless by plane they mean airplane, since in curved 3d surface this is not automatically given to be true.
- layer8 11mo agoEven if it was talking about airplanes, it doesn’t mention “surface”. So it would still hold, given that airplane parts aren’t infinitely thin.
- IAmBroom 11mo agoTopologically, an airplane is identical to a universe of curvature=+1. Since the size of the grid versus the airplane/universe is not given, I will assume there are infinitely many grid points.
- cousin_it 11mo agoWow, this works for any number of colors.
- paulddraper 11mo agoYes it does :) What a fun little result.
- deleted 11mo ago[deleted]
- Xmd5a 11mo agosudoku is just pigeonholing then
- ky3 11mo agoA grid with 19 columns is enough. Every column at worst has all 3 colors, one of them used twice. Once we fix that one color, there are C(4,2)=6 ways of filling out the rest of the entries. Since there are 3 colors, there are exactly 6*3=18 worst possible columns. With 19 columns a repetition is guaranteed, yielding the desired rectangle. For fun, try strengthening the result to a square.
- qsort 11mo agoI love Dijkstra's writing, but I don't think this is his strongest piece. In general parlance, when we say "by piegonhole" we mean "any variant of it". I'd still call what he's doing "piegonhole" lol. You can even further generalize it, e.g. by making expected value arguments. This is not uncommon: we can say that "by the fundamental theorem of algebra" two polynomials of degree N that agree on N+1 points are identically equal. "By induction" includes Cauchy induction, sometimes with "this and that are the same" we mean "up to isomorphism" and so on. The advice he ends on is extremely solid, though: The moral of the story is that we are much better off with the neutral, general standard procedure: name the unknown(s) so that you can formalize all conditions given or to be established and simplify by formula manipulation. The math will always math.
- CGMthrowaway 11mo agoCombining that with OP article, the obstruction to showing hardness is therefore not technical but foundational- ie. the required axiom lies outside the standard minimal toolkit
- robot-wrangler 11mo agoAlso makes an appearance in the recent thread about how "every mathematician only has a few tricks": https://mathoverflow.net/questions/363119/every-mathematician-has-only-a-few-tricks https://mathoverflow.net/questions/363119/every-mathematicia...