如何证明两类整数集合的n元子集分别存在连续元素与互素元素？

咱们用反证法来推导矛盾，逻辑会非常清晰：

假设存在一个n元子集$S$，其中没有任何两个连续元素。把$S$中的元素按从小到大排列：$a_1 < a_2 < ... < a_n$。因为不存在连续元素，所以对任意$1 \leq i \leq n-1$，都有$a_{i+1} \geq a_i + 2$。

由此可以推算出$a_n$的最小值：$a_1 \geq 1$，$a_2 \geq 1+2=3$，$a_3 \geq 3+2=5$……以此类推，$a_n \geq 1 + 2(n-1) = 2n-1$。

但原集合的最大元素是$2n-2$，这和$a_n \geq 2n-1$直接矛盾！因此假设不成立，原命题得证。

你的思路真的太巧妙了！完全命中了问题的核心，我来帮你把整个证明梳理得更顺畅，再补上连续元素互素的欧几里得算法验证：

1. 情况1：子集包含元素1
   1和任意正整数的最大公约数都是1，所以1和子集中其他所有元素都互素，直接满足结论。

2. 情况2：子集不包含元素1
   可选元素范围变为{2,3,…,2n-1}，这个集合共有$(2n-1)-2+1=2n-2$个元素。根据问题1的结论，从这2n-2个元素中选取n个，必然存在至少两个连续元素。

接下来用欧几里得算法证明：任意两个连续正整数$k$和$k+1$互素。

设$d = \gcd(k, k+1)$，根据最大公约数的定义，$d$能整除$k$，也能整除$k+1$。那么$d$必然能整除这两个数的差：$(k+1)-k=1$。而能整除1的正整数只有1，所以$d=1$，即$k$和$k+1$互素。

结合两种情况，原命题完全得证。

内容的提问来源于stack exchange，提问作者Orgenplop