Question

【题目】有一个由0和1构成的6行n列的 数字方阵，其中每行中恰有5个1，任意两行中同一列都取1的列数不超过2.求n的 最小值.

Answer 1

【答案】10

【解析】

首先，方阵中1的总个数有5×6=30个.

设第k列中1的个数为个.则.

对于任意的和，考虑这样的三元组：使得方阵第i行和第j行在第k列都是1.由于第k列这样的三 元组的个数为，故这样的三元组的总数为

其次，再用另外一种方法来计算上述那样的三元组的总数：对于任意的，记为方阵第i行和第j行中同一列都为1的列数，则有

.

于是，由条件有.

从而，

即.

对于n=10，图2是一个满足要求的方针：

1	1	1	1	1	0	0	0	0	0
1	1	0	0	0	1	1	1	0	0
1	0	1	0	0	1	0	0	1	1
0	1	0	1	0	0	1	0	1	1
0	0	1	0	1	0	1	1	0	1
0	0	0	1	1	1	0	1	1	0

n的最小值为10