IMO2021-6の別解

552

IMO2021の6番で本番に思いついた解答が想定解と若干違うので解説します。最初に解答を書いて、そのあとお気持ちを少し書きます。問題については http://www.imo-official.org/problems.aspx を見てください。

証明

背理法を使う。すなわち、 $| A | = k > 0$ であり $m > 2 k$ と仮定して矛盾を導く。

$u_{i} \in {0, 1}^{k} (i = 1, . . ., m)$ のとき、 $\sum_{i = 1}^{m} b_{i} u_{i} = 0$ を満たす $b_{i} \in (- m, m) \cap Z$ であって、少なくも一つは0でないようなものが存在する。

$S = {\sum_{i = 1}^{m} b_{i} u_{i} | b_{i} \in [0, m) \cap Z}$ と置く。この時、 $S \subset ([0, m^{2} - m] \cap Z)^{k}$ より、 $| S | \leq (m^{2} - m + 1)^{k} \leq m^{2 k}$ となる。一方、 $b_{i}$ の選び方は $m^{m}$ 通りある。 $2 k < m$ なので、鳩ノ巣原理より、 $\sum_{i = 1}^{m} b_{i} u_{i} = \sum_{i = 1}^{m} c_{i} u_{i}$ となる $(b_{i}), (c_{i}) \in ([0, m) \cap Z)^{m}$ であって、 $(b_{i}) \neq (c_{i})$ となるものが存在する。 $d_{i} = b_{i} - c_{i}$ と置けば、 $(d_{i})$ は条件を満たす.

$A = {a_{1}, a_{2}, . . ., a_{k}}$ とし、 $a = (a_{1}, . . ., a_{k})$ とする。条件より、 $u_{i} \in {0, 1}^{k} (i = 1, . . ., m)$ であって、 $u_{i} \cdot a = m^{i}$ を満たすものがとれる。上の補題のようにに $b_{i}$ をとると、 $0 = (\sum_{i = 1}^{m} b_{i} u_{i}) \cdot a = \sum_{i = 1}^{m} b_{i} (u_{i} \cdot a) = \sum_{i = 1}^{m} b_{i} m^{i}$ となる。ここで $b_{i} > 0$ となる最大の $i$ を $j$ と置く。すると、 $- b_{j} m^{j} = \sum_{i = 1}^{j - 1} b_{i} m^{i}$ となる。左辺の絶対値は $m^{j}$ 以上だが、右辺は $m^{j} - 1$ 以下なので矛盾。よって $m \leq 2 k$ となる。

気持ち

実験をしてみる:
例えば $m = 3, A = {a, b}$ だと、 ${a, b, a + b} = 3, 9, 27$ となり、 $3 + 9 = 27 か 3 + 27 = 9 か 9 + 27 = 3$ とならないといけないが、これは不可能。
同様に、 $m = 4, A = {a, b, c}$ とすると、 ${a, b, c, a + b, b + c, c + a, a + b + c} \subset {4, 16, 64, 256}$ が必要だが、 $x, y \in {4, 16, 64, 256} \Rightarrow x + y \notin {4, 16, 64, 256}$ より、 ${a, b, a + b}$ や ${a, b + c, a + b + c}$ のようなペアが存在しなくなる。ゆえに、 ${4, 16, 64, 256}$ は ${a, b, c, a + b + c}, {a + b, b + c, c + a, a + b + c}, {a, a + b, b + c, c + a}, {a, b, b + c, c + a}$ の形しかありえない。しかし、 $x, y, z, w$ が $4, 16, 64, 256$ の並び替えの時、 $x + y + z \neq w$ であり、 $x + y + z \neq 2 w$ であり、 $y + w \neq 2 x + z$ であり、 $x + y \neq w + z$ なので、これは不可能。ゆえに、 $| A | \geq 4$ が必要になる。

このように、そもそも $| A | < m$ の時点でかなり作るのが厳しいことが分かる。なぜなら、この時点で次数の都合上、 ${m, m^{2}, m^{3}, . . ., m^{m}}$ に非自明な関係式ができるようになってしまうからだ。ただし、当然 $Z$ 係数の関係式は当然あるので、上の補題のように係数を抑える必要がある。その係数を $m$ で抑えるためには、 $k < m$ ではなく、 $2 k < m$ が必要なんだなと察しがつく。

次に補題を証明することを考えると、係数に $\pm$ が許される場面で $0$ を線形結合で作りたい、ということで https://yukicoder.me/problems/no/1017 や http://www1.tmtv.ne.jp/~koyama/papers/Japanese/prime.pdf が思い浮かぶ。このように鳩ノ巣論法+差分をとれば今回も証明できる。

追記(2023/11/14):この補題1, siegelの補題の証明とやってることがほぼ同じですね. (この場合は $u_{i}$ が非負なのでよりstrictにとれる)
https://integers.hatenablog.com/entry/2017/06/25/150000
をみてたらでてきてびっくりしました.

投稿日：2021年7月27日

更新日：2023年11月14日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

14241

他の人のコメント

コメントはありません。

読み込み中

IMO2021-6の別解

証明
気持ち