トップ› 京都大学› 1980年› 文系第5問

京都大学 1980年文系第5問解説

方針・初手

集合 $S$ の要素を大きい順に並べて考える。すべての要素が「正の数」であるという条件から、任意の2要素を選んだとき、大きい方から小さい方を引いた値（正の差）のみが必ず集合 $S$ に属することがわかる。ある要素 $x_i$ に着目し、「$x_i$ から自分より小さい要素を引いて作られる値の集合」と「$S$ の要素のうち $x_i$ より小さいものの集合」を比較し、これらが完全に一致することを利用して、隣り合う要素の差が常に一定になることを導く。

解法1

集合 $S$ の要素はすべて正の数である。 $S$ の要素を大きい順に並べ替え、

$$ x_1 > x_2 > \dots > x_n > 0 $$

とする。 $1 \leqq i < j \leqq n$ を満たす任意の $i, j$ について、$x_i > x_j$ より

$$ x_i - x_j > 0, \quad x_j - x_i < 0 $$

である。集合 $S$ は正の数のみを要素にもつため、負の数である $x_j - x_i$ は $S$ に属さない。与えられた条件「$x_i - x_j$ と $x_j - x_i$ の少なくとも一方は $S$ に属する」より、正の差である $x_i - x_j$ は必ず $S$ に属する。

ここで、任意の $i \ (1 \leqq i \leqq n-1)$ について考える。 $S$ の要素のうち、$x_i$ より小さいものの集合を $S_i$ とする。

$$ S_i = \{x_{i+1}, x_{i+2}, \dots, x_n\} $$

$S_i$ の要素数は $n-i$ 個である。

一方、$x_i$ から自分より小さい要素を引いて得られる値の集合を $D_i$ とする。

$$ D_i = \{x_i - x_{i+1}, x_i - x_{i+2}, \dots, x_i - x_n\} $$

前述の通り、$D_i$ の各要素はすべて $S$ に属する。また、各 $x_k > 0$ であるから、$x_i - x_k < x_i$ であり、$D_i$ の要素はすべて $x_i$ より小さい。したがって、$D_i$ のすべての要素は $S_i$ に属する ($D_i \subseteq S_i$)。さらに、$x_{i+1}, \dots, x_n$ はすべて異なる値であるため、$D_i$ の要素もすべて異なり、その要素数は $n-i$ 個である。 $S_i$ と $D_i$ は要素数が等しい有限集合であり、包含関係をもつため、両者は完全に一致する（$D_i = S_i$）。

2つの集合が一致するため、それぞれの「最小の要素」も等しい。 $S_i$ の最小の要素は $x_n$ である。 $D_i$ の要素は $x_i - x_k$ の形をしており、引く数 $x_k$ が最大のときに値は最小となるため、$D_i$ の最小の要素は $k = i+1$ のときの $x_i - x_{i+1}$ である。したがって、

$$ x_i - x_{i+1} = x_n $$

が成り立つ。これがすべての $i \ (1 \leqq i \leqq n-1)$ について成り立つため、

$$ x_1 - x_2 = x_2 - x_3 = \dots = x_{n-1} - x_n = x_n $$

となる。これは、要素を昇順（小さい順）に並べた列 $x_n, x_{n-1}, \dots, x_1$ が、初項 $x_n$、公差 $x_n$ の等差数列であることを意味する。よって、$a_1, a_2, \dots, a_n$ の順序を適当に変えれば等差数列になることが示された。

解説

要素の差を集めた集合と、元の部分集合が一致することを利用する、論理的で美しい証明問題である。「実数」という条件からスタートする類似問題もあるが、本問は「正の数」という条件が初めからついているため、「要素がすべて同じ符号である」ことを背理法で証明するステップが省かれている。「要素の数が同じで、一方がもう一方に含まれるなら、その2つの集合は完全に同じものである」という有限集合の性質を使いこなし、最小値同士を比較して公差をあぶり出すアプローチは、難関大の整数・集合問題で時折必要になる考え方だ。