1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Counting problem relatively hard I think.

  1. May 17, 2012 #1
    1. The problem statement, all variables and given/known data

    For this problem assume that the 365 dates of the year are equally likely as birthdays.

    b)Find the probability that in a group of n people, at least two have the same birthday.

    2. Relevant equations

    3. The attempt at a solution

    Well Im not really sure what method I should use here??

    but... the total number of solutions is surely 365n

    but at least two?

    maybe something along the lines...


    the probability is P(365,2)/365n

    But I have a feeling I'm missing something, but I don't understand what?
  2. jcsd
  3. May 17, 2012 #2
    A way to approach this problem is to notice the probability of at least a pair having the same birthday is the same as one minus the probability of no one having the same birthday.
  4. May 17, 2012 #3


    User Avatar
    Science Advisor

    To determine the probability that "at least two" things occur, look at the opposite event- that NO two people have the same birthday. The probability that "at least two people have the same birthday" is then 1 minus the probability that no two people have the same birthday.

    And that calculation easy- imagine putting all n of the people in order- in a straight line. The first person can have any day of the year as a birthday. The probability of that is 365/365= 1, of course. The second person can have any day except that one day as birthday. The probability of that is 364/365. The third person can have any day except those two days. The probability of that is 363/365. Can you finish that?
  5. May 17, 2012 #4


    User Avatar
    Homework Helper

    HallsofIvy's post is good, and works for [itex]n \leq 365[/itex] but what happens when [itex]n \geq 366[/itex]? Hint: Pigeonhole principle.

    So the answer is a formula dependent on n for the former case, and just a single answer for the latter case.
  6. May 17, 2012 #5
    365 choose 366 is zero, so the answer will work for n >365. Also, I wouldn't call it the pigeonhole principle. I'd call it the common sense principle.
  7. May 17, 2012 #6


    User Avatar
    Homework Helper

    HallsofIvy's post did not introduce the combination operation. His post would directly have led to:

    [tex]p(n) = 1 - \frac{(365)(364)...(365-n+1)}{365^n}[/tex]

    which clearly holds for [itex]n \leq 365[/itex]. It also holds for [itex]n=366[/itex], because one can say the 366th person has zero "choice" of birthday to avoid a collision. However, when [itex]n > 366[/itex], the last terms of [itex](365-n+1)[/itex] stop making sense, because, for example, the 367th person does not have "-1" choices of birthday, etc., he simply has no (zero) choice. Even though the expression will evaluate to the correct answer (one) for [itex]n > 366[/itex] because exactly one of the terms in the product is zero, the expression is still not correct mathematically.

    The next commonly taken step, which involves simplifying the expression and recasting it in terms of combinatorial notation, is what you're referring to. Of course, based on the definition [itex]nCr = 0[/itex] for [itex]r > n[/itex], this expression would hold for all n, but the fact remains that this is not a mathematically sound way of deriving that formula since the initial expression does not make sense for [itex]n > 366[/itex], as I explained.

    Hence the usual way of working the problem, which is to break the problem up into two cases, [itex]n \leq 365[/itex] and [itex]n \geq 366[/itex]. Mathematical rigour matters.

    You can call it whatever you like, and it is common sense, but it IS called the pigeonhole principle.
    Last edited: May 17, 2012
  8. May 18, 2012 #7
    Thanks for all the replies cleared things up a lot I was really struggling to see where the 1 came from.
  9. May 18, 2012 #8


    User Avatar
    Science Advisor

    There are 365 days of the year (pigeon holes) and more than 365 people (pigeons) so the "pigeon hole principle" say that at least two people must have the same birthday. There are many "common sense principles", only one "pigeon hole principle".
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook