Talk:Pigeonhole Principle

From Math Images
Revision as of 15:34, 20 July 2011 by PhoebeJiang (talk | contribs) (Richard Comments 7/20)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Response to Checklist

Messages to the Future

  • Made two suggestions for future editors.

References and footnotes

  • Original sources of "borrowed" images are marked if you click them.
  • Direct quotes are cited.
  • References are listed with links at the bottom of the page.

Good writing


  • This topic “Pigeonhole principle” is my personal favorite! The main image is appealing. "More Mathematical Explanation" is comprehensive. I gave a lot of examples for readers to know this principle better. I believe those examples make this page a lot more interesting than other pages.

Quality of prose and page structuring

  • The beginning paragraph defines pigeonhole principle and provides another definition, name.
  • Each section is related to the main topic.
  • Real world applications and subsections in the mathematical explanations are listed from easy to hard, from fundamental to expanding. I hide some long proofs and just show the statements, in case people don't want to know the proof but just the examples themselves. The heaviest math is in “Why interesting.” Well, they are not heavy math but hard to understand.

Integration of images and text

  • Every image is referred in the context. In every image, the denotations are noted and readers know what each symbol means. Some images are just for better structure; they are not really illustrative (i.e. birthday cake, socks, hair, cards).
  • Readers are clear about which picture they should look at while viewing this page. Sometimes they can get inspired by the picture and know how to prove the problem.
  • There are no large chunks of words.

Connections to other mathematical topics

  • There is a link to another mathematical topic outside of Math Images.

Examples, Calculations, Applications, Proofs

  • The equations, calculations, and examples are clear to readers.
  • Every statement or property has its proof.
  • I wrote a summary and some guiding text to help people know how to solve this sort of problems using pigeonhole principle. (especially the “how to construct pigeonholes” section)

Mathematical Accuracy and precision of language

  • I try to make everything as clear as possible. Hopefully readers with any level of math will understand it.
  • I try to make everything error free. Corrections and suggestions are appreciated.
  • The definition of every mathematical term, theorem or rule readers might not know is either explained in the body text or via a mouse-over, or linked to another page.


  • Texts are short, not very long, and broken up by images or broken in paragraphs.
  • Mathematical terms are boldfaced.
  • Hide and see is appropriately used.
  • No awkward white chunks.
  • No weird computer codes.

Thank You

Comments from Chris 7.20.11

This is both a fun and interesting page. You've done an excellent job with this. My comments are mostly minor ones.

Thank you very much Chris!! Very helpful comments! Phoebe 7/20

Near the end of the Basic Description, you make an excellent statement that I think belongs instead in the intro: "The pigeonhole principle (PP) itself may seem simple but it is a powerful tool in mathematics." I'd make it the strong conclusion to your intro section.

I like your suggestion! You want me to move only this sentence or the whole paragraph this sentence is in?

Basic Description

  • Layout issue: It's clear on my browser that the last two paragraphs begin "The pigeonhole principle is also called the Dirichlet.." and "The PP itself may seem..." It's hard to tell. however, where the other paragraph(s) end(s) and begin.
I see. Fixed it.
  • Paragraph 1, Sentence 2 (P1S2) Is the principle really famous?
I think so... I've learnt it in middle school.
  • P1S3 Add "that" between "principle is" and "for any."
Fixed it.
  • Near the end of that long paragraph (if it is only one paragraph), there must be at least two pigeons in a pigeonhole.
Fixed it.

Interesting Applications

  • Birthdays: P1S1: Remove "the" from between "including" and "leap."
Fixed it.
  • Hair: P1S2: Make "hair" into "hairs a human normally has."
Fixed it.
  • Chairs: P2S1: Instead of "(see the two figures below)", add a new sentence that talks about how the first two examples show two ways of partitioning the chairs without two empty chairs next to each other.
Fixed it. Like your suggestion!
  • Strangers or Friends: really well done!

More Mathematical Examples

  • 3. This example is very hard to follow. At the very least, give a concrete example to relate all the variables with subscripts to.
Good to know. Add a more concrete example.

Summary *P1, Subsection 3. You didn't let the limit be 50 or "want to have" the limit be 50; the limit ends up being 50 because only 50 distinct groups can be made.

Fixed it.

