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.