2013年 日本数学オリンピック本選 第１問 解答例
$${n, k}$$を正の整数とし、$${n\geqq k}$$とする。
$${n}$$人の人がいて、どの人も団体$${1}$$、$${\dots}$$、団体$${k}$$のうちちょうど１つに属している。また、どの団体ににも１人以上の人が属している。このとき、次の条件をすべて満たすように$${n}$$人の人に$${n^2}$$個のお菓子を配ることができることを示せ：
・どの人にも少なくとも１つのお菓子を配る。
・団体$${i}$$に属する人には$${a_i}$$個ずつのお菓子を配る$${(1\leqq i \leqq k)}$$
・$${1\leqq i<j\leqq k}$$ならば$${a_i > a_j}$$である。
考え方：
まずは各団体に所属している人数を$${b_i}$$とでも置きましょう。
上手く$${a_i}$$を構成する複雑な操作を考えたくなるところですが、
第１問ということもあり、素直に数式をいじれば具体的に$${a_i}$$を構成できます。
下記解答例以外にも簡単な構成方法があるかもしれません。
解答例：
$${k=1}$$の時は$${a_1=n}$$とすればよい。
以下$${k\geqq 2}$$とする。
団体$${i}$$の人数を$${b_i}$$とすると、
$$
\sum_{i=1}^k b_i = n
$$
となる。両辺を２乗すると
$$
\begin{align*}
\sum_{i=1}^k b_i^2 + 2\sum_{i < j} b_ib_j &= n^2 \\
\Rightarrow \sum_{i=1}^{k-1}\sum_{j = 1}^{k-i} (b_{i} + 2b_{i+j})b_i + b_k^2 &=n^2
\end{align*}
$$
となるので、$${a_k = b_k}$$とし,
$${1\leqq i < k}$$なる$${i}$$に対しては$${a_i = \sum_{j = 1}^{k-i} (b_{i} + 2b_{i+j})}$$と置けばこれはすべて正の整数であり、
$$
\begin{align*}
a_{i} - a_{i+1} &= \sum_{j = 1}^{k-i} (b_{i} + 2b_{i+j}) - \sum_{j = 1}^{k-i-1} (b_{i+1} + 2b_{i+j+1})\\
&= b_i + b_{i+1} > 0
\end{align*}
$$
であることから、$${1\leqq i < j \leqq k}$$ のとき$${a_i > a_j}$$となるので
すべての条件を満たす。
コメント：
解答例は一般の$${k}$$について求めているので少し見づらいですが、
例えば$${k=3}$$に対しては
$$
(b_1+b_2+b_3)^2 = (b_1+2b_2 + 2b_3)b_1 + (b_2+2b_3)b_2 + b_3\cdot b_3
$$
のように、$${i}$$が小さい方から$${b_i}$$が出てくる項をまとめているだけです。
お知らせ：
少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
間違いなど見つけましたら是非お教えください。
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)