Question

【题目】设自然数。求证:全体不大于n的合数可重新排列(不一定按原来的大小顺序排列)，使得每三个依次相邻的数都有大于1的公因数(例如，当时，排列就满足要求)。

Answer 1

【答案】见解析

【解析】

对于，下面构造一种排列，使之满足要求.

令为所有的小于或等于的奇质数.因为，所以，即.令x为合数，且x为的奇数倍数}，

，

特别地，.

C={x是小于或等于n的偶合数，且.

我们再证明如下两个事实:

(1)

(2) 及.

因为，所以，且，从而，即.故(1)得证.

因为n≥25.所以，.从而，.

又均为奇数.所以，，从而，(它等价于).故(2)得证.

由(1)(2)可知把全体不大于n的合数组成如下的一个排列:

容易验证:排列①中各数两两不相等，它们恰是不大于n的全体合数且每三个依次相邻的数都有大于1的公因数.故本题得证.