Question

【題目】有一個(gè)由0和1構(gòu)成的6行n列的 數(shù)字方陣，其中每行中恰有5個(gè)1，任意兩行中同一列都取1的列數(shù)不超過(guò)2.求n的 最小值.

Answer 1

【答案】10

【解析】

首先，方陣中1的總個(gè)數(shù)有5×6=30個(gè).

設(shè)第k列中1的個(gè)數(shù)為個(gè).則.

對(duì)于任意的和，考慮這樣的三元組：使得方陣第i行和第j行在第k列都是1.由于第k列這樣的三 元組的個(gè)數(shù)為，故這樣的三元組的總數(shù)為

其次，再用另外一種方法來(lái)計(jì)算上述那樣的三元組的總數(shù)：對(duì)于任意的，記為方陣第i行和第j行中同一列都為1的列數(shù)，則有

.

于是，由條件有.

從而，

即.

對(duì)于n=10，圖2是一個(gè)滿足要求的方針：

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