Question

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

Answer 1

【答案】89

【解析】

先證.

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

由于 ，故可取.

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

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

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

用數學歸納法證明更一般的結論：

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

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

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

假設n=k時結論成立，要證n=k+2時結論成立.

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

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

由歸納假設，知對由另k個頂點構成的誘導子圖，存在的k個子集滿足相應的條件.取.

將大于的正整數成為“新元素”.

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

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

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

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

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

在經過一系列添加新元素的操作后，設變成，

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

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

故n=k+2時結論成立.

因此，對一切正整數n，結論成立.

特別地，當時，由，

知存在集合滿足條件.

綜上，n的最大值為89.