Question

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

Answer 1

【答案】89

【解析】

先證.

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

由于 ，故可取.

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

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

再證明：當(dāng)時(shí)，對任意n階簡單圖，存在集合滿足條件.

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

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

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

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

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

若每兩個(gè)頂點(diǎn)均不相鄰，取所有為空集即可.

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

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

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

因?yàn)?/span>、相鄰，所以，取新元素添加到、中.

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

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

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

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

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

則對任意i、j，當(dāng)且僅當(dāng)與相鄰.

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

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

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

特別地，當(dāng)時(shí)，由，

知存在集合滿足條件.

綜上，n的最大值為89.