Question 1143356: A school has 731 students. Prove that there must be at least three students that have the same birthday assuming that no one has a birthday on Feb 29.
Can anybody please help us with this question?
We would be very grateful
Thank you💜
Found 2 solutions by greenestamps, ikleyn:
Answer by greenestamps(13200)   (Show Source):
You can put this solution on YOUR website! Look at the question this way: you are trying to find as many people as you can without any three of them having the same birthday.
Assuming nobody has a birthday on February 29, you have 365 days in the year that can be a person's birthday.
The worst case scenario is that you find exactly 2 people who have birthdays on each of the 365 days of the year. You still have no 3 people with the same birthday; and the number of people you have will be 2*365 = 730.
But then the 731st person has to have a birthday on one of those 365 days; that means you will have three people with the same birthday.
And of course it is unlikely that you will easily find 730 people without having 3 of them with the same birthday; that means with 731 people you would almost certainly have more than one date that is a birthday for 3 people; and you could easily have one birthday that is shared by MORE THAN 3 of the people.
Answer by ikleyn(52786)  (Show Source):
You can put this solution on YOUR website! .
There is so called "the pigeonhole principle" in Math:
If 7 pigeons are placed in 6 holes, then at least one hole contains 2 or more pigeons.
In this joking form it is obvious and does not require more detailed proofs / explanations.
Further, in more general form,
if (n+1) pigeons are placed in "n" holes, then there is at least one hole containing 2 or more pigeons.
In this form it is obvious, again, and does not require more detailed proofs / explanations.
Now let me formulate even more general THEOREM.
If there are n*m+1 items in "m" containers, then there is at least one container containing "n+1" or more items.
The proof is in three lines.
If there is NO such a container, then the total number of items in "m" containers is NOT MORE than n*m.
It CONTRADICTS to the given part (!)
This contradiction proves the statement.
Now let's return to our problem.
We have 731 = 2*365 + 1 students (= items), and
365 days in the year (that are "containers" in this case).
From the Theorem, there is at least one container containing (2+1) = 3 or more items.
In other words, there is at least one day (one date in an year), when 3 or more students celebrate their birthdays.
Solved.
-----------------
In MATHEMATICS (notice all letters are capital, which means that I am talking about TRUE Math)
this principle is called "the Dirichlet's principle", after the famous mathematician Johann Peter Gustav Lejeune Dirichlet
(1805 - 1859).
About Dirichlet, see these Internet articles
http://www-history.mcs.st-and.ac.uk/Biographies/Dirichlet.html
https://en.wikipedia.org/wiki/Peter_Gustav_Lejeune_Dirichlet
About "the Dirichlet's principle", see this Internet article
https://en.wikipedia.org/wiki/Pigeonhole_principle
|
|
|
