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 时，把各行分成 ee 个连续的组，大小分别为 1,2,4,…,2e−11,2,4,\ldots,2^{e-1}（第 11 行；第 22–33 行；第 44–77 行；……；第 2e−12^{e-1}–2e−12^e-1 行）。在每一组内，可以像官方图示那样放置红色圆圈，使得任意一条忍者路径一旦在某组内选定一个分支，就无法在离开该组之前到达该组的其他红色圆圈。因此一条忍者路径在每组中最多经过一个红色圆圈，即总共最多经过 e=⌊log⁡2n⌋+1e=\lfloor\log_2n\rfloor+1 个红色圆圈，说明 kk 不能超过这个值。