Question

【題目】求正整數(shù)n的最大值，使得對任意一個以為頂點的n階簡單圖，總能找到集合的n個子集，滿足：當且僅當與相鄰.

Answer 1

【答案】89

【解析】

先證.

假如，考慮完全二部圖（即其中是所有的邊），并假設(shè)n個子集滿足條件.

由于 ，故可取.

易知，所有這些兩兩不同（否則，假如，且.則.但當時，，故只有.類似地，，矛盾）.

因此，至少含有個不同的元素，但這不可能.

再證明：當時，對任意n階簡單圖，存在集合滿足條件.

用數(shù)學歸納法證明更一般的結(jié)論：

對任意n階簡單圖，總能找到的n個子集滿足條件，其中， （當n=1時，規(guī)定只能取空集）.

當n=1時，條件無矛盾，結(jié)論成立.

當n=2時，令，可根據(jù)、是否相鄰決定取或空集，結(jié)論仍成立.

假設(shè)n=k時結(jié)論成立，要證n=k+2時結(jié)論成立.

若每兩個頂點均不相鄰，取所有為空集即可.

接下來假設(shè)存在相鄰頂點，不妨設(shè)、相鄰.

由歸納假設(shè)，知對由另k個頂點構(gòu)成的誘導子圖，存在的k個子集滿足相應(yīng)的條件.取.

將大于的正整數(shù)成為“新元素”.

因為、相鄰，所以，取新元素添加到、中.

對任意一個，若與、均不相鄰，則不需要用到新元素；

若與、均相鄰，則取一個未用過的最小的新元素，將其添加到、、中；

若與、中的一個相鄰，不妨設(shè)與相鄰，則取一個未用過的最小的新元素，將其添加到、中，但不能添加到中.無論如何每個至多用到一個新元素.

綜上，至多用到1+k個不同的新元素.

在經(jīng)過一系列添加新元素的操作后，設(shè)變成，

則對任意i、j，當且僅當與相鄰.

又只用了不多于1+k個新元素，則最大的元素不超過.

故n=k+2時結(jié)論成立.

因此，對一切正整數(shù)n，結(jié)論成立.

特別地，當時，由，

知存在集合滿足條件.

綜上，n的最大值為89.