ISL2018-A3

SLP,ISL

268

はじめに

　最近解いたISLの問題がかなり面白かった(のと夏休みの宿題が溜まった)ので，その問題の解説をしようと思います．

(ISL2018-A3　原文をかなり適当に翻訳しました)

　任意の正の整数からなる集合$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$を考えてあげます．

(ISL2018-A3　改)

　正の整数からなる集合$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$つ前の要素(小さい順に並べたとき．)の逆数がはまるのでこれを$1/z$とすると，

$\dfrac{1}{z} \geq \dfrac{2}{y} →$ $z \leq 2y$

が分かります．つまり，$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^*)}$は満たされない．