Problem 5

Let

n

be a positive integer. A Japanese triangle consists of

1+2+\cdots+n

circles arranged in an equilateral triangular shape such that for each

i=1,2,\ldots,n

, the

i

-th row contains exactly

i

circles, exactly one of which is colored red. A ninja path in a Japanese triangle is a sequence of

n

circles obtained by starting in the top row, then repeatedly going from a circle to one of the two circles immediately below it, and finishing in the bottom row. In terms of

n

, find the greatest

k

such that in each Japanese triangle there is a ninja path containing at least

k

red circles.

Step 5 of 5: Solve the recurrence to finish

Previous step Next step

In plain words

Unrolling the recurrence shows the row total grows by roughly a full unit of average value every time the row index doubles, which is precisely the mechanism that produces a logarithmic guarantee.

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

Detailed analysis

Writing $n=2^c+r$ with $0\le r<2^c$ , induction on $n$ using the recurrence of Step 4 shows $S_n\ge cn+2r+1$ (the inductive step splits into whether $n+1$ is a power of $2$ or not, both cases closing the induction cleanly). Dividing by $n$ , $S_n/n\ge c+(2r+1)/n>c$ , and since some entry of row $n$ is at least the average $S_n/n$ , that entry is at least $c+1=\lfloor\log_2n\rfloor+1$ . Hence every Japanese triangle has a ninja path with at least $\lfloor\log_2n\rfloor+1$ red circles, matching the construction of Step 2 and proving $k=\lfloor\log_2n\rfloor+1$ .