互いに素な部分集合

集合 $\{1, 2, ..., 2n\}$ から任意に $n+1$ 個の整数を取り出す。
取り出した整数群には、必ず互いに素な整数が$2$つ以上存在している。


$i$ が奇数である集合$\{i, i+1\}$ を $n$ 個作成する。
集合 $\{1, 2, ..., 2n\}$から取り出した任意の整数は、上で作成した $n$ この集合のいずれかに属する。
取り出した整数が $n+1$ 個であるため、少なくとも2つの整数が同じ集合 $\{i_1, i_1+1\}$ に属することになる。
隣り合う整数 $i_1$ と $i_1+1$ は互いに素である。

Q.E.D