53 Combinatoric Selections

Problem 53

组合公式 $$\begin{pmatrix} n\\r \end{pmatrix}=\frac{n!}{r!(n-r)!}$$ 当 $n=23$ 时，有 $$\begin{pmatrix} 23\\10 \end{pmatrix}=1144066$$ 超过了一百万，求有多少 $$\begin{pmatrix} n\\r \end{pmatrix},1\leq n\leq 100$$ 的值超过一百万。

当 $n=23,r=10$ 时，组合数就大于 100 万了。由此可知，$r$ 为 $10,11,12,13$ 时，都是大于 100 万的。所以满足题目的数的个数是 $23+1-10\times2=4$ 个。

同时，$n=24,r=10$ 时，肯定也大于 100 万。

那么 $n=24,r=9$ 的时候呢？拿科学计算器摁了一下，也大于 100 万。可以得到一个结论，当 $r=9$ 时，$n=24$ 是满足题意的最小的数字。当 $n=24$ 时，满足题意的数字有 $24+1-9\times2=7$ 个。

解释下上面出现的式子的原理。$r$ 有 $n+1$ 种取法，所以是 $23+1$ 和 $24+1$，$r=9$ 满足 100 万，那么 $r$ 从 0 到 8 这九个数不满足，减去一个 9，对称的，后面也有 9 个不满足题意。

接下来，寻找那个最小的 $n$，当 $r=8$ 时，就能满足题意。简单的计算了一下，结果是 $n=25$。以此类推，得到一个临界值组成的表：

$n$	$r$
23	10
24	9
25	8
28	7
33	6
44	5
72	4

这里说一下，不用每个数字都计算，利用类似于二分法的思想，只用计算很少的次数，就能得到这个表了。

这个时候利用 Excel 计算答案。首先填充 23 和 24，利用自动填充功能，把第一列填充为 23-100。

把临界值表里面的数字填到第二列，利用自动填充功能，把第二列也都填好。比如 25 到 27 都填充上 8，28 到 32 都填充 7，72 以后都填充成 4。

第三列写上公式 =A1+1-2*B1，第三列也可以自动都计算好。

在第三列最后，利用求和公式，得到答案。