2

IMO2021-6の別解

474
1
$$\newcommand{Aut}[0]{\mathrm{Aut}} \newcommand{C}[0]{\mathbb{C}} \newcommand{char}[0]{{\bf char}} \newcommand{comp}[0]{\circ} \newcommand{core}[0]{\rm{core}} \newcommand{gen}[1]{\langle #1 \rangle} \newcommand{imply}[0]{\Rightarrow} \newcommand{iso}[0]{\simeq} \newcommand{lnormal}[0]{\triangleleft } \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{rnormal}[0]{\triangleright} \newcommand{semiprod}[3]{{#1}\ltimes_{#2}#3} \newcommand{Z}[0]{\mathbb{Z}} $$

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

証明

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

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

$S=\{\sum_{i=1}^{m}b_i\boldsymbol{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^{2k}$となる。一方、$b_i$の選び方は$m^m$通りある。$2k< m$なので、鳩ノ巣原理より、$\sum_{i=1}^{m}b_iu_i=\sum_{i=1}^{m}c_iu_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\}$とし、$\boldsymbol{a}=(a_1,...,a_k)$とする。条件より、$\boldsymbol{u_i}\in\{0,1\}^k(i=1,...,m)$であって、$\boldsymbol{u_i}\cdot \boldsymbol{a}=m^i$を満たすものがとれる。上の補題のようにに$b_i$をとると、$0=(\sum_{i=1}^{m}b_i\boldsymbol{u_i})\cdot \boldsymbol{a}=\sum_{i=1}^{m}b_i(\boldsymbol{u_i}\cdot \boldsymbol{a})=\sum_{i=1}^{m}b_im^i$となる。ここで$b_i>0$となる最大の$i$$j$と置く。すると、$-b_jm^j=\sum_{i=1}^{j-1}b_im^i$となる。左辺の絶対値は$m^j$以上だが、右辺は$m^j-1$以下なので矛盾。よって$m\leq2k$となる。

気持ち

実験をしてみる:
例えば$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\}\imply 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 2w$であり、$y+w\neq 2x+z$であり、$x+y\neq w+z$なので、これは不可能。ゆえに、$|A|\geq 4$が必要になる。

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

投稿日:2021727
更新日:20231114

この記事を高評価した人

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

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

バッジはありません。

投稿者

bd
43
6852

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中