Talk:Pigeonhole principle/Archive 1

This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

Incorrect notation

I think the notation for the falling fractorial is incorrect, it should be $(x)_{n}$ , see Falling_factorial --Jaapkroe 21:18, 13 September 2006 (UTC)

Reference to the original paper

Could someone find a reference to the original paper where Dirichlet is said to have used this back in 1834? Thanks. Rob 23:04, 9 November 2006 (UTC)

Sock Drawer Example

I have a problem understanding the sock example, maybe it is related to me not being a native speaker.

Another example is: In a dark room there is a drawer with 10 black socks and 12 blue socks. Supposing you cannot distinguish them, how many socks do you have to pull out to be sure that you have at least one pair of socks of the same colour? When asked point-blank, people may sometimes unthinkingly give answers such as "thirteen", before realizing that the correct answer is obviously "three", as once you have taken three socks it is impossible to have three different colors.

I hope someone (who understands it) could clarify it a bit. Ccwelt 17:09, 24 January 2007 (UTC)

Sure. (The article could be rephrased there.) You have two mental pigeonholes: one for black socks, one for blue. By picking two socks, you could get two same-colored socks, but in the worst case, you fill both (imaginary) pigeonholes. By picking a third sock, you know that at least one "pigeonhole" has two socks in it – a matched pair. —Ben FrantzDale 18:23, 24 January 2007 (UTC)

Now I understand! :-) Ccwelt 10:56, 26 January 2007 (UTC)

I know now that my problem was the "...is a drawer..." part, as this drawer is not the drawer (=pigeonhole) the introduction talks about. I tried to make the examples clearer, hope it helps. Ccwelt 12:32, 26 January 2007 (UTC)

Shaking hands

"If there are n persons (at least two) who can arbitrarily shake hands with one another" Does anybody else find this example misleading, since it's difficult picturing a person shaking hands with more than two persons at the same time? And if it's not supposed to be simultaneous, I just don't know what the example is supposed to mean. Wouldn't it be better to pick an activity which isn't so mutually exclusive! 85.178.51.12 01:36, 23 February 2007 (UTC)

Summary

Hotpanda keeps adding a "summary" section. While it is accurate, it doesn't follow Wikipedia style to have a summary precede the article. Be aware of the three-revert rule. —Ben FrantzDale 21:23, 26 March 2007 (UTC)

For an articles such as this it makes sense to have a brief summary for people who don't want to wade through the artifical complexity at the bottom Hotpanda 00:31, 27 March 2007 (UTC) Hotpanda 00:31, 27 March 2007 (UTC)

I agree, but it should be integrated with the intro to the article rather than standing alone. —Ben FrantzDale 00:50, 27 March 2007 (UTC)

Then integrate it instead of deleting it? Hotpanda 01:21, 27 March 2007 (UTC)

Invitation

Hello, I have been reading your very nice contributions. I would like to extend you an invitation to join us at WP:TIMETRACE. What we help with is:

Where dates or periods are mentioned that are important to the article's subject, we see that those are clear, accurate and have citations to reliable sources
When an article's subject should have its orgins and development described, we see that the article has a history section and that this is accurate and has reliable sources.

You can read why this is important and more information at WP:TIMETRACE. You don't need to dedicate special time to this, you may for example, while editing diverse articles, check if they have sources in their history or chronology (or when they mention any important date. If they don't, you can either fix it if you have that information, or you can place inline {{Timefact}} calls where those citations to sources are missing, this will display ^{[chronology citation needed]}. There are also other resources and templates you can use, just visit us to know more. We will be very glad if we can count with your help. Regards Daoken 09:38, 13 September 2007 (UTC)

expectation inequality

I wrote in the article:

A further probabilistic generalisation is that when a random variable X has a finite mean E(X), then the probability is nonzero that X is greater than or equal to E(X), and similarly the probability is nonzero that X is less than or equal to E(X). To see that this implies the standard pigeonhole principle, let X be the number of pigeons in a randomly-chosen hole. The mean of X is m/n, so if there are more pigeons than holes the mean is greater than one. Therefore, X is sometimes at least 2.

Michael Hardy replied:

[The foregoing should probably be edited and then uncommented. It is not a generalization; it is at most a special case. And it doesn't seem to apply to random variables in general, but only to certain special ones.]

I rejoin:

Since I used this to give a proof of the standard pigeonhole principle, it is certainly a generalization. I'll spell out the proof in more detail. Take any fixed placement of m pigeons into n holes, then (holding that placement fixed) let X be the number of pigeons in a hole chosen uniformly at random. The expectation of X is exactly m/n, by linearity of expectation. If m is greater than n, we have that the probability that X is greater than or equal to m/n (and therefore greater than 1) is greater than 0 so this happens sometimes. This proof seems watertight to me, though it could have been written better.
I should have said that X is real-valued; otherwise I think it holds always. WLOG say that E(X)=0. Let F(x) be the distribution function of X. If F(0)=0, then for any a>0, E(X) ≥ a(1-F(a)) by Markov's inequality and so F(a)=1 since E(X)=0. This contradicts the right-continuity of F at 0, and therefore F(0)>0. Apply the same argument to -X as well. What's the problem?.

McKay (talk) 10:28, 21 July 2008 (UTC)

pigeonhole and pigeons

So...is the pigeonhole principle named after holes with pigeons in them (as the caption says), or is that a result of American ignorance (as the needlessly vitriolic body text suggests)?—Preceding unsigned comment added by 216.19.6.120 (talk • contribs)

I removed that material from the article as it needs sources and rewriting. There is nothing at all mistaken about associating pigeonholes and pigeons. The British (and Australian and NZ) use of "pigeonhole" for a small slot or shelf is itself derived from holes used by pigeons. This is clearly seen in OED, which shows that "pigeonhole" had both meanings and other obviously related meanings going back to the 17th century. It is dubious to say that the mathematical use in the UK referred only to the shelves when everyone knew that"pigeonhole" meant many similar things including holes for pigeons. At best it is a conjecture that needs a reliable source. McKay 03:06, 22 December 2006 (UTC)

I modified the caption with the pigeons. It asserted that pigeons and their holes were the inspiration for the name "pigeonhole principle". I don't know any evidence for this and it is much less plausible to me (personal opinion, of course) than to think of the pigeonholes into which letters used to be sorted by hand. I would say that any assertion about the origin of the name needs solid documentation. Zaslav (talk) 04:33, 3 November 2009 (UTC)

Finite vs. infinite

--Army1987 13:21, 29 December 2006 (UTC)==Hilbert's Grand Hotel does not deny pidgeonhole principle== Saying that the pigeonhole principle is generally restricted to situations with a finite set of pigeonholes is somewhat misleading. It seems to imply that, with infinite sets, there are counter-examples to the pidgeonhole principle. This isn't the case. For example, in the case of Hilbert's Grand Hotel, there are ℵ₀ rooms and ℵ₀ guests, so it is not the case that n > m. Indeed, I have seen "All functions from A to B are not injective" used as a definition of the relation card(A) > card(B). So I guess that sentence should be reworded. --Army1987 20:54, 28 December 2006 (UTC)

The introduction offers three different phrasings of the pigeonhole principle:

First phrasing: if n items are put into m pigeonholes, and n > m, then at least one pigeonhole must contain more than one item. Being pedantic about terminology, this phrasing restricts it to finite sets. ℵ₀ is not a number; while you can have "a set of items/pigeonholes, with cardinality ℵ₀", you can't actually have "ℵ₀ items" or "ℵ₀ pigeonholes". (Also, by convention 'n' and 'm' usually refer to integers.)

If we overlook that issue and accept "n items" as a colloquial way of saying "a set of items that has cardinality n", we run into the problem that '>' is ambiguous when applied to infinite sets, because there are more ways than one to extend its definition beyond the reals (each of which breaks some of the rules that apply to '>' when restricted to the reals). For instance, comparing the sets [0,1] and [0,2], they are the same in terms of cardinality... but different in terms of measure. (Loosely speaking, a measure-theory interpretation of '>' attempts to preserve the rule that when m>0, n+m>n, while a cardinality interpretation preserves rules about when you can create one-to-one/onto mappings between the sets. Infinite sets being what they are, you don't get to preserve both those rules at once.) It so happens that by choosing the 'cardinality' interpretation we can make the sentence correct, but at this point in the article it's not necessarily obvious to the reader that that's the correct choice.

Second phrasing: Another way of stating this would be that m holes can hold at most m objects with one object to a hole; adding another object will force you to reuse one of the holes. Clearly not correct for infinite sets; we can add another guest to the Grand Hotel without any doubling up.

Third phrasing: More formally, the theorem states that there does not exist an injective function on finite sets whose codomain is smaller than its domain. This one is explicitly restricted to finite sets.

In any case, I've changed "generally restricted to finite sets" to "generally applied to finite sets"; I hope the rest of that paragraph provides enough information for the reader to figure out how it translates to infinite sets. --Calair 04:41, 29 December 2006 (UTC)

It depends on what you mean by 'number'… (A friend of mine said that his professor claims +∞ to be "a number", whatever he means. And I believed it to be just a symbol for the supremum of an unbounded set of reals…) In the first phrasing it is very evident that m can't be fractional (and neither can n, unless the definition of 'item' one uses is too broad), ^* nor can it be negative or zero. But if one assumes they cannot be infinite cardinal numbers, we'd better make it clear. (Many books of real analysis, when referring to an interval (a; b), explicitly state that a and b must be finite, no matter how obvious this is in the given context.) Anyway this is not needed, provided that when talking about n items it is obvious that we refer to the cardinality of the set of the items. ^** But in the second wording, explicitly stating that m is finite makes the sentence less ambiguous and does no harm. As for the third phrasing, adding "in terms of cardinality" after "smaller" does away with the need to state that the sets must be finite. Anyway, since "smaller cardinality" is precisely defined that way, I bet this result is way too trivial to be called a "theorem".

^*Another principle by Dirichlet is that if x₁, …, x_n are real numbers, at least one of them is greater or equal to their average. If we denote m to be their sum, and m > n, at least one of them is greater than 1. We can consider this to be a continuous extension of the pidgeonhole paradox. (Consider x_i to be the number of grams of a given substance in the ith pidgeonhole, and m to be the total mass of that substance in grams… If m > n, at least one hole contains more than 1 g of substance.)

^**Or is it? My high school book states that a system of two linearly independent linear equations with four variables has ∞² solution, because they depend on two real parameters. Actually, since card(R) = card(R²), we could use just one parameter, e.g. instead of using k₁ = 12.276 and k₂ = 0.3567 we could use k = 1020.23756607. I guess they actually meant that the set of solutions is isomorphic to R², else saying "∞² solutions" is crap.

I had a professor who jokingly said that the pigeon hole principle is when you have n pigeons and you make n+1 holes in them, then at least one pigeon has more than one hole in it. —Preceding unsigned comment added by 75.140.10.44 (talk) 03:31, 17 March 2008 (UTC)

I've added a line to the infinite case indicating that it is tautological. The page on cardinalities does not talk about strict inequality of cardinals, but it is fair to assume that

|A|<|B|

means

|A|\leq |B|

and

|A|\neq |B|

, in other words there is an injective map from A to B but none from B to A. Therefore I feel that the infinite case does not deserve mention in the lead. Also I feel that the following sentence from the injective function could be mentioned as application of the pigeonhole principle: "If both X and Y are finite with the same number of elements, then f : X → Y is injective if and only if f is surjective (in which case they are bijective)". Or isn't it? (The proof of injective implies surjective supposes an element missing from the image and gets a contradiction from the pigeonhole principle; the converse uses an (obviously injective) section of the surjection.) Marc van Leeuwen (talk) 14:30, 17 January 2011 (UTC)

Unexpected results

In the article, the introduction says

It is an example of a counting argument, and despite seeming intuitive it can be used to demonstrate possibly unexpected results.

It would be great to see some examples of those situations. Lot 49a^talk 00:05, 14 September 2011 (UTC)

Read the rest of the article. I added a link from that claim to the examples section. —Ben FrantzDale (talk) 11:33, 14 September 2011 (UTC)

Picture is Awesome but Misleading

The picture on this page is awesome. Cazort 00:52, 15 October 2007 (UTC)

But doesn't show the principle in practice. --BirdKr 15:30, 21 October 2007 (UTC)

I agree. I think the picture and caption are very misleading. The PHP has nothing do with the reasoning that at least two holes must be empty. It's not incorrect, just irrelevant to this topic and misleading as to how the PHP is used. Particularly if a reader's eye is naturally drawn to the picture and caption, making it the first example one sees. A picture (photoshoped?) with more pigeons than holes would be a huge improvement to this page. --Tom Roby (UConn) 6 Mar 2008.

I used gimp to move a pigeon so now there's on empty hole and two holes with two pigeons. —Ben FrantzDale (talk) 12:58, 14 September 2011 (UTC)

Now there are 11 pigeons, while the caption says 10 :( — Preceding unsigned comment added by Rafaelst (talk • contribs) 23:34, 14 August 2012 (UTC)

Simple generalization with sum of real numbers

The "Generalizations" section has a few generalizations, but does not include the one that is most obvious to me:

   In a set S of m > 0 positive real numbers that sum to n, there exists an x ∈ S such that n/m ≤ x.

Should this also be included? Jameshfisher (talk) 18:15, 15 November 2013 (UTC)

who invented these Pigion Hole Principle? — Preceding unsigned comment added by 175.101.8.71 (talk) 06:16, 7 December 2013 (UTC)

Surjective functions

The pigeonhole principle states that if m>n, then there is no injection from a set of cardinality m to a set of cardinality n. Similarly, if m<n, then there is no surjection from a set of cardinality m to a set of cardinality n. GeoffreyT2000 (talk) 14:41, 16 February 2015 (UTC)

Yes, but I see no gain in stating it this way. For infinite sets this is tautological since it is merely stating the definition of strict inequality of cardinalities. In the finite case, being a non-existence statement, it does not lead to any numerical refinements. Bill Cherowitzo (talk) 19:19, 16 February 2015 (UTC)

Triples?

The pigeonhole principle is always presented in terms of pairs of equivalent distinguishable items. What about equivalent triples, or higher numbers of equivalent items? Suppose there are three kinds of items. What is the minimum number that can be sampled (without replacement) such that we are guaranteed to have at least one triple of a particular kind? Again, supposing there are four kinds of items. Why is this type of generalization not made? Is it even possible? (I am asking this not to answer a problem, but to probe whether this concept, whether valid or not, is missing from the article.) David Spector (talk) 15:31, 10 March 2015 (UTC)

Latest quantum research

http://phys.org/news/2014-07-physicists-discuss-quantum-pigeonhole-principle.html for recent news of why this is misleading in some aspects. 188.29.166.73 (talk) 22:46, 26 July 2014 (UTC)

Quantum mechanics is the physics of the very tiny, and other "nonstandard" regimes in which our familiar classical mechanics does not apply. In very tiny systems, particles behave like wavelets. These wavelets can freely overlap (just as radio, TV, and light can freely overlap), so that three particles (even atoms) can "fit" within the volume of space that normally would be expected to be only large enough to hold two particles. Thus the physical pigeonhole principle does not apply at very tiny distances. However, note that this has no effect on mathematics, which models counting and other operations as they happen in our "standard" regime of distances. David Spector (talk) 19:59, 10 March 2015 (UTC)

Merger Proposal

Pigeonholing should be merged with Pigeonhole principle, they are close enough in content that the first could be a section of this page. Wqwt (talk) 08:36, 31 March 2015 (UTC)

Opposed. The relationship is purely superficial. One refers to categorizing the other to counting. Had this principle been more widely known as Dirichlet's draw principle, there would be no talk of merging. Bill Cherowitzo (talk) 16:19, 31 March 2015 (UTC)

Hair-counting example

62.131.203.39 (talk) 12:53, 24 October 2010 (UTC) If I understand the principle right, this example is not realistic because it contains a assumption that for every count of hair, there is a person.

This is definitely a misleading example that does not demonstrate the real function of the principle. This can only confuse people who do not understand the principle. As 62.131.203.39 mentioned, it relies on an assumption which does not have to occur. Gregory finster (talk) 21:52, 5 December 2010 (UTC)

No, it doesn't. I added explanation. The case of every number of head hairs represented is the "worst" case. That gives a bound. In the realistic case, there will be empty pigeonholes. That's part of the beauty of the principal, you can apply it in cases when there may still be empty pigeonholes but when there are sufficient pigeons that they could fill all pigeonholes and then some.

It would be nice if the lead illustration (which I took at the San Diego Zoo) illustrated this point, e.g., with ten birds, nine holes, and two crowded holes. —Ben FrantzDale (talk) 15:06, 6 December 2010 (UTC)

I am not sure this can be considered counter-intuitive as the `hole' of 0 hairs, i.e. bald, is clearly populated more than once. I agree that the use of the assumption everyone has less than a million hairs is not ideal but I do not think that its a problem as there is still a clear `if then' statement.

Maybe some thing like 2 people currently alive must have been born within around 0.6 seconds of each other. Or maybe something from astrophysics. — Preceding unsigned comment added by 2001:630:12:1028:215:17FF:FE68:7246 (talk) 10:20, 20 June 2014 (UTC)

In the English language, wasn't the noun "hair" uncountable? It definitely was when I studied English in school (not my first language). Should the example refer to "hair strands" instead of "hairs"? 216.165.246.48 (talk) 20:01, 11 April 2015 (UTC)

There is an English expression, "As numerous as the hairs on his head" that associates hairs with a very large number, but I have never heard of the connection with something uncountable. "Strands of hair" would be correct, but is a very formal way of speaking, not justifiable in this example. "Hairs" is a perfectly acceptable term here and is being used in a way that is consistent with the very large number idea. Wcherowi (talk) 04:20, 12 April 2015 (UTC)

The essence does not belong to the lead

The essence of Pigenhole principle is to obscure the basic trivial principle, "maximum ≥ average". Yet, this remark was removed from the intro with a note that it belongs to somewhere else. I do not understand why short and valuable simplification of the definition belongs somewhere else and, furthermore, doesn't Wikipedia prescribe to keep simple definitions for the general population with prefer add/rewirte over remove rule? Is there such rule? Why materials are always removed in the first place, even faithful and valuable ones? --Javalenok (talk) 08:41, 9 May 2015 (UTC)

Let me expand on why I reverted this edit. First of all, Dijkstra's opinion piece is not providing an alternate expression for the principle, it is a diatribe against using the principle at all. What he writes does not make much sense unless the reader is well versed in the meaning of the Pigeonhole principle. Putting this in the lead can only lead to confusion. As the lead is supposed to provide a summary of the article contents, a statement in the lead indicating that "there are critics of this formulation (to be expounded upon below)" would be acceptable. Secondly, if I can fix, amend, reword or edit in some other way an addition to an article I will do so. I only revert in cases of vandalism (which this is not) or when, in order to improve an article, I see no way other than to remove the addition and start all over again (which I may or may not do myself). In this case WP:TONE and WP:NPOV indicated to me that this addition needed to be totally reworked, so I reverted. I do not plan on reinserting a properly written version of this, as I am not sure of the value of the addition. To be clear, the author's reputation makes the statement notable, but if I had written exactly the same piece and someone else had posted it here, it would have been removed as an unreliable blog entry. If you feel that this is a valuable addition to the article, then by all means please try again - but this time try to use a neutral tone and put the criticism in context rather than trying for the three second "photo op". Bill Cherowitzo (talk) 19:44, 9 May 2015 (UTC)

I do not think that it is just a mere rant. It draws our attention to the amazing fact that the average of distribution resides between extremes rather than asks to forget it. I have actually realized it and this is how I discovered Dijkstra rant. There are not much people paying attention to this account. Yet, it is so amazing that it worth a note in WP, I am sure. Probably, Dijkstra was so angry because you keep rejecting any valuable piece of information in WP ;) Nobody rejects his "GoTo considered obsolete" just because it is also a rant. I always wonder why western public is indoctrinated to hate the rants. It is cool to listen at non-conformist account, after all. Rejecting rants helps to suppress the dissident voices, I think. This guy says that something is silenced -- shut him up! Why? Because disliking something is a rant! That is how tolerance to imperfection is developed. --Javalenok (talk) 19:10, 11 June 2015 (UTC)

Socks Vs Toe-Socks or Shoes or Gloves

The Socks discussion assumes that there is no handedness with colored socks, ie that a sock will fit either foot. It also assumes only one property, eg colour is important. This is also important with objects such as "Shoes" or "Gloves".

But "Toe-Socks" - socks which have knitted toes- (and are popular fashion in some cultures) and Shoes and Gloves do have handedness - ie, can only fit one of the two types, so to obtain a "pair" by random selection is more complex, needing more than 3 selections. This is also the case where a sock has a distinctive emblem that is intended to be only displayed on one side, eg outward facing side.

Thus the Socks discussion should include a statement that the "socks" concept as categorized can only apply in cases that are non-handed. This is especially important when the "Socks" discussion is used in cases where handedness is critical, eg gloves, unless the normal assumed only property of "colour" is ignored as irrelevant.

Perhaps the entry should be amended to remove colour and mention handedness or better, that it can only apply to a single indexed property concept instead.

60.242.247.177 (talk) 00:01, 14 November 2015 (UTC)

The Japanese term 鳩ノ巣原理 translates to "pigeon nest principle"

鳩ノ巣原理 - "hato no su genri" is 鳩ノ巣 (hato no su) pigeon nest 原理 (genri) principle. Removing it from the list of words that use the "original 'drawer' name". Orafu (talk) 11:56, 24 January 2016 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Pigeonhole principle/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

Introduction needs a gentler introduction before formal statement. Section on infinite sets neds expansion. Tompw (talk) 15:40, 4 January 2007 (UTC)

Last edited at 23:07, 19 April 2007 (UTC). Substituted at 02:28, 5 May 2016 (UTC)

"Schubfachprinzip"?

Is "Schubfachprinzip" used in English? --Wik 13:50, 28 August 2003 (UTC)

I don't think so, so I've moved it to a sentence on Dirichlet. --Zundark 08:11, 30 August 2003 (UTC)

But Hardy and Wright in their Introduction to the Theory of Numbers refer to Schubfachprinzip of the German writers, as though there was no name for it in English. — Preceding unsigned comment added by 129.180.141.54 (talk) 05:32, 22 June 2016 (UTC)

Is it "demonstrated mathematically" that the pigeonhole principle is violated in quantum mechanics?

In a short final section claiming that Aharonov, et al. have "demonstrated mathematically" that "the pigeonhole principle is violated in quantum mechanics", I replaced "demonstrated mathematically" with "presented arguments that".

First of all, the arguments of Aharonov, et al., are controversial even as physical arguments within quantum mechanics. Second, this is a mathematical article, and the former "demonstrated mathematically" claim does not correspond to the way that "demonstrate" is used in mathematics as a synonym for "proved". Whatever one thinks of the arguments of Aharonov, et al., in no way can they be interpreted as proving a mathematical theorem within a well-defined axiom system. Their conclusions should not be presented as equivalent in reliability to the conclusion of a mathematical theorem. — Preceding unsigned comment added by Parrott SK (talk • contribs) 21:16, 26 July 2016 (UTC)

Data compression

I find it odd that the article doesn't contain any reference at all to the pigeonhole principle's importance in lossless compression theory, given that this is the primary reason I care about the pigeonhole principle. Chris Cunningham 15:32, 29 January 2007 (UTC)

"This principle also proves that there cannot be a lossless compression algorithm that will compress any file to a certain amount. If it could then two files would be compressed to the same smaller file and restoring them would be ambiguous." Could do with expansion, but it's certainly a reference. --Calair 01:41, 30 January 2007 (UTC)

Ah, indeed, yes. I'll see about expanding this later if I can track down an appropriately-licensed source. Chris Cunningham 10:24, 30 January 2007 (UTC)

Excuse me, but this statement about the principle proving "there cannot be a lossless compression algorithm that will compress any file to a certain amount" seems wrong. For example, with run-length encoding, five 1's and five 2's could both be encoded to two characters. So if you allow for making the distinction between a compressed file and an uncompressed file, then there is no problem unambiguously restoring two files compressed to the same smaller size. Furthermore, with there being multiple possible compression algorithms, it is even conceivable to have to different files compressed to both the same size and same bit content, and still be unambiguously restored - providing you allow to make the distinction between compression algorithms used. So it is just a matter of how the bits are interpreted. Perhaps what was meant is that a compressed file collides with a another file that is either uncompressed or compressed with a different algorithm? Guy N. Hurst 20:17, 14 April 2007 (UTC)

The problem here is wording. The sentence is meant in this sense: "there does not exist a lossless algorithm A such that for any file X, A will compress X to a certain amount". For instance, while run-length works for some X, encoding '11111' to 51 and '22222' to 52, it fails on '12345' because it delivers '1112131415', twice the length of the original. (Any specific file can be compressed to a single bit by an algorithm optimised for that file, but such algorithms lose out elsewhere.) I'll see if I can reword that to be rather less ambiguous. --Calair 01:29, 15 April 2007 (UTC)

I'm afraid your wording is no better. What does "to a certain amount" mean? Both "certain" and "amount" are ambiguous. Here is a precise statement which is also stronger: "there is no lossless compression algorithm such that no compressed file is larger than the original and at least one compressed file is smaller than the original". Here is another equivalent formulation: "if a lossless compression algorithm makes at least one file smaller, then there is some other file that it makes larger". I prefer the first one. McKay 04:28, 16 April 2007 (UTC)

Yes, I used a less ambiguous wording for my actual edit to the article yesterday than in my comment here, but it still had room for strengthening. I would go with your first version in a formal mathematical discussion, but I think the second is a little easier for the casual reader to absorb, so I went with that - does it look reasonable now? --Calair 04:54, 16 April 2007 (UTC)

I'd put it this way. There is no compression method that works on all finite sequences from a finite symbol set with the following three properties: (a) the original sequence can always be unambiguously recovered from the compressed sequence, (b) at least one sequence is compressed into something shorter than itself, and (c) no sequence is compressed into anything longer than itself. 70.245.199.7 (talk) 21:30, 18 March 2009 (UTC)

I'd support Calair's version (plus, maybe, e.g anonymous's one afterwards). Generally the maths articles on wiki seem geared for mathematicians rather than general readers (so, not as it should be). As shown throughout this Talk page for instance a general problem with mathematical understanding is one of language. General readers use general language not mathematical expression. Of course this is not meant to imply that ALL mathematics is comprehensible to everybody by using a general language but that perhaps all of its basics might be. IMO a general explanation should come first followed by the precise mathematical one. For instance I came to this Talk page because the Pigeonhole_principle#Sock-picking example confused me. Ironically though, when I read the first explanation of it given above (provided by someone who was confused!) I understood. The ensuing attempts to generalize math-speak (or mathematize gen-speak?) did not help my grasp at all, and this despite the issue in the end being simple. LookingGlass (talk) 11:41, 11 September 2016 (UTC)

History of the principle

There's a good article The pigeonhole principle two centuries before Dirichlet by Benoît Rittaud and Albrecht Heeffer about the history of the principle which was published in the Mathematical Intelligencer June 2014 and also in The Best Writings in Mathematics 2015. The original example of the principle was the one still used that there must be two men with the same number of hairs as each other. Dmcq (talk) 14:47, 7 December 2016 (UTC)

Thanks. I added the reference to the article. --Bill Cherowitzo (talk) 01:09, 13 December 2016 (UTC)

Proof

I know it seems trivial, but I think it would be useful for there to be a formal proof near the beginning of the article for why it is true in the finite case at least, and an explanation for why it is tautological in the infinite case — Preceding unsigned comment added by 121.215.83.165 (talk) 10:45, 7 August 2014 (UTC)

I second this and am considering creating a whole new section titled 'Logical Fallacy'. Perhaps I'm missing the basic concept here. For instance, consider the sock drawer example. If I pull out 3 socks, what is the guarantee that all 3 socks are not blue? Same for the original pigeon example; what's to say there are not 3 pigeons in one hole, or literally any other of the possible combinations. This whole thing seems to hinge on the idea that all things are uniformly distributed, where in the real world this is often not the case. — Preceding unsigned comment added by 199.168.146.48 (talk) 19:37, 4 April 2017 (UTC)

The point of the example is: if you pull three socks out of a drawer, you will have at least two of one color. If all three socks are blue, you will have a pair of blue socks. Similarly, if one pigeonhole contains three pigeons, then "at least one hole has more than one pigeon" as promised.—Anita5192 (talk) 21:51, 4 April 2017 (UTC)

I slightly rephrased and amended the socks-example. Hopefully this helps for the finite case. Purgy (talk) 08:41, 5 April 2017 (UTC)

Why m > 0 is appropriate in the first line

For reference, the first line of the article is:

In mathematics, the pigeonhole principle states that if $n$ items are put into $m$ containers, with $n > m$ , then at least one container must contain more than one item.

An IP inserted the condition $m > 0$ in the first line of this article and Tgoodwil removed it. I replaced it and Tgoodwil reverted me. An issue like this is usually settled by finding appropriate sources, but in this case I have found the sources (even the usually very reliable authors) to be almost uniformly sloppy with their presentation and those few who have addressed the condition have buried it under notation and inference in other sections of the texts. So, let me explain and hope that someone can find an appropriate source. First of all, to deal with Tgoodwil's assertion that $m = 0$ would make the hypothesis false and so give a true implication, I need only point out that this hypothesis is not a proposition (as written) but only an unquantified predicate, so there is no well formed implication here. If you attempt to quantify the statement, you would need to specify the domain of $m$ and $n$ and at the level where you usually find this result, this is given as the natural numbers. But there is the rub, some authors include 0 as a natural number and others don't. With very few exceptions, the authors of the texts I examined do not include 0 as a natural number, so $m > 0$ is implied by these authors without them actually stating it. Since we (WP) don't take a stand on including 0 or not, it needs to be made explicit in our statements. It is also not necessary to state the Pigeon-hole principle as a "pseudo" conditional; I have found one reference which purposely did not not use the "if ... then ..." construction in their statement of the principle. I also came across (unfortunately, only once) an author who explicitly stated what is implicit in most accounts, namely that placing the "pigeons" in "pigeonholes" implies that each pigeon is placed in a pigeonhole. This of course, in turn, implies that there must be at least one pigeonhole. Some texts eschew this informal approach to the principle and either talk about partitioning a non-empty set into $m$ pieces (and you can't partition such a set into 0 pieces) or functions between sets of different cardinalities not being injections (most definitions of functions will not allow an empty codomain). So there is my dilemma. The condition is valid and should be stated explicitly, but you have to dig it out of the sources (at least those 20-25 that are available to me) and that would generally be considered WP:SYNTH.--Bill Cherowitzo (talk) 00:22, 24 July 2017 (UTC)

The problem seems to me that the lead contains two very slight different theorems, the second one being 'There does not exist an injective function whose codomain is smaller than its domain". One can have an injective function with a null domain and codomain. However there are no functions injective or otherwise with a non-null domain and null codomain. Confusing this with the usual pigeonhole principle is what is causing the problem. The sources don't state m>>0 so the alternatives are either to leave iit out and not say it, or to be rather a bit more careful in dealing with the zero or null case. I think it would probably be acceptable to deal with it properly in the main text and leave it ambiguous in the lead but don't have a strong feeling about it. Dmcq (talk) 11:20, 24 July 2017 (UTC)

In the sources where both versions are mentioned, the function version is referred to as a formal version, while the other is the informal version. I guess that one can argue that in going over to the formalization, something is lost and so the statements aren't exactly the same. However, a value of formalization is that it makes precise what is by nature imprecise. --Bill Cherowitzo (talk) 16:30, 24 July 2017 (UTC)