Talk:Pigeonhole principle

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	B Class	High Priority	Field: Discrete mathematics
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. Introduction needs a gentler introduction before formal statement. Section on infinite sets neds expansion. Tompw (talk) 15:40, 4 January 2007 (UTC)

[edit] "Schubfachprinzip"?

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

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

[edit] 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)

[edit] 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)

[edit] 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)

--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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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) Hotpanda 01:21, 27 March 2007 (UTC) Hotpanda 01:21, 27 March 2007 (UTC) Hotpanda 01:21, 27 March 2007 (UTC) Hotpanda 01:21, 27 March 2007 (UTC) Hotpanda 01:21, 27 March 2007 (UTC) Hotpanda 01:21, 27 March 2007 (UTC) Hotpanda 01:21, 27 March 2007 (UTC) Hotpanda 01:21, 27 March 2007 (UTC) Hotpanda 01:21, 27 March 2007 (UTC) Hotpanda 01:21, 27 March 2007 (UTC)

[edit] 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 source 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)

[edit] 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.