第5問

n

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

1+2+\cdots+n

個の円からなり、各

i=1,2,\ldots,n

に対して第

i

行にはちょうど

i

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

n

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

n

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

k

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

k

を求めよ。

ステップ 1/5: 答えを述べる

ざっくり言うと

行数を2倍にすると、避けられない赤い円がおよそ1個だけ増えるはずであり、これはまさに底が2の対数の振る舞いである。

k=\lfloor\log_2 n\rfloor+1

詳しい解説

求める答えは $k=\lfloor\log_2n\rfloor+1$ である。残りの部分では、ある三角形がすべての経路にこの個数以下の赤い円しか許さないこと、そしてどの三角形にもこの個数以上の赤い円を持つ経路が存在することの両方を証明する。