Birthday laws probability puzzle

Wouldn’t it be fun if you could get a holiday every year on your birthday?

Wouldn’t it be even better if your friends got the same holiday too?

Such a labor law would make for some fun parties. But it might have some interesting macro effects on the economy as a whole.

Here’s a probability puzzle that asks about this question explicitly.

In mathland, companies have to give a holiday to everyone whenever one employee has a birthday. Other than those holidays, employees work every day.

If a company wants to maximize the expected total number of man-hours worked per year, how many employees should it hire? Assume companies cannot discriminate in hiring based on someone’s birthday.

(problem reworded from this book)

As usual, I will be posting an answer on Friday in the comments section.

If you solve the problem, leave a comment about how long it took you.



Share this post:

| More

Previous post:

Next post:



  • tony

    Assuming for the sake of the argument that each employee works one hour a day. Also assuming that each birthday is equally likely to occur.

    365 workers = expected man hours of zero.
    364 workers = 364
    1 worker = 364
    0 workers = 0

    Didn’t do anything complex, but it would seem as if man hours equals number of workers times number of days in the year minus the number of workers. Best way to maximize profits would be to hire 182 or 183 workers for a total expected hours of:

    183 workers x 182 expected working days = 33306 hours
    182 workers x 183 expected working days = 33306 hours

  • tony

    Took me about a bit over a minute.

  • Rafael

    number of employees -> days of work in the worst case -> total number of days (working days)

    1 -> 364 -> 364 * 1
    2 -> 363 -> 363 * 2
    3 -> 362 -> 362 * 3
    .
    .
    181 -> 184 -> 184 * 181
    182 -> 183 -> 183 * 182
    183 -> 182 -> 182 * 183
    184 -> 181 -> 181 * 184
    .
    .
    .
    364 -> 1 -> 1 * 364

    The number of employees could be 182 or 183 (half the number of days in a year). Both numbers would produce the same result. Although 182 would make the company spend less money ;) !

    I took me about 3 minutes. I don´t know if its right though ;) . But I guess it is.

  • aaa

    1

  • Lisa Clarkson

    183 people. I just made a spreadsheet with expected work days * number of employees and 182/183 is where it peaked.

    There is probably a deeper dive to be had because the 1st employee automatically adds a holiday on 1 out of 365 days. But with the 2nd employee, there is a 1 in 365 chance that a holiday WON’T be added (because they might have the same birthday). I’ll noodle around with that.

  • Graham

    Long time reader and first post but I think a lot of you are overlooking the ‘Birthday Problem’. Im not sure how to do this problem but for people who think that 365 workers means that there will be 0 work,
    http://en.wikipedia.org/wiki/Birthday_problem

  • Tristan

    I’m going to go with around 380 employees. From which I expect to obtain around 50,000 man-days of work.

    You really need to factor in the probability of people having the same birthday in your calculations. It makes this problem, at least tangentially, related to the birthday problem. (Although this one is a little more complex)

    I’ve spent around 4 hours on this so far, and I suspect I’ll spend some more looking for a closed mathematical form to summarize the result.
    Thanks for the neat problem.

  • Dan

    My guess is a tie at 364-365 employees and ~84500 hours. Did some simulations and arrived at 350-370 employees as the optimum. I then did the problem for very small number of days and found an interesting trend.

    First, 2 days:
    For 1 employee – 1 working day
    For 2 employees – 50% of zero working days (different d-days) and 50% of 2 working days (same b-day). The average is 1 working day. So the optimum is either 1 or 2.

    Next, 3 days

    For 1 employee – 2 working days
    For 2 employees – 2.667 days (2 people * 1.33 working days)
    For 3 employees – 2.667 days (3 people * 8/9 working days)

    In both cases, the optimum is either n or n-1 with n being the total number of days in the year. I did this for 4 days and 10 days and got the same trend. I’m extrapolating to 365 days. The simulations came up with ~232 working days which I used to estimate the total working days. I expect that I am within 5-10 days of the correct answer.

    Also interesting is that a “normal 9-5 job” has roughly this many working days.

    52 weeks * 5 days = 260
    10 holidays, 3 weeks vacation ~ 25 days
    A “normal” job has ~235 working days.

  • Travis

    Took less than 5 minutes to do via calculus. The answer was rather surprising.

    Disclaimer: I went with 365 days per year, ignoring leap years.

    Process:
    1) number of days worked by n employees [D(n)] = D(n-1) – (D(n-1)/365) since the probability of losing a day by hiring a new employee is equal to the number of days worked by the current number divided by the number of days in a year. D(0) = 365, for obvious reasons.

    2) I will skip the intervening steps, but this formula reduces to D(n) = 365*(364/365)^n

    3) Total man-days worked per years by n employees is n*D(n). The max will be where the derivative = 0.

    4) Derivative (skipping math) reduces to [365*(364/365)^n]*[n*ln(364/365) + 1]

    6) To get the derivative = 0 requires one of the terms to reach zero. There are three ways of doing this:
    a) (364/365)^n = 0 at n = infinity, which makes sense because with infinite employees every day will be a birthday and noone will ever work.
    b) n = 0, which again leads to no work being done
    c) n*ln(364/365) = -1. This must be the one we want.

    7) Solving for n*ln(364/365) = -1, we get 364.5. So either 364 or 365 must be the answer, but let’s check the work to be sure.

    n*D(n) for:
    n=363 -> 48943.154 man-days/year
    n=364 -> 48943.5238 man-days/year
    n=365 -> 48943.5238 man-days/year
    n=366 -> 48943.156 man-days/year

    This verifies that 364 and 365 are a local maximum, and it is safe to conclude that this is the actual maximum. For the record 365 comes slightly higher when you go out over 30 decimal places, but since that is less than one picosecond per year it doesn’t really matter.

  • http://www.vpsgraphics.com V Paul Smith Jr

    I also got 364 and 365, but in a slightly different way.
    A bit of empirical tinkering got me to this:
    (D)ays, (W)orkers

    [(D-1)^W] / [D^(W-1)]) W

    http://tinyurl.com/3tt5d69

    After trying a few smaller cases one quickly finds that the maximum is when W = D-1 and D

    It took about an hour.

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    Thanks all for the comments. Dan, Travis and V Paul Smith Jr came upon the right answer and came up with the correct methods.

    If you want to see it for yourself, you can play around with this Excel spreadsheet which explains in detail how to arrive at the solution.

    http://www.washjeff.edu/users/mwoltermann/Mosteller/34.xls

  • Chris Shannon

    I came up with the same answer using a different technique, if you are interested.

    Suppose there are already n employees at the company and they have amongst them m unique birthdays ( 0 < m<=n, m<=365 and are both positive integers). They therefore work 365-m days per year. They hold a meeting to decide if they should hire another employee.
    Employee A says, "yes we should, since there is an m/365 chance that he'll share a birthday with us, and we'll therefore get 365-m extra man-days of work for our company every year."
    Employee B says, "But there is a 1-m/365 chance that he'll have a different birthday than all of us, and he and all n of us will need to take an extra day off."
    The boss says, "You're both right, so let's calculate the expected gain in man-days per year by hiring this new employee…
    (m/365)*(365-m) + (1-m/365)*(365-m -1-n)
    If this is greater than 0, than we should hire him."
    "One sec" says Math Intern C, "this simplifies to 364-m-n+m/365+mn/365, we can see that regardless of m this is positive if n is less than 364, and equal to 0 if n = 364, and negative if n is greater than 364. So we can continue to hire employees until we reach 364, at which point hiring 1 more will not change our expected man-days per year at all, but hiring any more than that will decrease it."

    … This took a bit longer than I'd like to admit since I went down a long track trying to find a closed form expression for m.

  • Tim

    The size of the company can be anything you want, How about 26,300 people? (about the size of Google)

    You just need to hire people whose birthdays all fall on the same day.

    If this seems too trite, or lacking in math, then think about the probability for people to share birthdays, and work out the best number of duplicate birthdays to have.

    I am also betting that most of the above “solutions” ignore things like weekends!! People tend not to work on weekends, so you can easily hire those people, for a year, whose birthdays will fall on a weekend.

    Alternatively, just hire people, for just under a year on the day after their birthday.

  • Suresh Manchi

    worst case scenario:
    If there birthday on each day of the year then no working days.
    Man-days per year = n*(365-n) where 1<=n<=365
    n*(365-n) is maximum when n is 365/2

    Number of employees should be 182 or 183.

  • http://brevity.org/ Neil Kandalgaonkar

    Came up with the answer of 364 workers, using this perl script. I tried to figure the cases of workers = 0, 1, 2, 3 and saw a recursive pattern. So it was a simple matter after that. Took about 10-15 minutes.

    http://brevity.org/misc/workers_pl.txt

  • http://phunehehe.isgreat.org phunehehe

    I cheated by writing a script that will calculate the results. It’s in Python below. The idea is, I expect the results to go up and then down, so the script runs until it find the point where the results start to go down. I also take into account the possibility of birthdays being overlap. The final result is nice: 365 employees would be the best, resulting in around 48943 work days. I was halfway with a more math-like solution, but it seems I’m not so much of a mathematician.

    http://pastebin.com/KcKap7yL

    (Somehow the code in my previous post was scrambled up so I posted again on pastebin. Please remove the other one.)

  • Zhehao Mao

    Took me about five minutes. Let’s calculate in man-days instead of man-hours since that is easier. If x is the number of workers, the number of man-days worked in a non-leap-year is

    x*(365-x)
    = 365x – x^2

    If we differentiate and set to 0.

    0 = 365 – 2x
    x = 365/2 = 182.5

    So 182 or 183 workers is the optimal amount.

  • Non Sequitur Boy

    I made a further assumption that a company stops hiring when the hours worked would decrease.

    Using a short recursive function based on i.i.d. birthdays, I ran 10,000 simulations, and every simulation had a range of 196-219 employees, with 207 being the median. Add one to these if the last employee interviewed was actually hired.

    I suspect the people who got 182 didn’t consider that some employees might share birthdays by chance.

    It took me longer to write this post than it did to write the simulation code :p

  • Pingback: Matrix67: My Blog » Blog Archive » 趣题：公司应该雇用多少员工？

  • Chris Lomont

    With n people, you expect sn=365(1-(364/365)^n) distinct birthdays. Then you get n*(365-sn) as the number of man-days worked, which has a global maximum (tied) at n=364 and n = 365 with value 48943.523805351118109 man days.

    For the proof of the expected number of distinct birthdays, let pk = probability at least one person has a birthday on day k, then the expected value for the total X is E(X)=sum {k=0 to 365} pk = 365*p1 = 365(1-(364/365)^n).

    So, answer is n=364 or n=365 for a tie, with a little more than 48943.5 man days of work expected.

  • http://sandeepkatada.blogspot.com/ Sandeep Katada

    assuming year has 7 days

    (Kgs of work) — (no.of ppl) —- (Probable holidays)

    6kgs – 1 — 6
    10/12 – 2 — 5/6
    12/15/18 – 3 — 4/5/6
    12/16/20/24 – 4 — 3/4/5/6
    10/15/20/25/30 – 5 — 2/3/4/5/6
    6/12/18/24/30/36 – 6 — 1/2/3/4/5/6
    0/7/14/21/28/35/42 – 7 — 0/1/2/3/4/5/6

    Clearly “4″ is the winner

    => upper of round of no.of ppl by 2 is answer ( [7/2] = 4 )

  • http://manasgajare.com Manas

    @Travis and @V Paul Smith

    Could you please explain your methods in details?

  • http://vpsgraphics.com V Paul Smith Jr

    @Manas, hopefully this is clear enough. Ask if you have questions:

    Seeing as I don’t have the skills necessary to tackle the problem using calculus, and using formulas involving logs, which I see other have, I had to go about it a bit more brute force, at first, and then generalize and find a formula that matched what I found.

    I started off with a much more manageable cases involving 3 days, 3 workers {3,3} and also the cases of {4,3} and {5,3}
    I manually listed all the different arrangements that 3 workers birthdays could fall on 3 days. There were 9 different combinations. (Note: I only dealt with a third of the cases as the other two thirds would be symmetric)
    Over those 9 days, there were 8 days available to work.
    I also manually listed out {4,3} and {5,3} yielding these results:

    {d/w} = average number of work-days
    {3,3} = 8 / 9
    {4,3} = 27 / 16
    {5,3} = 64 / 25

    Just a glance at the numbers reveals the pattern, and therefore the formula:
    ((d-1)^w) / (d^(w-1))

    That is the average number of work days for the given d and w.
    Multiply that by the number of workers and you have the amount of man-days of work in our given “year.”

    With that formula, I then listed out {20,1}, {20,2}, {20,3}…{20,19}, {20,20}, {20,21}…
    and saw that it peaked, with matching numbers at 19 and 20.
    I did the same thing for many other numbers, and saw that it always co-peaked at d and d-1

    And that’s how I did it.

    Not elegant, but I didn’t have the means to do so.





Previous post:

Next post:

Other posts you may enjoy reading:

This site is for recreational and educational purposes only (privacy policy)

Powered by WordPress