Question

【题目】若整数、既不互素，又不存在整除关系，则称、为一个“联盟”数对.设为集的元子集，且中任两数均为联盟数对.求的最大值

Answer 1

【答案】504

【解析】

称这种子集为“联盟子集”.

首先构造一个联盟子集，其中具504有个元素.为此，取

.

接下来证明，504就是的最大值。

设为元素个数最多的一个联盟子集.

若为集合中的最小数，显然，.若，则，即，

显然，，（这是因为与有整除关系）.

考虑在集合中用，替代，其他元素不变，成为子集，则仍为联盟子集，这是因为对于集合中异于的任一元素，由与，不互素，故与也不互素；再说明与没有整除关系，这是因为，所以，.

又若，设，(显然，否则，、有整除关系），则.于是，，这与的最小性矛盾.

故仍为联盟子集，且仍为元集.

重复以上作法，直至子集中的元素均大于1007为止。

于是，得到元联盟子集

，

即.

因为任两个相邻整数必互素，所以，在这1007个连续正整数中至多能取到504个互不相邻的数，即.

又据前面所述的构造，知的最大值即为504.