Question

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

Answer 1

【答案】13

【解析】

的最小值為13.

由題設(shè)知的子集數(shù).

當時,記子集族,

，

顯然,對于, ①

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

首先證明：對于,均有.

事實上,假設(shè)存在,有,則.此時, ,.

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

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

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

于是,結(jié)論成立.

設(shè).不妨設(shè).

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

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

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

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

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

因此,.

下面定義數(shù)表序列如下：,.

其中,為數(shù)表,其每個數(shù)均為.

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

接下來對,用數(shù)學(xué)歸納法證明：滿足題設(shè)的兩個條件.

顯然, 滿足條件.

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

考慮.

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

;

;

;

.

而數(shù)不在中出現(xiàn),因此,它們是兩兩不同的.

所以, 滿足題設(shè)條件.

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

綜上,的最小值為13.