第5题

设

n

为正整数。一个日本三角形由排成等边三角形状的

1+2+\cdots+n

个圆圈组成，使得对每个

i=1,2,\ldots,n

，第

i

行恰好有

i

个圆圈，其中恰好一个被染成红色。日本三角形中的忍者路径是指从最顶行出发，每次从一个圆圈走到其正下方两个圆圈之一，最终止于最底行的

n

个圆圈组成的序列。用

n

表示，求最大的

k

，使得每个日本三角形中都存在一条至少包含

k

个红色圆圈的忍者路径。

第 5/5 步：求解递推式以完成证明

上一步下一步

通俗地说

展开这个递推式可以看出，每当行号翻倍时，行总和大约会增加一整个平均值单位，这正是产生对数保证的机制。

S_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=2^c+r$ ，其中 $0\le r<2^c$ ，对 $n$ 用第4步的递推式作归纳可得 $S_n\ge cn+2r+1$ （归纳步骤按 $n+1$ 是否为 $2$ 的幂分为两种情形，两种情形都能干净地完成归纳）。两边除以 $n$ 得到 $S_n/n\ge c+(2r+1)/n>c$ ，又因为第 $n$ 行中某一项至少等于平均值 $S_n/n$ ，该项至少为 $c+1=\lfloor\log_2n\rfloor+1$ 。因此每个日本三角形都存在一条至少含有 $\lfloor\log_2n\rfloor+1$ 个红色圆圈的忍者路径，这与第2步的构造相符，并证明了 $k=\lfloor\log_2n\rfloor+1$ 。