How to Find the Bounds

  • P1S1 Change the tense to past perfect; "we have only been told" and "whether we have reached"
  • P1S3 Either make the question are full sentence or say "This leads to the interesting question of how to find the bounds."
Fixed them.
  • Examples #1: Do you want a direct link to another website? (Ramsey Numbers) I don't think that's the convention for Math Images. I'll check tonight at Swarthmore; maybe you can also investigate this.
I'm sorry if I did anything inappropriate. I don't really want to link to another website either. It's just that I don't have time to make a page for Ramsey Number, but I put it as a future direction for other people. How about I create a helper page and link PP to Ramsey Number? I'll add more things to it if I have time and if I'm not able to do that, future editors could investigate it as well. What do you think?

Richard Comments 7/20

  • Phoebe, the page looks great! I know you've done a ton of editing and fixing already, so take these comments however you'd like. Richard 7/2
After reading this a second or third time, I'm realizing more what I was having trouble saying last time. In the basic description, you outline these two great ways to think about the pigeonhole principle: (1)a very intuitive way of thinking in terms of pigeons fitting into pigeonholes (2)a more "mathy" way with average and maximum value. You do a great job of explaining why they are the same in the basic description, but I think you are selling yourself short on the math side of things especially with many of the examples that you use. I guess what I'm trying to say is that there's more math to this than your examples show. For example, you could use math to describe the suit of cards example as well as describing it in terms of pigeons and holes. you could say that the avg value=5/4 so the max must be at least that, and since we can't pick a fraction of a card, there must be at least two cards of the same suit. I think it could be helpful to describe each example using both ways (1) and (2) like you did in the basic description.
  • This also provides the potential for a MME that is more than just example. I think you can more thoroughly describe avg value and max value pictorially and with words. By defining average, you can show mathematically that there must be a number in the non-empty finite set that is greater than the average.
I like your idea. Good point, but I might need more time to make those changes. For some easy examples, I didn't apply the max and avg value because they are understandable and pretty obvious. Maybe I'll just add those description to some harder ones.
Alright, I add the max and avg thing to each example. They look better now! Phoebe
  • For Interesting applications number 6 I'd reword the main statement to be something like "In a room with six people in it, there will always be either 3 people who know each other or 3 people who don't know each other.
  • In the same example, I'd get rid of "This seems to be a chaotic problem but we need to find order in this mess." and "How should we prove that it is true all the time?" You can start the section off instead with something like "We can use a diagram to help us show that this statement is true. Note that these..."
Fixed it.
  • you sort of just say that by the pigeonhole principle, at least three lines must be the same color. I think it would be useful for you to show how you got that in terms of avg and max value here.
  • I'm a little confused still by MME example 3.
And you used the wring less than symbol I think...try this one  \leq
Fixed it. I think I made some changes after you viewed it. Other people thought that this part is confusing as well, so I added more guiding texts to this problem. Thank you for letting me know.
  • For How to Construct example 2, I think you could maybe put this one in terms of pigeons and pigeonholes as well and put the factorial form of 15 choose 2 like you have for the example 11 choose 4.
Fixed it.
  • In your summary section, you mention limit several times and I'm not exactly sure what you're talking about.
Think about how many possible ways you can find in the problem; this is your restriction and also the pigeonholes you are trying to find. Limit means the restriction. Fixed it.
  • Same with bounds. Maybe define limits and bounds in terms of the principle.
Fixed it. Add a mouseover
  • This is a really cool page, Phoebe. I really like its roots in application and that you use some pretty cool examples to teach the topic in the process.
Glad to know. Thank you for spending time on my page!

Richard 7/20

Comments from Flora 7.16

General Comments

  • This page is very good. All the examples are interesting and thoughtful.
  • My suggestions sometimes are not all right. You can just ignore if they are wrong, or you can explain to me.
  • The page is almost done, so all my suggestions are for tiny confusing points.
  • The only one part I think you may need a big work is the 1st example in How to construct pigeonholes, I could not get your answer from your example.
Thank you Flora for looking at my page! You've made lots of important and helpful comments!


  • The intro is interesting and attractive.But you may want to use fewer sentences to introduce the image.
I see your point, but I don't know which sentence should I leave out... All of them are very important...

