题目内容
【题目】有一个由0和1构成的6行n列的 数字方阵，其中每行中恰有5个1，任意两行中同一列都取1的列数不超过2.求n的 最小值.
【答案】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
练习册系列答案
相关题目
