第5题

设

n

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

1+2+\cdots+n

个圆圈组成，使得对每个

i=1,2,\ldots,n

，第

i

行恰好有

i

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

n

个圆圈组成的序列。用

n

表示，求最大的

k

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

k

个红色圆圈的忍者路径。

第 1/5 步：给出答案

通俗地说

把行数翻倍大致只会多付出一个不可避免的红色圆圈，这正是以2为底的对数所表现的行为。

k=\lfloor\log_2 n\rfloor+1

详细分析

所求答案是 $k=\lfloor\log_2n\rfloor+1$ ；解答的其余部分证明了：既存在某个三角形使每条路径最多经过这么多红色圆圈，也证明了每个三角形都保证存在一条至少经过这么多红色圆圈的路径。