Basic Description

  • The first sentence you say: "If more than n items are put into n pigeonholes, then at least one pigeonhole must contain more than one pigeon." First you say "items", then you change it to pigeon. If you want to introduce the pigeonhole theory in Basic Description, then you do not include the same thing in your Intro section.
I don't know what happened but I changed it before and somehow the old version showed up. Thanks for letting me know!
  • In the green balloon, I saw the explaination of "non-empty" and "finite set". I'm wondering maybe you need to define "set" first. In "average value"'s balloon, I think your explaination is more confusing than "average value" itself.
Added the definition of "set". Yeah, when I was defining the average value, I found the definition more confusing than the original term. I put up a new definition.
  • I am not sure if "the average value of\frac{pigeons}{pigeonhole}" is right. I understand what you want to say, but \frac{pigeons}{pigeonhole} is already an average value. And in next sentence you say: "the maximum value of the number of pigeon per pigeonhole should be greater than one," same issue. Usually we say the maximum value of "something." The number of "Something" should be bigger than 1, than we can make the comparison.
Good point. I'm gonna make it clear.

Interesting Applications

  • This part is very clear and easy to understand.
Thank you
  • The structure in section 2.Apair of socks is a little wierd, "a matching pair." is under the image, but not with the whole texts body. You may want to delete one blank line under the bold sentences to move "a matching pair." up one line.
It is about the size of the user's browser. I move the text up, so this kind problem won't happen again.
  • In section 5. Chairs, it's a little confusing why you make the left figure in 2 rows. In your example, 9 people will seat in 1 row, where there are 12 chairs. But in the first figure, it seems that there are 2 rows. You could change your image to that 1 row with 12 triangles to show that there is 1 row with 12 empty chairs. And draw 9 circle beside to show that there are 9 persons who want to seat on those chair.
Agree. I changed my image cause I found out that maybe more people would understand the updated image.
  • You can create more images like your right figure to show more possibles that at least consecutive set of 3 chairs are filled with people.
Good point.
  • Also in this example, it is not necessary to devide people into 4 groups. If there are only 2 groups, you can insert all 3 empty chairs together but still left at least 3 consecutive chairs filled with people. This example is interesting, and you can talk about more possibilities. For me this is an example that there are 12 holes, but you need to fill these hles with 3 empty chairs.
True, you can think of this question that way. I'd rather make it into four groups because it is easier to explain why one group definitely has 3 filled chairs. Also, I added a few lines to point out why there are four groups; because some groups may have zero filled chairs. What do you think about it now?
  • 6.Strangers or Friends. I fond this part is hard for me to understand. You say: "Draw lines joining every pair of two points," but I find that the highest point has no line with lower left point. And you say: "What the statement graphically means is that we can always find a pink triangle (3 mutual friends) or a green triangle (3 mutual strangers) in this hexagon." I find a triangle with all 3 sides in green. But it is hard to find, you may change your image a little bit to make it clear which triange is satisfied with the situation.
Oops, my bad. Didn't realize that. Thanks!

More Mathematical Examples

*In the first example, it is hard to read for all notations. You could bring in a real example with numbers to say the example is true.

  • In the second example, You could add one sentence to say that there are 50 pairs(subsets), to make sure the reader know what subset is.
Fixed it.

How to Construct Pigeonholes


  • I'm confused about the 1st example that you say "a square of side length 2," is it true? Or you mean the area is 2? If the side is 2, then the largest distance of random 2 points will be the side, which is also the hypotenuse of the right triangle, and it is 2, but not \sqrt{2}.
  • The example you have in figure 5 is not very related to pigeonhole theory, because you simply put 4 points in the corner and 1 in center. And you calculate the largest distance with 2 points on the corner, but they are not in the same pigeonhole.
  • Also if I put all 4 points on the corner, and 1 random. then the largest distance will be the diagonal of the biggest square, which is 2 \sqrt{2}.
I deleted the first example because it is not very good and I don't want to confuse the readers. Plus, three examples are enough for this section.
  • I like the images you have in example 2. You could make a similar image for 6.Strangers or Friends. But the hiden image is not easy to find. Could you move it down and say this is the solution?
  • For your example 3. you may want to define the combination notation first or just avoid using them, since you did not use them again in the rest of you page.
I may need the combination notations in order to get 105 and 6 but I'll definitely put up more explanation to it.
  • Could you explain C^4_2 = \frac{4\times3}{2} = 6 more clearly? It is confusing why choosing 2 over 4.
Fixed it.
  • Could you make "pair of courses" clearer? Is that you only make the same two courses into a pair or you make all 15 courses into pairs? Or you mean in 4 courses of each student can be make into pairs?
I pair up all the 15 courses. And I pair up the 4 courses each student chooses. Good to know that I'm not being clear. Added more explanation. Is it better?
  • Example 4 is really smart and interesting! But it may cause confusion why all the groups are disjoint. Could you explain that?
Yes. They are disjoint because they don't have the same elements. They don't have the same elements because each group is expanded by adding multiples of a different odd number.
That is more clear, you just need to add that sentence to your page.Flora 18:07, 17 July 2011 (UTC)


  • It is a little hard to follow your summary, since you talk all the four examples, but you don't have images there. Readers may be lost. For me I have to go back to each example to see what you talked about. Maybe you can move this section to the bottom of each example. You can also ignore this suggestion. It is not a big problem.
I don't know. If the readers read those 3 examples carefully, they'll know what I'm talking about. And if I move them at the bottom of each example, it won't be a summary of "how to construct pigeonholes." I admit that this summary needs more work but this is the clearest summary I could do...== I appreciate it if other people could help me with this summary.
It's fine if you just keep the oringin version.

How to Find the Bounds


  • For the first example, it is confusing about the notation.
I'm sorry but could you tell me which part is confusing? You mean you don't understand R (3, 3) ?
Yes, that's the point. The explaination of this notation is not very clear.
  • For the first example. The image only illustrate one possibility. But you do not provide a proof of your conclusion. If you trun any green line to pink, you can get a pink triangle. Turn other 2 pink to green you can get a green triangle also. I'm also confused if you can make all 4 lines from one point to a single color to make she or he know or does not know any other ones.
Since we want to prove that a number is the best lower bound, the basic idea is showing that a smaller number leads to a contradiction or an error. As I stated earlier, I just need to give a counterexample to prove that 5 doesn't always work. No need to give a proof~
I understand your point. But as what I said, I think if you turn a green line to pink than you can get a pink triangle, so 5 works also.

Why It's Interesting

  • In the example of Taking Medicine, you say this section may cause some confusion. I think your proof is very interesting. The confusing point may be that the first bold sentence is true, but it is not an argument. For normal people they will think any 14 days they take one pill each day will satisfy your condition. But I don't know how to help to improve this sentence, sorry.
  • In the example of Domino, the figure is more under your statement but not left.

General Comments

Pictures will be so cool for this one! Richard 6/29

Phoebe 18:35, 8 July 2011 (UTC)Yeah, I realized that too. I'm not finished with this page yet, so I'll work on it! Thanks!
Ps: We have pretty much the same font color~ lol

Richard 7/8

  • This page is really really cool. You've got a ton of opportunities for applications and pictures.
  • I'd make you Interesting Applications Section a "Why It's Interesting" section. I think this is more standard for math images. You can go to the edit with form tab to start that section.
  • You really only use examples to go into the topic. Is there some graphical proof or derivation that you could include?

Phoebe 21:06, 8 July 2011 (UTC)

  • First of all, thank you for leaving comments!! I use a different color to distinguish us.
  • As you can see, I intend to use those 10 examples to lead in, giving readers a basic idea of what Pigeonhole principle is and how it works. The principle itself is pretty self-explanatary, so I didn't include the proof of this principle. Then, after you know how this simple principle helps in daily life, you will see the MME section with more examples and tricks about constructing pigeonholes. This is how I conceive this page, from easy to hard, from the description of pigeonhole principle, to applications (lead in), and eventually the hardest part, MME. So do you think I should put the applications under "Why interesting" after MME? If so, I'm afraid readers will feel overwhelmed by MME section. What do you think?
