平山：ほとんど $0$ でいいってことか
平山：というか $n$ に依存しないのすごいな
宿田：問題文を、理解してきました……
平山：$0$ じゃないのが $2k$ 個以上あったとして
平山：二つ以上を一つにまとめられれば帰納法が回って
渡辺：それ言おうと思った
平石：これ $n$ は $2^k$ 以下と思っていいのか
宿田：一つ選んでバラバラにする方がそれっぽいかな
平山：というか $a$ たちが $1$ 以下で出来ればいいんだよな
兒玉：それは怪しくない？
平山：その解体経路を定数倍するだけで大丈夫では
渡辺：$1$ 以下として大丈夫だと思う
馬杉：高々 $1$ ずつ減らせば大丈夫か
渡辺：あ、出来たと思う
渡辺：$2k$ 個の $u$ から部分集合を取る方法は $2^{2k}$ 通りで
渡辺：各部分集合の元の総和は高々 $2k\cdot 2^k$ だから
渡辺：どこかで総和が被って、それを足し引きすれば
平石：ああー、なるほど
兒玉：理解した
宿田：$1$ 以下にする必要別になかったよね…？
平石：$a$ が一番小さいやつを基準にすれば大丈夫
渡辺：複数個でまとめるとか変なこと考えずには済むと思う
宿田：なるほど

• $2^{2k}$ の選び方を考えたのは, 値が制約により窮屈に並んでいるところで足して同じ値になるものを取りたいという状況から鳩の巣原理を考えたくなったのと, 値の雰囲気をみて累乗オーダーを作りたくなったことが気持ちとしてあります
• $2k$ は評価としては基本的に甘くそれ自体にはあまり意味はない, 数オリの問題において具体的な数値にどれほどの意味があるかの見立ては誤ると辛いので, 色々な可能性を考えよう

$t$ の表現のうち $0$ でない項の数が最小のものの一つを $(b_1,b_2,\cdots ,b_n)$ とし, $X=\{i\mid b_i\ne 0\},m=|X|$ とおく.

以下 $m>2k$ として矛盾を導けば良い.

$X$ の冪集合を $2^X$ とすると $|2^X|=2^m$ である. また $A\in 2^X$ に対し $\sum _{i\in A}{u}_i$ は $0$ 以上 $m\cdot 2^k$ 以下の整数である. ここで補題より鳩の巣原理を用いることで, ある異なる $A,B\in 2^X$ が存在し以下が成立する. $${\displaystyle \sum _{i\in A}{u}_i={\displaystyle \sum _{i\in B}{u}_i}}$$ さらに $C=A\cap \bar{B},D=B\cap \bar{A}$ とすると, $C\cap D=\mathrm{\varnothing }$ かつ以下が従う. $${\displaystyle \sum _{i\in C}{u}_i+{\displaystyle \sum _{i\in A\cap B}{u}_i=\sum _{i\in A}{u}_i={\displaystyle \sum _{i\in B}{u}_i={\displaystyle \sum _{i\in D}{u}_i+{\displaystyle \sum _{i\in A\cap B}{u}_i⟹\sum _{i\in C}{u}_i={\displaystyle \sum _{i\in D}{u}_i}}}}}}$$ また $A\ne B$ より $C\ne \mathrm{\varnothing }$ または $D\ne \mathrm{\varnothing }$ であるから, 一般性を失わず $C\ne \mathrm{\varnothing }$ としてよい.

$b_i(i\in C)$ で最小のものの一つを $b_l$ とする. 各 $1\leqq i\leqq n$ に対し $c_i$ を

$$c_i=\{\begin{array}{ll}{b}_i+b_l& (i\in D)\\ b_i-b_l& (i\in C)\\ b_i& (i\notin C\cup D)\end{array}$$

で定めると, 全ての $c_i$ は非負整数であり, さらに以下より $\{c_i\}$ は $t$ の表現である. $${\displaystyle \sum _{i=1}^n{c}_i{u}_i-{\displaystyle \sum _{i=1}^n{b}_i{u}_i={\displaystyle \sum _{i\in D}{b}_l{u}_i-{\displaystyle \sum _{i\in C}{b}_l{u}_i=0⟹{\displaystyle \sum _{i=1}^n{c}_i{u}_i=t}}}}}$$ 　ここで $b_i=0$ のとき, $i\in \bar{X}\subset \overline{C\cup D}$ より $c_i=b_i=0$ であり, $b_l\ne 0$ かつ $c_l=0$ より $c_i$ において $0$ でない項は $m$ 個より少ないが, これは $m$ の最小性に反する.