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 4 of 5: A pigeonhole recurrence for the row totals

Previous step Next step

In plain words

Summing the best-path counts across an entire row and comparing it with the next row shows the total must grow noticeably faster than linearly, because the largest single value in a row is, by pigeonhole, already a sizable fraction of the row's total.

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

Detailed analysis

Let $S_j=\sum_{i=0}^jf(i,j)$ . By pigeonhole, some entry $f(m,j)$ in row $j$ is at least the average $S_j/(j+1)$ , and reusing this maximal entry when forming its contributions to row $j+1$ (through both branches leading into it, together with the mandatory $+1$ from row $j+1$ 's own red circle) gives the recurrence $S_{j+1}\ge S_j+\left\lceil S_j/j\right\rceil+1$ .