Author Topic: 每周一题: 生日休假的最大工作量 (10/4/04 -- 10/10/04)  (Read 11089 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
上周我们这个论坛有两个突破。一个是注册人数超过了五十。第二是我们的贴子居然
要用到第二页。而在此之前所有的贴子都可以在一页里面表示出来。按我初步统计,
每天看这个论坛的人大约是150个人左右。这种论坛的起飞点(critical mass)大
概是每天500人次。考虑到这个论坛的内容,要达到这个500,大概不是很容
易的事。慢慢来吧。

上周题目讨论:

第一道题是很老的题,所以有人说小学时候就做过。关键是不要去把每次的距离算
出来。而直接看要多少时间两人相遇,而这么长时间里鸟能飞多远。据说有人把这
个题出给冯·诺曼,他考虑了一下很快就给出了答案。出题的人说,还是你厉害,
很多人找不到关键,而是去算每次鸟掉头时飞的距离然求级数和。冯·诺曼说,什
么关键,我就是用的算级数和的办法。

第二道题初看起来很复杂。实际上,每次两只蚂蚁相遇时,虽然每只蚂蚁都掉头,
但从两只蚂蚁整体来看与两只蚂蚁继续往前走一样,只不过两只蚂蚁互换了一下而
已。所以,总时间不会超过一只蚂蚁走完全程的时间。

第三道题看起来与天文有关,实际上是纯数学问题。关键是地球除了自转以外还要
绕太阳公转。我们平常所说的每天24小时是地球上一点两次面对太阳的时间。这
个时间要比自转一周多一点点,365个这一点点就多出来一圈。所以,每天相差
的这3分五十六秒差不多等於1/365天。

有人说上次的题太容易,这次就来一个相对难一点的。应该算是一个概率题,但比
两周以前的概率题难一点。

本周题目:

一个国家的法律规定,任何工厂的职工中只要有一人过生日,则那一天全工厂所有
职工都放假。只要没有人过生日,则全体工人都必须上班。没有周日或其它假日。
而且规定招工时不能有生日歧视,也就是说工人的生日是均匀分布。我们的问题是,
在这种前题下,一个工厂要招多少工人才能使他的年工作量最大(一个人工作一天
算一个工作人日)。如果招的人太多,几乎每天都有人过生日,每天都放假,则工
作人日为零。如果招一个人,则这个工厂每年有364个工作人日。如果招两个人,
则差不多有2乘363等於726个工作人日。显然最优点是一个大於一的有限数,
这个数是多少?当然我们是从概率的角度来考虑这个问题。如果所有的人都在同一
天过生日,当然人越多越好。

supertramp

  • Newbie
  • *
  • Posts: 18
每周一题: 生日休假的最大工作量 (10/4/04 -- 10/10/04)
« Reply #1 on: 十月 04, 2004, 06:36:30 am »
Suppose the factor has N workers, with n different birthdays.

Add one more worker:
with probability n/365, this new work will have one of the existing n birthdays;
with probability ( 1 - n/365 ), this new work with a new birthday, so the total number of birthdays becomes n+1.

In case one, the new worker-day = ( N + 1 ) * ( 365 - n ).
In case two, the new worker-day = ( N + 1 ) * ( 365 - n - 1 ).

New expected worker-day =  n / 365 * ( N + 1 ) * ( 365 - n )
 + ( 1 - n / 365 ) * ( N + 1 )  * ( 365 - n  - 1 )

Old worker-day = N ( 365 - n ).

Expected increase in worker day = ( 365 - n )  * 364 / 365 - N ( 365  - n ) / 365.

The optimum occurs when expected increase is zero.

This requires N = 364.

sean

  • Jr. Member
  • **
  • Posts: 86
每周一题: 生日休假的最大工作量 (10/4/04 -- 10/10/04)
« Reply #2 on: 十月 04, 2004, 10:16:13 am »
My  answer might be wrong, 'cause it conflicts with Prof. 10k's and super's.   :wink:  I guess I am just not good at probability.  Anyway, since I gave it some thought, I will post my answer here. I wish someone can clean the bugs in my knowledge of probability.

My answer is: the more workers, the better.

Suppose there are N workers.  For any day, the probability that it is not a birthday of anyone is 364/(364+N) : this comes from computing some elementary probability, which I guess is correct.

Thus for any day, the expected workload is N*364/(364+N) person.day's. Thus  for the whole year,  the expected workload is

      365*364*N/(364+N).

Thus, the more the better.

When N=1 or 2, the expected workload is equal to or close to what Prof 10k says.

The answer is kind of *funny*. If it is correct, here is an explanation: when N becomes larger, it is harder for one day not to be a birthday; however, if the boss gets one lucky day, he gets a big N person.day's.

idiot94

  • Sr. Member
  • ****
  • Posts: 484
每周一题: 生日休假的最大工作量 (10/4/04 -- 10/10/04)
« Reply #3 on: 十月 04, 2004, 01:06:44 pm »
Sean, your idea is right, but your calculation is not right.

The very first step, while
Quote
Suppose there are N workers. For any day, the probability that it is not a birthday of anyone is 364/(364+N) : this comes from computing some elementary probability, which I guess is correct.
...
is wrong.

For any given day, suppose the probability of this day being the birthday of worker1 is p (of course, p=1/365). For worker1, this day not being his birthday would have prob. 1-p. With N independent workers, this day not being any1's bday has prob. (1-p)^N.

The expected workmanday of this day is thus N*(1-p)^N. This is the same for all 365 days. Thus you need just to max N*(1-p)^N w.r.t. N, given p=1/365.
The result is 364 or 365, which is the same as Mr. S.'s answer (of course).
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

sean

  • Jr. Member
  • **
  • Posts: 86
每周一题: 生日休假的最大工作量 (10/4/04 -- 10/10/04)
« Reply #4 on: 十月 04, 2004, 02:36:34 pm »
Quote from: idiot94
Sean, your idea is right, but your calculation is not right.

The very first step is wrong.

 


Yeah, I was wrong. I made a stupid mistake. Thanks a lot.  Your explanation is very clean and convencing.  

Prof Wan, maybe you (and whoever give the problems) can mark the problems that are solved as "solved"  (or beautifully solved).  I checked the old problems posted here since June, and think that some of them are still not cleanly solved, though there are some useful discussions and the correct solutions can be obtained based on them (the guy who provided the useful ideas should be able to write a clean solution).  For example,  for the rectangle problem posted last week,  from those discussions, we know that when k satisfies some condition, there is a solution; and when k satisfies some other condition, L shapes do not work.  I think the person who showed that could easily tell whether there are other working shapes or not.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
每周一题: 生日休假的最大工作量 (10/4/04 -- 10/10/04)
« Reply #5 on: 十月 04, 2004, 03:04:49 pm »
I think a general principle should be whoever post the problem should make a statement after 1 or 2 weeks. Either post the answer (in case nobody solves it) or make a statement about the answer that other people has (confirm it or disagree).

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
Re: 每周一题: 生日休假的最大工作量 (10/4/04 -- 10/10/04)
« Reply #6 on: 九月 13, 2013, 12:11:47 pm »
这几天在微博上又见到这道题。想了一下,可以有更简洁的解答

假设n个人的期望工作日是w(n),那么w(n+1)=w(n)*364/365 (因为每一天有1/365的可能性变为休息日)。
从n人到n+1人,总工作时间增量为 w(n+1)*(n+1)-w(n)*n = w(n)*(364-n)/365。显然,n < 364时,
增量为正,n>364时,增量为负。所以,364为最佳解。

另外,这个题目适用于任意天数的年。假设一年有K天,那么,K-1就是最佳解。