I am vaguely aware of the Pigeonhole principle and I understand that you would need 367 people to ensure that two people have the same birthday. I think that it may be required to have 734 people in a room to ensure 100% probability, since you can have 366 birthdays repeated and not have three people. Is this a correct assumption, and if so, how would you solve it without just guessing/checking?

  • 6
    $\begingroup$ You mean 733. $ $ $\endgroup$ – Did Apr 12 '15 at 16:08
  • 8
    $\begingroup$ I think the use of "probability" in your question is misleading. There are situations in which "occurs with 100% probability" is weaker than "must occur", but this is not one of them. This is indeed a direct application of the Pigeonhole Principle. It sounds like you should become more than vaguely aware of the Pigeonhole Principle: certainly it is simple enough for anyone to understand, and once you get it you'll regard questions like this as being 100% (!) straightforward. $\endgroup$ – Pete L. Clark Apr 12 '15 at 17:16
  • $\begingroup$ Any space large enough to contain that many people would probably not be considered to be a "room"; the word "hall" would seem more appropriate. $\endgroup$ – Marc van Leeuwen Apr 13 '15 at 10:35

Your reasoning looks pretty much right (you're off by one) and looks to me like a direct approach more than guessing and checking. Maybe if we just crystalize your argument a little, you'll understand it more deeply:

There are $366$ possible birthdays; if we have $366\times 2=732$ people, then it is possible for each day, exactly two people call it their birthday. This is the maximum number of people where we can have at most $2$ per birthday. If we have one more person, then at least three people must share a birthday. Thus, in a room of $733$ people, at least three share a birthday.

| cite | improve this answer | |
  • $\begingroup$ Oh okay! Your explanation cleared up my confusion. I was thinking it may have been +2 for some reason, instead of just +1. $\endgroup$ – Ampage Green Apr 12 '15 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.