MathLabs

第1問

a1,…,ama_1,\ldots,a_m を {1,…,n}\{1,\ldots,n\} の相異なる元とし、i≤ji\le j かつ ai+aj≤na_i+a_j\le n ならばその和もいずれかの aka_k であるとする。a1+⋯+amm≥n+12\frac{a_1+\cdots+a_m}{m}\ge\frac{n+1}{2} を証明せよ。
ステップ 3/3: 組を足し合わせる
ざっくり言うと

各組の不等式を足して全要素の和を得る。

2∑i=1mai≥m(n+1)2\sum_{i=1}^m a_i\ge m(n+1)
詳しい解説

k=1,…,⌊(m+1)/2⌋k=1,\ldots,\lfloor(m+1)/2\rfloor について ak+am−k+1≥n+1a_k+a_{m-k+1}\ge n+1 を足す(mm が奇数なら中央の不等式は一度だけ数える)。これは 2∑i=1mai≥m(n+1)2\sum_{i=1}^m a_i\ge m(n+1) と同値であり、2m2m で割れば a1+⋯+amm≥n+12\frac{a_1+\cdots+a_m}{m}\ge\frac{n+1}{2} を得る。