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 1 of 5: State the answer

Previous step Next step

In plain words

Doubling the number of rows should roughly cost one more unavoidable red circle, which is exactly the behavior of a base-2 logarithm.

k=\lfloor\log_2 n\rfloor+1

Detailed analysis

The claimed answer is $k=\lfloor\log_2n\rfloor+1$ ; the rest of the solution proves both that some triangle forces every path to meet at most this many red circles, and that every triangle guarantees a path meeting at least this many.