Talk:Pigeonhole principle

Softball team section

The section points out that if you have 7 people who want to play softball, and there are only 4 teams, 1 team must have at least 2 of the 7 players. I don't understand the mathematics of the section, but it seems obvious that 5 people and 4 teams give the same result. Equivalently, if you have 7 players and 6 teams, one team must have 2 of the 7 players.

Perhaps I'm missing something here because of some ignorance about mathematics or softball, so I didn't feel competent to edit the page. TomClement (talk) 02:09, 8 March 2017 (UTC)

You aren't missing anything. The significance of this example lies in the fact that there is a formula which gives the correct conclusion. In the simpler cases that you mentioned, you don't need to rely on a formula since you can just reason it out and the answer is very obvious. With larger numbers you would need to put more effort into obtaining the correct conclusion. The 7-4 example is not as immediate as these others, but it is still small enough so that you can reason through the example and see why the formula is correct. --Bill Cherowitzo (talk) 05:11, 8 March 2017 (UTC)

If you don't need to rely on a formula for 5 players and 4 teams, then you certainly don't need a formula for 7 players and 4 teams, since it's trivial that 7 > 5. This section thoroughly confused me due the choice of 7/4. Reading this talk page section, it seems as though the only purpose was to give a formula for a less trivial case. If that's true, then perhaps it would be better to say it's true for 5, present the formula (even though it's obvious) and then extend the formula to 7 (even though it's obvious that 7 > 5). Or perhaps, to show how the formula is derived for arbitrary numbers, and then using 7/4 as an example. But as it stands, it's a real head-scratcher and detracts from the article rather than contributing to it. Learjeff (talk) 20:19, 6 August 2018 (UTC)

I think you are missing the point here. It is also true that 9 > 5 and 101 > 5 so you are claiming that you don't need a formula for these cases? The answers for 9 players and 4 teams is that some team must have at least 3 players, and in the other example some team must have at least 25 players. These results are not in any way related to the number 5. Actually, you don't need a formula for this in the same way that you don't need a formula to solve quadratic equations. You can always work it out. A formula is just a way of codifying this process, so that when the numbers change you don't have to go through all the steps again (those steps, if carried out with general rather than specific numbers, form the proof of the formula). The 7/4 example was chosen to illustrate that the formula works correctly. Smaller numbers would present no challenge to the formula's ability. --Bill Cherowitzo (talk) 21:22, 6 August 2018 (UTC)

On the evitability of hash table collisions

The pigeonhole principle arises in computer science. For example, collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array. A hashing algorithm, no matter how clever, cannot avoid these collisions.

If the number of items stored in the hash table is less than the number of buckets, there need not be any collisions. If a perfect hash function is used (an algorithm that is exactly as clever as it needs to be), there are guaranteed to be no collisions. The number of possible keys is irrelevant; what matters is the actual number of items stored vs. the actual number of buckets -- and even that's assuming a hash table that does not dynamically resize.

I'd remove this example altogether because the caveats make it not very insightful. I hope someone with a name agrees. 82.95.254.249 (talk) 21:06, 2 November 2017 (UTC)

I agree and I have removed it. I think it was a good example, but it was worded incorrectly and unsourced. If another editor wants to reinsert it, it should be reworded and cited.—Anita5192 (talk) 21:23, 2 November 2017 (UTC)

The way strong form of the pigeonhole principle is stated is unnecessarily complicated

I propose rewriting it as follows:

Let q₁, q₂, ..., q_n be positive integers. If more than

$q_{1}+q_{2}+\cdots +q_{n}$

objects are distributed into n boxes, then there exists a box i that has more than q_i objects. The simple form is obtained from this by taking q_i = 1 for i = 1 to n.

Misleading image

If you want yer actual pigeons, Trafalgar Square used to be full of them.

Those Columbidae in the article pic are doves. MinorProphet (talk) 17:31, 17 January 2021 (UTC)

Applications to Computer Engineering

I think it makes sense to discuss applications of the Pigeonhole principle to Computer Engineering because it comes up so often in memory management and allocation, but some editors disagree. CessnaMan1989 (talk) 16:54, 13 September 2021 (UTC)

Quantum mechanics section citation dates don't make sense

The article says that someone proposed that quantum mechanics violates the pigeonhole principle but that 'later' research has shown this might not be the case, but the citation on the proposal is 2016, and the two refutation sources are from 2014 and 2015 respectively. (Also, all of this is now six years out of date at the least, which is relatively large for a rapidly moving field like QM.) Seems like this needs revision? --Nerd1a4i (talk) 07:45, 7 April 2022 (UTC)

Yes! How about that article:

Photons suggest the weird quantum pigeonhole paradox is real | Science News

?? :) 80.215.65.208 (talk) 11:21, 20 July 2022 (UTC)

https://www.sciencenews.org/article/quantum-pigeonhole-paradox-photons

Sorry.

It links to a more "scientific" article on pnas.org where one can read:

"In summary, we have implemented the quantum pigeonhole paradox by transmitting three single photons through two polarization channels, which demonstrates the pigeonhole paradox definitely at the level of individual quantum particles (31). The experiments show that in addition to the condition of well-defined pre- and postselected subensemble, noninvasive weak measurement is also required to observe the counting paradox. We implement the desired measurement indirectly by analyzing the measurement effects order by order and reveal the paradox will not survive under high-order measurement."

Creds to Ming-Cheng Chen, Chang Liu, Yi-Han Luo and Jian-Wei Pan (dating from end 2018, start 2019). 80.215.65.208 (talk) 11:54, 20 July 2022 (UTC)

\lfloor(n - 1)/m \rfloor + 1 = \lceil n/m\rceil is not true when n/m is integer

Second paragraph states "For arbitrary n and m this generalizes to k + 1 = \lfloor(n - 1)/m \rfloor + 1 = \lceil n/m\rceil ..." This is not true when n/m is integer. My sugestion is to replace by "For arbitrary n and m this generalizes to k + 1 = \lceil n/m\rceil ..."

Renato.carmo (talk) 15:58, 8 April 2022 (UTC)

In answer to both the Computer Engineering & Quantum mechanics topics above... and with some of txt of the topic "Why m > 0 is appropriate in the first line" in mind

Well when you think of it, real life violates the pigeonhole principle. Let's say I am blind and have a drawer with 50 thousand blue socks and 50 thousands black socks: do you really believe I will need to pull out only 3 to have a guaranteed pair of either black or blue socks? Assuming a uniform repartition of the 2 types in the drawer and that the color is the only difference between all those socks here. It's like saying in a class of 366 students (367 if taking leap years into account) it is guaranteed to find a pair with the same birthday: true for computer, false for real life unless some divinity has forcedly distributed all possible birthday dates without exception! Let us be careful with generalization and thus the examples we present. In clear text I strongly agree with the 2 first mentioned topics above. The third one about m>0 is interesting because it talks about what is implicit in the pigeonhole principle and those implicit rules are enough to understand that this principle is rarely usable in real life, outside of computer science. I am no expert in QR so will not judge the validity of the above statement but can intuitively imagine that it's not hard in physics to violate this principle as soon as someone fails to realize the implicit rules are not met. In a way I'm not talking about violation but misuse of the pigeonhole principle. 80.215.65.208 (talk) 11:16, 20 July 2022 (UTC)

Sorry, but your comment shows you don't really understand what the article is talking about. Referring to the sock example: if you pull three socks from the drawer, you will either have 3 blue socks, or 2 blue and 1 black, or 1 blue and 2 black, or 3 black; in any case, you will have a pair of two socks of the same color (although you can't know in advance if it'll be black or blue). I also don't know why do you think that the birthday example is "false for real life" -- unless you can somehow show us how 367 people can all have 367 different birthdays if there are only 366 possible birthdays. JudgeDeadd (talk) 12:25, 31 August 2022 (UTC)

Hairs and London.

Could someone explain the London example and the hair ? I feel like this makes sense from a syntactic sense and when you replace pigeonholes and pigeons with population and hairs, but in real life, I don’t think this would actually work like that, since you don’t put humans in pigeons, metaphors or not. Could somebody explain ? Kwikygoat (talk) 17:44, 28 April 2023 (UTC)

Edit : here’s what I struggle with and don’t really understand. If we assign a person to the pigeon hole corresponding to the numbers of hairs on its head, what tells me on the 1 000 000 than there won’t be 100 000 with 12 hairs in the column 12 and 900 000 with 100 hairs in the column 100 ? Still, there would be way more than 10 Londoners with the same amount of hairs (here 900 000). So why would we suppose there is supposed to be the same amount of people for every hair, that is 9 people have 1 hair, 9 have 2, 9 have 3, etc… — Preceding unsigned comment added by Kwikygoat (talk • contribs) 19:08, 28 April 2023 (UTC)

London currenly has a population of about 8,799,800 (and increasing). The number of hairs on a human head is not likely to exceed 150,000. Hence if the 8,799,800 people (pigeons) in London are "placed" (categorized) in 150,000 "pigeonholes" (categories), they cannot all be in separate categories. There must be at least one pigeonhole (category) with at least two people (in fact, many) placed in it. That is, there must be at least two people in London who have the same number of hairs on their heads.—Anita5192 (talk) 19:10, 30 April 2023 (UTC)

More criticism of the London Hair example

Many readers (perhaps only the non-mathematicians?) will argue that of course there must be two people in London having same number of hairs, in particular the many bald Londoners, so why invoke some pigeonhole principle? This is an example of a problem where mathematics are not an appropriate way of thinking. More convincing would be "in this company two employees have the same birthday", or "have the same code for opening their padlock".

three gloves analogy

I don't like the three gloves analogy makes things more confusing if anything, the pigeonhole idea is already an analogy, i don't see the reason for an analogy ontop of another analogy. 2407:7000:986C:1300:A421:58E0:3174:9124 (talk) 01:25, 9 April 2024 (UTC)