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