第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$ 。