奇数を 2a + 1 の形で表す

正の奇数は 1, 3, 5, \ldots と並び、0 以上の整数 a を使ってどれも 2a + 1 と表せます。そこで l = 2a + 1、m = 2b + 1、n = 2c + 1 とおく。

l + m + n = K に代入すると 2(a + b + c) + 3 = K となり、条件は次の式に変わります。

a + b + c = \dfrac{K - 3}{2}

K は 3 より大きな奇数だから、右辺は正の整数。(l, m, n) と (a, b, c) は 1 つずつ対応するため、N はこの式を満たす 0 以上の整数の組の個数と等しくなる。

図は K = 11 の例です。11 個のマスを長さ l、m、n に区切り、それぞれ先頭の 1 マスを除くと、残りは 2 マスずつの組に分かれる。その組の数が a、b、c にあたります。

(1) 玉と仕切りの並べ方で数える

K = 99 では \dfrac{K - 3}{2} = 48 だから、数えるのは a + b + c = 48 を満たす 0 以上の整数の組です。

48 個の玉と 2 本の仕切りを 1 列に並べ、左の仕切りより左にある玉の数を a、2 本のあいだを b、右の仕切りより右を c とする。並べ方と組 (a, b, c) は 1 つずつ対応します。

玉と仕切りを合わせた 50 か所のうち、仕切りを置く 2 か所を決めれば並びは 1 通りに決まる。

N = {}_{50}\mathrm{C}_2 = \dfrac{50 \cdot 49}{2} = 1225

図の下の (l, m, n) は、上の (a, b, c) から l = 2a + 1 などで戻した組です。

図は l を横、m を縦にとって組を点で表したもので、n = 99 - l - m は点の位置で決まります。1225 個の点のうち、3 本の直線 l = m、m = n、n = l の上にある点を数える。

l = m のとき n = 99 - 2l で、これが正になるのは l \leqq 49 のとき。奇数から偶数を引いた n はいつも奇数なので、l = 1, 3, \ldots, 49 の 25 個がすべて条件を満たします。

3 つとも等しいのは 3l = 99 のときで、(33, 33, 33) の 1 個だけ。3 本の直線はこの点で交わる。

l = m の 25 個から (33, 33, 33) を除いた 24 個は、ちょうど 2 つが等しい組です。m = n だけを満たす組と n = l だけを満たす組も 24 個ずつあり、互いに重ならない。

合わせて 24 \times 3 + 1 = 73 個になります。

(1) と同じ数え方を一般の K で行うと、玉は \dfrac{K - 3}{2} 個、仕切りは 2 本で、並べる場所は \dfrac{K + 1}{2} か所。N は、そこから仕切りを置く 2 か所を選ぶ組合せの総数です。

N = \dfrac{1}{2} \cdot \dfrac{K + 1}{2} \cdot \dfrac{K - 1}{2} = \dfrac{K^2 - 1}{8}

K = 99 を代入すると \dfrac{9800}{8} = 1225 となり、(1) の値と一致します。

N > K を整理すると K^2 - 8K - 1 > 0 で、K(K - 8) > 1 と同じ。K = 5、7 では左辺は負になり、K = 9 では 9 > 1 となって成り立つ。

求める最小の K は 9 です。図のとおり、K = 7 では N = 6 で K に届かず、K = 9 で N = 10 となって K を上回る。