一个 $20$ 行若干列的 $0,1$ 数阵满足：各列互不相同且任意两列中同一行都取 $1$ 的行数不超过 $2$．求当列数最多时，数阵中 $1$ 的个数的最小值．
【难度】
【出处】
2008年全国高中数学联赛甘肃省预赛
【标注】
【答案】
$3820$
【解析】
对于满足条件的列数最大的一个数阵，如果这个数阵中某一列 $1$ 的个数超过 $3$ 个，那么就保留其中任意 $3$ 个 $1$，其余的都改变成 $0$，这样就得到一个列数相同并且仍然满足要求的一个新数阵．如果这个新数阵中还有 $1$ 的个数超过 $3$ 的列，则重复上述过程，最后可以得到一个列数最多，且每列中 $1$ 的个数最多为 $3$ 的满足要求的数阵，它的列数最多为$$1+\mathrm{C}_{20}^{1}+\mathrm{C}_{20}^{2}+\mathrm{C}_{20}^{3}.$$另一方面，构造一个满足要求的数阵如下：它包括没有 $1$ 的列以及所有互不相同的只有一个 $1$ 的列，$2$ 个 $1$ 的列和 $3$ 个 $1$ 的列．由前所述，可知这个数阵的列数是最多的，同时在满足要求的列数最多的所有数阵中，该数阵中的 $1$ 是最少的．此数阵的列数为$$1+\mathrm{C}_{20}^{1}+\mathrm{C}_{20}^{2}+\mathrm{C}_{20}^{3},$$此数阵中 $1$ 的个数为$$\mathrm{C}_{20}^{1}+2\mathrm{C}_{20}^{2}+3\mathrm{C}_{20}^{3}=3820.$$
答案
解析
备注
