IMO2021-6の別解
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
をみてたらでてきてびっくりしました.
