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 2 of 5: A doubling construction limits every path

Previous step Next step

In plain words

Grouping the rows into blocks of sizes 1, 2, 4, ..., 2^(e-1) and placing the red circles so that a single downward path can only ever pass one red circle per block caps the total at one red circle per block.

n=2^e-1\implies\text{some triangle admits no path with more than } e \text{ red circles}

Detailed analysis

For $n=2^e-1$ , split the rows into $e$ consecutive groups of sizes $1,2,4,\ldots,2^{e-1}$ (rows $1$ ; rows $2$ – $3$ ; rows $4$ – $7$ ; …; rows $2^{e-1}$ – $2^e-1$ ). Within each group the red circles can be positioned (as in the official figures) so that any ninja path, once it commits to a branch inside a group, cannot reach the other red circles of that same group before leaving it. Hence a ninja path meets at most one red circle per group, i.e. at most $e=\lfloor\log_2n\rfloor+1$ red circles in total, showing $k$ cannot exceed this value.