趣题：和有可能为1的区间分布

如果 10 个非负数 x1, x2, …, x10 满足 x1 + x2 + x3 + … + x10 = 1 ，那么这 10 个数都均匀地分布在 [0,1] 之间吗？显然不是。为了说明这一点，最好的方法或许是把分布情况变得有限——我们可以把 [0,1] 区间划分成若干个小区间，并说明这 10 个数不可能均匀地分布在这些区间内。比方说，把 [0,1] 分成 [0, 0.25), [0.25, 0.5), [0.5, 0.75), [0.75, 1] 这四段：如果 10 个数都落在 [0, 0.25) 里，它们的和是有可能为 1 的；但若 10 个数都落在 [0.75, 1] 里，显然它们的和不可能为 1 。一个有趣的问题由此产生：考虑 10 个数的 4^10 种分布，它们的和有可能为 1 的有多少情况？

显然， 10 个区间的右端点之和一定比 1 大。因此，只要 10 个区间的左端点之和不超过 1 ，就可以保证在这些区间中选的数之和可能为 1 。不妨把区间 [0, 0.25), [0.25, 0.5), [0.5, 0.75), [0.75, 1] 依次编号为 0, 1, 2, 3 ，由于它们的左端点分别为 0/4, 1/4, 2/4, 3/4 ，因此左端点之和不超过 1 相当于 10 个区间的编号之和不超过 4 。而和不超过 4 的 10 个非负整数，又与 4 个小球和 10 个隔板的排列顺序一一对应，它们一共有 C(14, 4) = 1001 种情况。但在这 1001 种情况中， (4, 0 ,0, …, 0), (0, 4, 0, …, 0), ……, (0, 0, 0, …, 4) 这 10 种情况是要排除的，因为区间编号只有 0 到 3 。因此，在 10 个数的 4^10 种区间分布中，只有 991 种分布才满足它们的和可能为 1 。

接下来，我们自然而然地想到了这样一个问题：如果把 [0, 1] 划分成不同的四段，问题的答案还是 991 吗？好像并不是这样。容易想到，由于偏小的数更容易出现，因此若划分出来的区间在前面更密集一些，就会出现不止 991 种满足要求的分布。那么，同样是把 [0, 1] 分成四段，满足要求的分布最多能有多少个呢？

我们先来说明，答案最多不会多于 4^10 – 3^10 ，因为无论怎样划分区间，至少有 3^10 种分布是不满足要求的。只需要注意到，如果某种分布符合要求，则所有区间的左端点之和一定比 1 小；那么把所有 10 个区间都左移一下，原分布中的左端点之和就变成了新分布的右端点之和，由于它比 1 小，因此新的分布一定不符合要求。现在，假如 10 个数都只能落在编号为 1, 2, 3 的区间里，那么总的分布情况数就有 3^10 种。对于这里面的每一种分布，要么它自身是不合要求的，要么所有区间左移一下后得到的新分布是不合要求的。因此，至少有 3^10 种分布不符合要求，也即最多有 4^10 – 3^10 种可行的分布。

这个上界是可以达到的。例如，四个区间分别为 [0, 0.01), [0.01, 0.02), [0.02, 0.03), [0.03, 1]，则满足要求的分布恰有 4^10 – 3^10 = 989527 种。

题目来源：上月 IBM Ponder This(http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/May2010.html)