MathLabs

第5問

nn を正の整数とする。日本三角形とは、正三角形状に並んだ 1+2+⋯+n1+2+\cdots+n 個の円からなり、各 i=1,2,…,ni=1,2,\ldots,n に対して第 ii 行にはちょうど ii 個の円があり、そのうちちょうど一つが赤く塗られているものである。日本三角形における忍者経路とは、最上段から出発し、ある円からその真下にある二つの円のいずれか一方へ進むことを繰り返して最下段で終わる、nn 個の円からなる列である。nn を用いて、どの日本三角形にも赤い円を少なくとも kk 個含む忍者経路が存在するような最大の kk を求めよ。
ステップ 5/5: 漸化式を解いて完成させる
前のステップ次のステップ
ざっくり言うと

漸化式を展開すると、行の番号が2倍になるたびに行の合計がおよそ平均値1単位分だけ増加することが分かり、これがまさに対数的な保証を生み出す仕組みである。

Sn≥cn+2r+1 for n=2c+r, 0≤r<2c  ⟹  max⁡if(i,n)≥c+1S_n\ge cn+2r+1\ \text{for}\ n=2^c+r,\ 0\le r<2^c\implies\max_if(i,n)\ge c+1
詳しい解説

n=2c+rn=2^c+r（ただし 0≤r<2c0\le r<2^c）と書くと、ステップ4の漸化式を用いた nn に関する帰納法により Sn≥cn+2r+1S_n\ge cn+2r+1 が示される（帰納段階は n+1n+1 が 22 のべき乗であるかどうかで場合分けされ、どちらの場合も帰納法をきれいに閉じる）。nn で割ると Sn/n≥c+(2r+1)/n>cS_n/n\ge c+(2r+1)/n>c となり、行 nn のある項が平均 Sn/nS_n/n 以上であることから、その項は少なくとも c+1=⌊log⁡2n⌋+1c+1=\lfloor\log_2n\rfloor+1 である。したがって、どの日本三角形にも少なくとも ⌊log⁡2n⌋+1\lfloor\log_2n\rfloor+1 個の赤い円を持つ忍者経路が存在し、これはステップ2の構成と一致し、k=⌊log⁡2n⌋+1k=\lfloor\log_2n\rfloor+1 を証明する。