难度：++
一个国家的法律规定，一个工厂的职工中只要有一人过生日，则那一天全工厂所有职工都放假。只要没有人过生日，则全体工人都必须上班。没有周日或其它假日。而且规定招工时不能有生日歧视，也就是说工人的生日是均匀分布。我们的问题是，在这种前题下，一个工厂要招多少工人才能使工厂的总年工作量的期望值最大（一个人工作一天算一个工作人日）。
364 or 365? |
本贴由[huxlnn]最后编辑于：2006-2-17 1:19:8 |
(365-x)x365=365x356÷2 x=182.5 |
假设招工人数是 n, n 个工人的生日数为 m 的概率是 P(n,m)，则总工作量的期望值 y(n)： y(n) = Σm[n(365-m)P(n,m)], sum m from 1 to n, n≤365; y(n) = Σm[n(365-m)P(n,m)], sum m from 1 to 365, n>365. 以及 P(n,m) 的递推关系： P(1,1) = 1; P(n,1) = P(n-1,1)/365; P(n,n) = P(n-1,n-1)*(1-(n-1)/365); P(n,m) = P(n-1,m-1)*(1-(n-1)/365) + P(n-1,m)*(1-m/365), m=2,...,n-1; 根据 P(n,m) 的递推关系，我们可以证明： 1）y(n) 是递增函数, n<364; 2) y(n) 是递减函数，n>365; 3) y(364)=y(365). 也就是说，当招工人数达到 364 或 365 的时候，总工作量的期望值最大。这应该是做计划时的数学估计，实际运作时，老板可以只招与已有工人共有生日的新工。（这一招在中国可行，在美国行不通。） 前面 (1),(2) 的证明尽管不难，但稍显繁复，不只是否有更直觉的证明？ 本贴由[流动的建筑]最后编辑于：2006-2-15 18:3:54 |
设该工厂有N个工人，这些工人有n个不同的生日。
再增加一个工人时，新工人生日与原来的工人重合的概率是n/365，不重合是（1 - n/365）。工作日变化的期望值为
n / 365 * ( 365 - n ) + ( 1 - n / 365 ) * ( 365 - n - 1 - N) = (365-n)*(364-N) / 365
这个期望值的符号只与N有关，而与n无关。N = 364时期望值为0，超过364时变为负数。N = 364时年工作量的期望值最大。 |
N=364 时工作日变化的期望值为 0，也就是说，N 从364变到365时工作日的期望值不变，N=365 应该也是一解。 |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |