Question

【题目】求最小的正整数,使得存在一个的数阵满足如下条件： (1)每一个数均属于集合; (2)记为数阵中第行中的数组成的集合, 为第列中的数组成的集合,则,是4026个不同的集合.

Answer 1

【答案】13

【解析】

的最小值为13.

由题设知的子集数.

当时,记子集族,

，

显然,对于, ①

而有个子集,故恰有个子集不属于子集族.

首先证明：对于,均有.

事实上,假设存在,有,则.此时, ,.

结合式①,至少有个子集均不在子集族中,矛盾.

其次证明：要么对,均有,要么对,均有.

事实上,若存在集合,使得,由于对于,均有,且,故.

于是,结论成立.

设.不妨设.

于是,中元素个数小于的子集均不在子集族中；再结合式①,知这些子集也不在子集族中.

当时, 中元素个数小于的子集数为,矛盾;

当时, 中元素个数小于的子集数为,矛盾.

于是, ,即子集族中不包含元素个数小于6的子集.但恰有70个子集不在子集族中,故至少有个子集在子集族中.

结合式①,这些子集中的任意一个的补集(对)的元素个数均大于6,且均不属于子集族.于是,至少有个子集不在子集族中.但,矛盾.

因此,.

下面定义数表序列如下：,.

其中,为数表,其每个数均为.

易知,对每一个,数表为数表,且其中的数均属于集合.

接下来对,用数学归纳法证明：满足题设的两个条件.

显然, 满足条件.

假设满足题设条件,其行与列中的数组成的集合分别为,.

考虑.

对于,其行与列中的数组成的集合分别为

;

;

;

.

而数不在中出现,因此,它们是两两不同的.

所以, 满足题设条件.

故为20482048数表,且其中的数均属于集合{1,2,…,13},对于,则的左上角20132013的数阵满足题设的两个条件.

综上,的最小值为13.