Okay, I see what you mean and I understand where you're coming from. To me, this page starts out with a very intuitive topic/description, and then gets more complicated in the current MME. What if there were some middle ground? I'm thinking like describing what average value is mathematically or something to put at the beginning of the MME to sort of segway into harder examples. There's a lot of examples on this page, and as the reader, I think it gets to be more difficult to pick out which examples are the most important ones. I don't know.... Richard 7/12
Richard! Check this out. I want some simple and interesting examples to lead in and I also want to put some hard applications under "why interesting" as you suggested. So, I'm thinking about splitting them into two sections, leaving the first 4-5 examples where they are now and put the rest of the examples after MME. Plus, those ten examples seem to be really long together. And people could apply those tricks mentioned in MME to see how the tricks work via the hard examples at the end of the page. What do you think about this idea? :) Phoebe 20:38, 13 July 2011 (UTC)
  • Pigeonhole principle is basically about combinatorics, about numbers. This principle itself doesn't have much to do with pictures. I agree with you about the pictures. I personally like graphs than simply words and numbers, so I'm thinking about adding more illustrative pictures on it.

  • Phoebe, this page is looking great! I can read it through again if you want me to, just let me know when it's ready! Richard 7/12
  • Phoebe 03:16, 14 July 2011 (UTC) Yeah actually could you read it through one more time, please? Tell me where I need to explain more precisely. Thanks a lot!


Richard 7/8

  • I'd reorganize this paragraph to something like this:
A pigeon is looking for a spot in the grid, but each box in the grid, or pigeonhole, is occupied. Where should the poor pigeon on the outside go? No matter which box he chooses, he must share with another pigeon. If all of the pigeons fit into the grid, here is definitely a pigeonhole contains more than one pigeon. This concept is known as the pigeonhole principle.
  • I think it's important to introduce the topic here in this section(I added a sentence at the end in my edit above).

Phoebe 21:05, 8 July 2011 (UTC)

  • Agree. Fixed it!

Basic Description

Richard 7/8

  • In the first sentence, change "items" to "pigeons" or vice versa for consistency.
  • In the second paragraph, I think that this quote is more confusing than helpful. I feel like you generalizing the same thing in your own words would be waaaaaay more helpful.
  • It might be helpful to define "average value" and "maximum value" (maybe with a green mouse-over)
  • I'd delete "Although the two versions look very different, they are mathematically stating the same thing." and into the next paragraph, "To know why they are the same," and start with "Consider the main image instead". I think it's unnecessary to say.
  • Maybe change "bigger" to "greater"???? That sounds more mathy to me.
  • What's "its" referring to?
"Thus, its maximum value should be bigger than one as well, which means that there must be a pigeonhole contains more than one pigeons. Now we know that the two versions are actually talking about the same math principle."
  • Be careful with words like "pretty obvious". You're assuming a lot of the reader.
  • Move the sentence "Here are 10 exciting real life applications listed from easy to hard for you to have a better grasp on this famous principle." into the next section before the first example.

Phoebe 21:24, 8 July 2011 (UTC)
  • You have a lot of good points. I totally agree with you.
  • Fixed all of them. Are they better now?

  • Rebecca 02:35, 16 July 2011 (UTC) Phoebe, I'm Becky and I give feedback on many of the Math Images pages. I have a few suggestions for this page...
  • I would include mouseovers for "non empty" and "finite" because I think that if someone doesn't know what a maximum value or an average value is, they wont know either of those words either.
  • It's great that you introduce the general pigeonhole principle and then use explain the implications for the image. It's a logical order, and I think your approach is great!
Thank you Becky!!! Appreciate all of your comments! <3 Added the mouseover.

Interesting Applications

Richard 7/8

  • This section is awesome awesome awesome.
Phoebe 23:04, 8 July 2011 (UTC)Thanks!
  • Rebecca 02:58, 16 July 2011 (UTC) I agree- I like how you show people that these paradoxes must be true rather than formally proving them. It makes the page really interesting.
That's what I want!! Thanks!!! Phoebe 16:13, 16 July 2011 (UTC)
  • Pictures would be really super cool here. The way its formatted right now makes it seem longer than it actually is, especially with the table of contents. One way that I'd think to format this is like the "More than just shadows" section of Solving Triangles. Assign a picture to each example, and make two columns where the picture and text alternate sides. The picture doesn't have to be super complicated. The birthday one could just be a cake or something. Make it look more visually appealing.
  • This will also help the table of contents because you'd have to make each of the ten headings just bolded words, and not section titles.
