Question

【題目】求最小的正整數,使得存在一個的數陣滿足如下條件： (1)每一個數均屬于集合; (2)記為數陣中第行中的數組成的集合, 為第列中的數組成的集合,則,是4026個不同的集合.

Answer 1

【答案】13

【解析】

的最小值為13.

由題設知的子集數.

當時,記子集族,

，

顯然,對于, ①

而有個子集,故恰有個子集不屬于子集族.

首先證明：對于,均有.

事實上,假設存在,有,則.此時, ,.

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

其次證明：要么對,均有,要么對,均有.

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

于是,結論成立.

設.不妨設.

于是,中元素個數小于的子集均不在子集族中；再結合式①,知這些子集也不在子集族中.

當時, 中元素個數小于的子集數為,矛盾;

當時, 中元素個數小于的子集數為,矛盾.

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

結合式①,這些子集中的任意一個的補集(對)的元素個數均大于6,且均不屬于子集族.于是,至少有個子集不在子集族中.但,矛盾.

因此,.

下面定義數表序列如下：,.

其中,為數表,其每個數均為.

易知,對每一個,數表為數表,且其中的數均屬于集合.

接下來對,用數學歸納法證明：滿足題設的兩個條件.

顯然, 滿足條件.

假設滿足題設條件,其行與列中的數組成的集合分別為,.

考慮.

對于,其行與列中的數組成的集合分別為

;

;

;

.

而數不在中出現,因此,它們是兩兩不同的.

所以, 滿足題設條件.

故為20482048數表,且其中的數均屬于集合{1,2,…,13},對于,則的左上角20132013的數陣滿足題設的兩個條件.

綜上,的最小值為13.