dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

Thread: Birthday is no problem

  1. #1
    Join Date
    Feb 2017
    Posts
    406

    Birthday is no problem

    (a) Give a formula for the probability P (n) that of n randomly selected persons, at least two have their birthday on the same day. Also indicate the derivation of your solution or justify its correctness. You can assume that each year has 365 days (none of them have their birthday on February 29th) and that birthdays are evenly distributed (there are no special events that lead to higher birth rates on certain days).
    (b) Determine the values ​​P (10), P (23), P (35) and P (50) to a minimum of 3 decimal places.
    (c) What did you calculate in this task related to hashing?

    ----------

    The above question was recently posted at this forum in a thread that got locked. It's obviously homework but may still be of general interest in an algorithms & data structures forum. It must be clear to the problem constructors that this problem both is quite hard and also a well-known standard problem known as the Birthday problem which even has a Wikipedia entry. It's naive to think that data structure students would bother with a difficult probability problem when it's so much easier to just Google the solution and get over with it.

    On the other hand, if the Birthday problem is attacked from a hashing viewpoint it becomes much simpler, even easy. The hashing point of view offers an effective solution strategy. Instead of solving the Birthday problem first and then figure out what it has to do with hashing it would be more meaningful if the exercise were posed the other way around like this:

    Use your knowledge of hashing and the hints below to solve the Birthday problem and code it in your language of choice. You get points for ingenuity of solution, cleverness of conclusions and elegance of code:

    1. Imagine a row of 365 empty chairs.

    2. Repeatedly select a chair with probability 1/365 and place a person in it.

    3. There exists a function based on date-of-birth that maps any person onto a number between 1 and 365.

    4. Someone who gets assigned a free chair is considered lucky.

    5. At first all chairs are free so the first person will be lucky with probability 1. As the chairs fill up the probability of luck gets smaller to finally become 0 when all chairs are occupied.

    6. The probability that exactly the k'th person is lucky depends solely on the number of remaining free chairs in relation to the total number of chairs.

    7. The combined probability that all of k persons are lucky is the product of the luck probability of each of the k persons.

    8. The probability that at least one of k persons is unlucky is the complement to the probability that all k persons are lucky.
    Last edited by wolle; December 19th, 2018 at 09:31 AM.

  2. #2
    Join Date
    Dec 2018
    Posts
    12

    Re: Birthday is no problem

    Never heard about such problem. But as it turned out, this paradox is indeed described in Wikipedia. The topic is quite interesting and not simple. I think about it all evening ....

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)