Phoebe 21:27, 8 July 2011 (UTC)Guess what! I'm thinking about the same thing!
  • Some of the example descriptions get a bit wordy. For the purposes of these comments I'll just talk about the first one as an example and then say which ones were more confusing.
  • For the birthday one, you could make it more clear by changing "Under the worst condition when the first 366 students have their birthdays from January 1st to December 31th, the 367th person has to be born on any day of the year. Thus, there are definitely two of the students who have their birthday falling on the same day." to "Under the worst condition when each of the first 366 students have their birthdays on different days from January 1st to December 31th, the birthday of the 367th person must be a repeat of one of those days. Thus, there are definitely two of the students who have their birthday falling on the same day."
Phoebe 22:34, 8 July 2011 (UTC)Yeah, yours is waaaay better.
  • Numbers 5 and 9 could be a lot clearer with good pictures.
Phoebe 23:03, 8 July 2011 (UTC)Add some pictures.
  • Number 7's main statement is confusing to me.
Phoebe 23:13, 8 July 2011 (UTC) Could you please be more specific about it?
I understand what you are trying to prove, but I think the statement is wordy. What if you say something like: " Some n number of people are at a party. There are always at least two people who shake hands with the same number of people."? But even with the way I worded it...It' awkward. Richard 7/12
  • I really like how you relate this one back to the pigeon/pigeonhole metaphor.
  • Phoebe 23:03, 8 July 2011 (UTC) Thanks. I though it may be easier to understand if I do this.
  • Number 8 is very confusing. That's the only one I don't understand.
Phoebe 23:55, 8 July 2011 (UTC) I made some changes. Try to make it as clear as possible.
I'm still a bit confused by this. If he has to take at least one aspirin a day, does he take 14 consecutively in a period of 14 days? I think that's where I'm confused. What statement are you trying to make? Also, where did you get 59? Richard 7/12
That is one possible answer. But he could also take 14 aspirin in less than 14 days, say he could take 14 aspirin in only 3 days. In other words, if he wants to try to avoid taking 14 aspirin during certain period, he can't do it. He may avoid taking 15 aspirin during a period of consecutive days. However, this statement is trying to say that you can always find a period of consecutive days where he takes exactly 14 aspirin. Am I being clear enough or not? Please ask me more questions if you are still confused. :P
How did I get 59? Since you add 14 to every term in the first inequality, you'll get 45 + 14 = 59 for the very last term.
Maybe I could generalize this statement instead of using numbers 45, 14, 30. (i.e. he has to take n aspirin over a m day period. Then there is definitely a period of consecutive days where he takes exactly n - m -1 aspirin.) Do it make more sense now?
  • Number 10a is awesome! Great, clear description!
Phoebe 23:55, 8 July 2011 (UTC) Good to know. Thanks!
  • For 10b, I didn't know exactly what you you were trying to show until you had already started to prove it. This one might be in need of some more clarity in the initial description of the proof and statement.
  • Typo:"situation" should be "situations" in "Since there are over 32,000 possible colorings, we could not draw and check every one of the situation."

Fixed it. What do you think about this part now?

  • Rebecca 02:49, 16 July 2011 (UTC) "Here are 6 exciting real life applications for you to have a better grasp on this famous principle." I would say "real world applications to give you a better grasp of this famous principle."
  • "Under the worst condition when each of the first 366 students have their birthdays..." I would say "In the most extreme condition"
  • "This example may sound impossible to believe but mathematics, more precisely, the seemingly meaningless pigeonhole principle tells you it could happen." I would say " This example may sound impossible to believe, but the seemingly obvious pigeonhole principle tells us it must be true."
Fixed all of them. Thank you.


More Mathematical examples

Richard 7/8

  • Number 1 is confusing.
  • For number 2, wouldn't it just be easier to choose all of the odd numbers, knowing that they are not consecutive and that there are only 50, then we know that the 51st must be even and next to an odd number.
Phoebe 02:10, 9 July 2011 (UTC)Yes, you are right.

How to Construct

Richard 7/8

  • I was a bit confused by these examples.
  • This might also be a good point to derive or prove the principle explicitly with the math for average and maximum values????
Phoebe 03:09, 9 July 2011 (UTC) I tried to fixed those confusing examples. Maybe some of them are still not very clear. I'll work on them later. Please feel free to tell me where should I improve. Thanks!