生日休假的最大工作量

constant · 发表于 2006-2-14 21:37:56

难度：++

www.ddhw.com

一个国家的法律规定，一个工厂的职工中只要有一人过生日，则那一天全工厂所有职工都放假。只要没有人过生日，则全体工人都必须上班。没有周日或其它假日。而且规定招工时不能有生日歧视，也就是说工人的生日是均匀分布。我们的问题是，在这种前题下，一个工厂要招多少工人才能使工厂的总年工作量的期望值最大（一个人工作一天算一个工作人日）。

流动的建筑 · 发表于 2006-2-15 02:25:46

364 or 365?

huxlnn · 发表于 2006-2-15 05:57:27

本贴由[huxlnn]最后编辑于：2006-2-17 1:19:8

朗朗晴空 · 发表于 2006-2-15 17:52:18

(365-x)x365=365x356÷2

x=182.5

constant · 发表于 2006-2-15 18:27:08

对。能给个证明吗？

流动的建筑 · 发表于 2006-2-15 22:08:21

假设招工人数是 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

constant · 发表于 2006-2-16 06:24:47

设该工厂有N个工人，这些工人有n个不同的生日。

www.ddhw.com

再增加一个工人时，新工人生日与原来的工人重合的概率是n/365，不重合是（1 - n/365）。工作日变化的期望值为

www.ddhw.com

n / 365 * ( 365 - n ) + ( 1 - n / 365 ) * ( 365 - n - 1 - N) = (365-n)*(364-N) / 365www.ddhw.com

www.ddhw.com

这个期望值的符号只与N有关，而与n无关。N = 364时期望值为0，超过364时变为负数。N = 364时年工作量的期望值最大。

流动的建筑 · 发表于 2006-2-16 11:54:13

N=364 时工作日变化的期望值为 0，也就是说，N 从364变到365时工作日的期望值不变，N=365 应该也是一解。

		自动登录	找回密码
密码			立即注册

动态微博

生日休假的最大工作量

回复：生日休假的最大工作量

若以一年365天计算?

回复：生日休假的最大工作量

对。能给个证明吗？

回复：对。能给个证明吗？

解答

回复：解答