第5問

n

を正の整数とする。日本三角形とは、正三角形状に並んだ

1+2+\cdots+n

個の円からなり、各

i=1,2,\ldots,n

に対して第

i

行にはちょうど

i

個の円があり、そのうちちょうど一つが赤く塗られているものである。日本三角形における忍者経路とは、最上段から出発し、ある円からその真下にある二つの円のいずれか一方へ進むことを繰り返して最下段で終わる、

n

個の円からなる列である。

n

を用いて、どの日本三角形にも赤い円を少なくとも

k

個含む忍者経路が存在するような最大の

k

を求めよ。

ステップ 4/5: 行の合計に対する鳩の巣原理による漸化式

前のステップ次のステップ

ざっくり言うと

ある行全体で最良経路の値を合計し、次の行と比較すると、合計が線形よりも明らかに速く増加しなければならないことが分かる。なぜなら鳩の巣原理により、ある行の中の最大の単一の値はすでにその行の合計のかなりの割合を占めているからである。

S_j=\sum_{i=0}^{j}f(i,j),\qquad S_{j+1}\ge S_j+\left\lceil\dfrac{S_j}{j}\right\rceil+1

詳しい解説

$S_j=\sum_{i=0}^jf(i,j)$ とおく。鳩の巣原理により、行 $j$ のある項 $f(m,j)$ は平均 $S_j/(j+1)$ 以上であり、この最大の項を行 $j+1$ への寄与を作る際に再利用すると（そこへ至る両方の枝を通じて、さらに行 $j+1$ 自身の赤い円による必須の $+1$ とともに）、漸化式 $S_{j+1}\ge S_j+\left\lceil S_j/j\right\rceil+1$ が得られる。