若整数 $a,b$ 既不互质，又不存在整除关系，则称 $a,b$ 是一个“联盟”数对．设 $A$ 是集合 $M=\{1,2,\cdots,2014\}$ 的 $n$ 元子集，且 $A$ 中任两数皆是“联盟”数对，求 $n$ 的最大值．
【难度】
【出处】
2014年全国高中数学联赛江西省预赛
【标注】
【答案】
略
【解析】
设 $A$ 是元素个数最多的一个联盟子集，$$A=\{a_1,a_2,\cdots ,a_n\}.$$若 $a_j$ 是集合 $A$ 中的最小数，显然 $a_j>1$．
如果 $a_j \leqslant 1007$，则得 $2a_j \leqslant 2014$，即 $2a_j \in M$，而 $2a_j \not \in A$（因为 $2a_j$ 与 $a_j$ 有整除关系）．
在 $A$ 中用 $2a_j$ 代替 $a_j$，其他元素不变，称为子集 $A'$，则 $A'$ 仍然是联盟子集．这是由于对于 $A$ 中异于 $a_j$ 的任一元素 $a_i$，因为 $a_j$ 与 $a_i$ 不互质，故 $2a_j$ 与 $a_i$ 也不互质．
再说明 $2a_j$ 与 $ a_i$ 没有整除关系：
因为 $a_j \nmid a_i$ 所以 $ 2a_j \nmid a_i$．
若 $a_i \mid 2a_j$，设 $2a_j=ka_i$（显然 $k \neq 1,2$，否则 $a_i$，$a_j$ 有整除关系），则 $k>2$，于是 $a_i<a_j$，这与 $a_j$ 的最小性矛盾．
因此 $A'$ 仍然是联盟子集，并且仍然是 $n$ 元集合．
重复以上做法，直至子集中的元素都大于 $1007$ 为止，于是得到 $n$ 元联盟子集$$B=\{b_1,b_2,\cdots ,b_n\},$$其中 $1007<b_j\leqslant 2014$，即$$B \subseteq \{1008,1009,\cdots ,2014\}.$$因为任意两个相邻整数必互质，所以在这 $1007$ 个连续正整数中至多能取到 $504$ 个互不相邻的数，即 $n \leqslant 504$．
又根据前面所述的构造可知，$n$ 的最大值为 $504$．
如果 $a_j \leqslant 1007$，则得 $2a_j \leqslant 2014$，即 $2a_j \in M$，而 $2a_j \not \in A$（因为 $2a_j$ 与 $a_j$ 有整除关系）．
在 $A$ 中用 $2a_j$ 代替 $a_j$，其他元素不变，称为子集 $A'$，则 $A'$ 仍然是联盟子集．这是由于对于 $A$ 中异于 $a_j$ 的任一元素 $a_i$，因为 $a_j$ 与 $a_i$ 不互质，故 $2a_j$ 与 $a_i$ 也不互质．
再说明 $2a_j$ 与 $ a_i$ 没有整除关系：
因为 $a_j \nmid a_i$ 所以 $ 2a_j \nmid a_i$．
若 $a_i \mid 2a_j$，设 $2a_j=ka_i$（显然 $k \neq 1,2$，否则 $a_i$，$a_j$ 有整除关系），则 $k>2$，于是 $a_i<a_j$，这与 $a_j$ 的最小性矛盾．
因此 $A'$ 仍然是联盟子集，并且仍然是 $n$ 元集合．
重复以上做法，直至子集中的元素都大于 $1007$ 为止，于是得到 $n$ 元联盟子集$$B=\{b_1,b_2,\cdots ,b_n\},$$其中 $1007<b_j\leqslant 2014$，即$$B \subseteq \{1008,1009,\cdots ,2014\}.$$因为任意两个相邻整数必互质，所以在这 $1007$ 个连续正整数中至多能取到 $504$ 个互不相邻的数，即 $n \leqslant 504$．
又根据前面所述的构造可知，$n$ 的最大值为 $504$．
答案
解析
备注
