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 3 of 5: Count the best partial path recursively

Previous step Next step

In plain words

The largest number of red circles reachable by any partial ninja path ending at a given circle only depends on the two best partial paths ending at its two possible predecessors.

f(i,j)=\max\{f(i-1,j-1),f(i,j-1)\}+[\text{circle }(i,j)\text{ is red}]

Detailed analysis

For any Japanese triangle, let $f(i,j)$ denote the greatest number of red circles on a ninja-path segment from the top circle down to the circle in position $i$ of row $j$ (with $f(i,j)=0$ if that position does not exist). Since every path through $(i,j)$ arrives from $(i-1,j-1)$ or $(i,j-1)$ , $f(i,j)=\max\{f(i-1,j-1),f(i,j-1)\}+1$ if $(i,j)$ is red, and $f(i,j)=\max\{f(i-1,j-1),f(i,j-1)\}$ otherwise.