ISL2018A3
はじめに
最近解いたISLの問題がかなり面白かった(のと夏休みの宿題が溜まった)ので，その問題の解説をしようと思います．
任意の正の整数からなる集合$S$について，次のうち少なくとも$1$つが成り立つことを示せ．
$\mathbf{(A)}$ $S$のある部分集合$F,G ~ (F \neq G)$が存在して，$\displaystyle \sum_{x \in F} \frac{1}{x}=\sum_{x \in G} \frac{1}{x}$．
$\mathbf{(B)}$ ある$1$未満の正の有理数$r$が存在し，任意の$S$の部分集合$F$について，$\displaystyle \sum_{x \in F} \frac{1}{x} \neq r$．
ネタバレを含みます．あと原文では条件が$(1)$と$(2)$になっていますが見やすさのためにこうしてます．ご了承下さい...
.
..
.
...
.
..
.
....
.
..
.
...
.
..
.
思ったこと
かなり主張が綺麗な感じですね．というかそもそも$\mathbf{(B)}$を満たさない$S$が思い付きません(多分正整数全体の集合は満たさないんだろうけど証明ができない)．多分直接示すのは難しそうです．
考えたこと
すぐ分かること
少なくとも$1$つが成り立つ、は流石にやばいです．どっちも成り立たない集合$S$を考えてあげます．
正の整数からなる集合$S$であって，次をともに満たすものは存在しないことを示せ．
$\mathbf{(A^*)}$ $S$の任意の異なる部分集合$F,G$について，$\displaystyle \sum_{x \in F} \frac{1}{x} \neq \sum_{x \in G} \frac{1}{x}$．
$\mathbf{(B^*)}$ 任意の$1$未満の正の有理数$r$について，ある$S$の部分集合$F$が存在し，$\displaystyle \sum_{x \in F} \frac{1}{x} = r$．
この条件を言語化してみると，｢正の有理数を逆数和で表す方法はせいぜい$1$通りだよね、特に$1$未満なら必ず$1$個あるよね、(謎口調｣となります．$S$は$2$進法の進化版みたいな，スーパーハイパーなめっちゃ強いやつというイメージです．${}_{(??)}$
まず，$1$未満の正の有理数は無限に存在するので，$S$は無限集合だと分かります．ちなみにですが，この考察があまりにも明らかだからといって，答案に書き忘れないようにしましょう．($1$敗)
また，$S$は$1$を含まないとします．$1$が満たさないことが分かったら，$1$があっても満たしません．まあどうせ$1$はそんなに関係ないので...
次に分かること
$r$は常に逆数和で表せることが決まっているので，$r+\dfrac{1}{y} ~ (\lt 1)$のような形を考えると何かできそうです．$r$を逆数和で表すとき，$1/y$が現れないとしてみます．すると，$r+\dfrac{1}{y}$には$1/y$が現れます(当たり前ですが)．逆のこともいえると嬉しいです．つまり
・$r$を逆数和で表すとき$1/y$が現れるなら，$r+\dfrac{1}{y}$には$1/y$が現れない．
が言えて欲しいです．これを示してみます．もし$r+\dfrac{1}{y}$に$1/y$が現れるなら，$r$には$1/y$が現れません．ですがこれは前提と$\mathbf{(A^*)}$に矛盾しています．よって示されました．(実はこれは使わなかったんですが)
また，対偶をとることで
・$r$を逆数和で表すとき$1/y$が現れないなら，$r-\dfrac{1}{y} ~ (\gt 0)$には$1/y$が現れる．
・$r$を逆数和で表すとき$1/y$が現れるなら，$r-\dfrac{1}{y} ~ (\gt 0)$には$1/y$が現れない．
が分かります．
...ここで，この条件はめちゃくちゃ強いということが分かります．というのも
$r-\dfrac{1}{y} ~ (\gt 0)$には$1/y$が現れる $→$ $r \geq \dfrac{2}{y}$
だからです．そこで，明らかに$1/y$が現れず，$1/y$より大きい$r$を取ってくると良さそうです．これはいろいろ考えると，$y$の$1$つ前の要素(小さい順に並べたとき．)の逆数がはまるのでこれを$z$とすると，
$\dfrac{1}{z} \geq \dfrac{2}{y} →$ $2z \leq y$
が分かります．つまり，$S$のうち$k$番目に小さい要素は$2^k$で下から抑えられることが分かりました．$2^k$と聞いてピンときた人もいるかもしれませんが，これらの逆数和は$1$以下の値に収束します！ もし$1$未満の値に収束したら，それより大きく$1$より小さい有理数を$r$にすれば$\mathbf{(B^*)}$に合いません．なので，$1$に収束し，$S=\{2,4,8, \ldots 2^k, \ldots \}$ ですが，このとき$\dfrac{1}{3}$などは(有限個の)逆数和になりません．よって，この問題が解けました！
もうちょっと正確に議論する必要がありそうですが，一応これで解けています．答案では見やすいように文字の置き方とかを変えています．(なら上でもその置き方にすべきでは)
答案
$S$が問題の条件を満たすなら，$\{1\} \cup S$も条件を満たす．以下では$1 \notin S$とする．次をともに満たす$S$が存在すると仮定する．この$S$は，明らかに無限集合である．
$\mathbf{(A^*)}$ $S$の任意の異なる部分集合$F,G$について，$\displaystyle \sum_{x \in F} \frac{1}{x} \neq \sum_{x \in G} \frac{1}{x}$．
$\mathbf{(B^*)}$ 任意の$1$未満の正の有理数$r$について，ある$S$の部分集合$F$が存在し，$\displaystyle \sum_{x \in F} \frac{1}{x} = r$．
$\mathbf{(B^*)}$の$r$について，そのような$F$を$r$の$\textbf{表現}$とよぶ．また，$S$の要素のうち$k$番目に小さいものを$s_k$とする．
今，$\dfrac{1}{s_k}-\dfrac{1}{s_{k+1}}$の表現には$s_{k+1}$が含まれる．なぜなら，含まれないと仮定したとき，$\bigg(\dfrac{1}{s_{k}}-\dfrac{1}{s_{k+1}}\bigg)+\dfrac{1}{s_{k+1}}=\dfrac{1}{s_k}$の$s_{k+1}$を含む表現が存在するが，これは$\mathbf{(A^*)}$に矛盾するからである．特に
$$\dfrac{1}{s_{k}}-\dfrac{1}{s_{k+1}} \geq \dfrac{1}{s_{k+1}} ~ → ~ 2s_k \leq s_{k+1}$$
であり，$2 \leq s_1$より帰納的に$2^k \leq s_k$が分かる．
$s_i \gt 2^i$となる$i$が存在するとき，$\displaystyle \sum_{k=1}^{\infty} \dfrac{1}{s_k} \lt \sum_{k=1}^{\infty} \dfrac{1}{2^k} = 1$より$\displaystyle \sum_{k=1}^{\infty} \dfrac{1}{s_k}$は$1$未満の正の実数に収束するが，この収束値より大きく$1$より小さい有理数を$r$としてとれば$\mathbf{(B^*)}$を満たさない．
従って，任意の$k$について$s_k=2^k$だが，このとき$S$の有限個の要素の逆数和として表せる有理数は，既約分数で表したとき分母が偶数であるから，$r=\dfrac{1}{2023}$などをとれば$\mathbf{(B^*)}$は満たされない．
以上より，$\mathbf{(A^*)},\mathbf{(B^*)}$をともに満たす$S$は存在せず，題意は示された．■
感想
こういうタイプの代数はかなり好きです．A3にしては易しめな気はしますが...