Pigeonhole Elementary School has 500 students. Show that at least two of them were born on the same day of the year.

Question

I'm having a hard time grasping the concept of pigeon hole problems, can someone give me a step by step of how they would solve this pigeon hole problem? like an algorithmic approach

Answer 1

You can find the analogy on this exemple , if you have 13 persons , there are atleast 2 born on same month, since there are only 12 months in the year,they could all be born on same month ofcourse but we can be sure that ATLEAST 2 of them was born on same month .

Answer 2

There are $365$ days in a year .Since there are $500$ students, therefore atleast 2 students(pigeons) must have the same birthdate(pigeonhole). In fact, there are atleast $500-(365+1)=134$ students, amongst whom atleast $2$ share a date of birth.

Answer 3

Let's look at this student by student.

If the second student has the same birthday as the first student, we have two students with the same birthday, so we are done. So suppose the second student was born on a different day from the first student.

Now let's look at the third student. If she shares a birthday with one of the previous two students, again we are done. So let's suppose that each of the first three students have a different birthday.

Continue in this fashion until we get to student 366. If any of the previous 365 students shared a birthday, we would have finished, so each of students 1 to 365 must have a different birthday. In other words, we have a student with a birthday on each of the 365 days of the year. So whenever student number 366 has her birthday, she shares her birthday with some student.

Hence two students share a birthday.

Answer 4

Imagine to have one box for each day of the year, including February 29, which makes $366$ boxes.

Now, imagine that each student drops a copy of their ID in the box corresponding to their birthday. Some boxes might turn out to be empty, say they are in number of $E$. So the students dropped their ID in $366-E$ boxes. If each of the nonempty boxes contains exactly one ID, the number of students would be $366-E<500$.

Answer 5

Just count the worst case scenario. If you have 500 students, let's begin by trying to make sure all their days that they were born at are different, starting with placing Student 1 at January 1, then Student 2 at January 2 and so on...

Eventually we get to Student 365 and place him/her on December 31 (assuming no leap years, the argument is easily extended to include that, there are 365 days in a year). Now where can we place Student 366 so that the day he was born doesn't fall on anyone else's?

And looking back at our students, we still have 135 students left to place!

Answer 6

Take a slightly different question: What is the maximum number of students the school can have if no two pupils are born on the same day?

Since there are at most 366 days in a year, and on each day either none or one pupil was born, there can be at most 366 students.

Answer 7

There are 7 days in a week and you supposed to meet 8 people, so you have to meet at least 2 on same day. all these problems have same strukture , but in some problem can dirichlet principle give some surprising good results.