MathLabs

第5問

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

行をサイズ 1, 2, 4, ..., 2^(e-1) のブロックにまとめ、下向きの経路が各ブロックにつきちょうど一つの赤い円しか通れないように赤い円を配置することで、合計をブロックごとに一個に抑える。

n=2e−1  ⟹  some triangle admits no path with more than e red circlesn=2^e-1\implies\text{some triangle admits no path with more than } e \text{ red circles}
詳しい解説

n=2e−1n=2^e-1 のとき、行を大きさ 1,2,4,…,2e−11,2,4,\ldots,2^{e-1} の ee 個の連続したグループに分ける（行 11；行 22–33；行 44–77；…；行 2e−12^{e-1}–2e−12^e-1）。各グループ内で赤い円を（公式の図のように）配置すれば、忍者経路はいったんグループ内のある枝を選ぶと、その道を離れるまでに同じグループの他の赤い円には到達できないようにできる。したがって忍者経路は各グループにつき高々一つの赤い円しか通らず、すなわち合計で高々 e=⌊log⁡2n⌋+1e=\lfloor\log_2n\rfloor+1 個の赤い円しか通らないので、kk はこの値を超えられないことが分かる。