Just wanted to say that this problem is great, one of the best combos in recent years.

The answer is log2(n)+1.

Solved. The answer is $ k = \lfloor $log$_{2} n \rfloor +1$ Quite interesing.

The answer is $k = \lfloor \log_2 n \rfloor + 1$. To prove that one can't do better, note that it suffices to find a construction for $n = 2^m-1$ that has no path with more than $m$ circles. This is doable by placing the red cells "diagonally" such that no path intersects more than one red cell in rows $1$, $2$, $3$ through $4$, ..., $2^{m-1}$ to $2^m - 1$. An example with $m = 4$ is shown below: [asy][asy] unitsize(5mm); for (int i = 1; i < 2; ++i) { int j = 2*(i-1); fill(shift(i*dir(240)+j*dir(0))*scale(0.5)*unitcircle,lightred); } for (int i = 2; i < 4; ++i) { int j = 2*(i-2); fill(shift(i*dir(240)+j*dir(0))*scale(0.5)*unitcircle,lightred); } for (int i = 4; i < 8; ++i) { int j = 2*(i-4); fill(shift(i*dir(240)+j*dir(0))*scale(0.5)*unitcircle,lightred); } for (int i = 8; i < 16; ++i) { int j = 2*(i-8); fill(shift(i*dir(240)+j*dir(0))*scale(0.5)*unitcircle,lightred); } for (int i = 1; i < 16; ++i) { for (int j = 0; j < i; ++j) { draw(shift(i*dir(240)+j*dir(0))*scale(0.5)*unitcircle); } } [/asy][/asy] Now we show that $k = \lfloor \log_2 n \rfloor + 1$ is always achievable. To do this, for $1 \leq j \leq i \leq n$, let $a_{i,j}$ be the maximum number of red circles in any path starting from the $j$th circle in the $i$th row and going to the bottom of the triangle. We have the recurrence \[a_{i,j} = \max\{a_{i+1,j}, a_{i+1,j+1}\} + \begin{cases*} 1 & the $j$th circle in the $i$th row is colored \\ 0 & else \end{cases*}\]and we wish to show that $a_{1,1} \geq \lfloor \log_2 n\rfloor + 1$. To do this, our main claim is that \[\sum_{j=1}^{i} 2^{a_{i,j}} \geq \sum_{j=1}^{i+1} 2^{a_{i+1,j}}\]for all $i$. This will finish, since we can compute that $\sum_{j=1}^{n} 2^{a_{n,j}} = n+1$, and chaining together these inequalities shows that $2^{a_{1,1}} \geq n+ 1$. To prove the inequality, pick a specific $i$. For a given $b$, the number of $j$ with $a_{i+1,j} < b$ is strictly greater than the number of $j$ with $\max\{a_{i+1,j}, a_{i+1,j+1}\} < b$, unless the former quantity is zero. Therefore \begin{align*} \MoveEqLeft \sum_{j=1}^{i+1} 2^{a_{i+1,j}} -\sum_{j=1}^{i} 2^{\max\{a_{i+1,j}, a_{i+1,j+1}\}} \\ &= \begin{multlined}[t] \left(i+1+\sum_{b=1}^\infty 2^{b-1} \lvert \{ j : a_{i+1,j} \geq b\}\rvert\right) \\ - \left(i+\sum_{b=1}^\infty 2^{b-1} \lvert \{ j : \max\{a_{i+1,j}, a_{i+1,j+1}\} \geq b\}\rvert\right)\end{multlined} \\ & = 1 + \sum_{b=1}^\infty 2^{b-1} (1+\lvert \{ j :\max\{a_{i+1,j}, a_{i+1,j+1}\} < b\}\rvert- \lvert \{ j : a_{i+1,j} < b\}\rvert) \\ &\leq 1 + \sum_{b = 1}^{\min_j \{a_{i+1,j}\}} 2^{b-1} \\ &= 2^{\min_j \{a_{i+1,j}\}}. \end{align*}On the other hand, if $j^*$ is the location of the colored circle in row $i$, \[ \sum_{j=1}^{i} 2^{a_{i,j}} -\sum_{j=1}^{i} 2^{\max\{a_{i+1,j}, a_{i+1,j+1}\}} = 2^{\max\{a_{i+1,j^*}, a_{i+1,j^*+1}\}} \geq 2^{\min_j \{a_{i+1,j}\}}.\]Subtracting these two inequalities yields the claim.

Is this correct? Let the $i$th row from the top be denoted the $i$th "level". Label red circles with positive integers as follows. Label the top red circle with $1$. Then label the red circles inductively downwards with the smallest label $k$ for which no other red circle with the label $k$ lies "above" it. Here are the key claims: Claim 1: For any red circle with label $k$, there exists a Japanese path which intersects at least $k$ red circles and ends at $k$. Proof: By induction. Claim 2: If the "highest" circle of label $k$ is on level $m$, then there are at most $m$ circles of label $k$. Proof: Consider the diagonals oriented "/" which are left of the diagonal oriented "/" which intersects said highest circle, and also consider the diagonals orienter "\" which are right of the diagonal oriented "\" which intersects said highest circle. Then each such diagonal has at most $1$ circle of label $k$ and there are $m - 1$ such diagonals (the bound now follows by adding in your original circle.) Anyways these two claims combined readily solves the problem; the construction has already been given in the previous posts. Ok maybe actually the construction hasn't been given LOL. Anyways on row $2^k + i$ where $0 \leq i < 2^k$, just make the $2i + 1$th circle (from the right) red.

The answer is $\left \lfloor \log_2 n \right \rfloor + 1$. For convenience, we label the rows of the triangle from the top, starting the count from $1$. For each red circle $A$, we assign it a number corresponding to the maximal amount of red circles that can appear in a ninja path from the top of the triangle to $A$. We can see that in a Japanese triangle, there is a ninja path with $t$ red circles iff there is a red circle assigned with the number $t$. We are left to find the maximum number $k$ that can appear in any Japanese triangle. Claim 1: If $A,B$ get assigned by the same number $t$, then the sub-triangle with $A$ as the top can not contain $B$ and vice versa. Proof: Kinda straightforward. If the sub-triangle with $A$ as the top contains $B$, then there is a ninja path that goes to $A$, and then $B$, with at least $t+1$ red triangles, and $B$ can not be assigned the number $t$. Claim 2: there are at most $2^i$ red circles assigned with the number $i$. Proof: We proceed by induction. $i=1$ is trivial. Assume that for any $i \le t$, there are at most $2^i$ red circles assigned with the number $i$. Then, there are at most $2^{t+1}-1$ red circles assigned with a number less than or equal to $t$. Hence, there exists a red circle $A$ assigned with the number $t+1$ that lies in a row $h \le 2^{t+1}$. By Claim 1, the sub-triangle with $A$ as the top can not contain any other red circles with the number $t+1$. It also means that there are at most $2^{t+1}-1$ rows either oriented "/" or "\" that can contain a red circle of number $t+1$. By Claim 1 again, each of these rows can have at most one red circle with the number $t+1$. So there can be at most $2^{t+1}$ red circles assigned with the number $t+1$, proving the induction. The rest of the problem should be straightforward. Due to Claim 2, there is always a red circle assigned with the number $\left \lfloor \log_2 n \right \rfloor + 1$ in any Japanese triangle with $n$ rows. Using the similar idea, we can also construct a Japanese triangle where the maximal number assigned to a red circle is $\left \lfloor \log_2 n \right \rfloor + 1$. Hence, $\left \lfloor \log_2 n \right \rfloor + 1$ is the maximal number.

The answer is $\lfloor \log_2(n) \rfloor + 1$. Proof that $\lfloor \log_2(n) \rfloor + 1$ is achievable. Consider the following process. Start with an array composed of $n + 1$ zeroes. At any point, if the current array is $[a_1, a_2, \dots, a_k]$, replace it with the $k - 1$ element array \[[b_1, b_2, \dots, b_{k - 1}] = [\max(a_1, a_2), \max(a_2, a_3), \dots, \max(a_{k - 1}, a_k)]\] Finally, if the row with $k - 1$ circles has a red circle at position $i$, increase $b_i$ by one. It is straightforward to verify that at any point our $k$-element array gives, for each circle in the row with $k$ circles, the maximum number of red circles that can be visited starting from said circle. For any array consider the quantity $f(a_1, a_2, \dots, a_n) = 2^{a_1} + 2^{a_2} + \dots + 2^{a_n}$. Main claim. $f(b_1, b_2, \dots, b_{k - 1}) \ge f(a_1, a_2, \dots, a_k)$. Proof. Let $i$ be such that $a_i = \min(a_1, a_2, \dots, a_k)$. Then we have \begin{align*} \max(a_1, a_2) &\ge a_1 \quad &\max(a_i, a_{i + 1}) &\ge a_{i + 1} \\ \max(a_2, a_3) &\ge a_2 \quad &\max(a_{i + 1}, a_{i + 2}) &\ge a_{i + 2} \\ &\vdots \quad &&\vdots \\ \max(a_{i - 1}, a_i) &\ge a_{i - 1} \quad &\max(a_{k - 1}, a_k) &\ge a_k \end{align*} So before adding $1$ to any element, the value of $f$ is at least $2^{a_1} + 2^{a_2} + \dots + 2^{a_{i - 1}} + 2^{a_{i + 1}} + 2^{a_{i + 2}} + \dots + 2^{a_n} = f(a_1, \dots, a_k) - 2^{a_i}$. After adding $1$ to say, $a_j$, the value of $f$ increases by $2^{a_j}$and therefore \[f(b_1, \dots, b_{k - 1}) \ge f(a_1, \dots, a_k) - 2^{a_i} + 2^{a_j} \ge f(a_1, \dots, a_k)\] Since $a_i$ was chosen to be minimal. This proves the claim. Initially we have $f(0, 0, \dots, 0) = n + 1$ and at the end we have a single number $m$. Therefore $2^m \ge n + 1$ and $m \ge \lfloor \log_2 n \rfloor + 1$ as desired. Proof that $\lfloor \log_2(n) \rfloor + 1$ is the best possible. It suffices to exhibit a construction with $n = 2^k - 1$ rows in which at most $k$ red circles can be achieved, then prefixes of the triangle provide constructions for other $n$. For each red circle consider drawing the two diagonals parallel to the non-base sides of the triangles and recording which circles on the bottom row they touch. These form an interval of length $\ell$ where $\ell$ is the number of the row counting from the bottom. For the example in the statement we get the intervals $\{[1, 6], [1, 5], [3, 6], [3, 5], [4, 5], [1, 1]\}$. Notice that the intervals uniquely determine the circles, and that we can visit circle $A$ after circle $B$ if and only if the interval corresponding to $A$ contains the interval corresponding to $B$, therefore it suffices to give a collection of intervals of sizes $1, 2, \dots, 2^k - 1$ such that no $k + 1$ of them are nested. Consider now the collection \[ \begin{matrix} [1, 1] & [2, 3] & [3, 5] & \dots & [2^{k - 1}, 2^k - 1] \\ [1, 2^{k - 1} + 1] & [2, 2^{k - 1} + 3] & [3, 2^{k - 1} + 5] & \dots & [2^{k - 2}, 2^k - 1] \\ [1, 2^{k - 1} + 2^{k - 2} + 1] & [2, 2^{k - 1} + 2^{k - 2} + 3] & [3, 2^{k - 1} + 2^{k - 2} + 5] & \dots & [2^{k - 3}, 2^k - 1] \\ \vdots & \vdots & \vdots & & \vdots \\ [1, 2^{k - 1} + 2^{k - 2} + \dots + 2 + 1] \end{matrix} \] We can verify that this arrangement contains all lengths of intervals from $1$ to $2^k - 1$ going from left to right, top to bottom. Moreover, no two intervals in the same row contain each other, and therefore any sequence of nested intervals contains at most $k$ of them (one from each row), as desired.

I am quite surprised how a problem based so heavily on the Dilworth's theorem appeared on IMO. I would expect only a small fraction of contestants to know it while it quite blatantly is of a great help here. If we create the relation between red circles if we can get from the higher to the lower one then it is clearly a poset and we are interested in the longest chain, which by Dilworth is equal to the minimum number of antichains needed to cover red circles. If an antichain has a red circle in k-th row then it contains at most k circles. From that we easily get inductively that first $c$ antichains cover at most $2^c-1$ circles and we are done (antichains are sorted by their first element).

The answer is $\boxed{k = \lfloor\log_2 n\rfloor+1}$. For convenience, define coordinate of a circle by $(r,i)$ where $r$ is the row ($1$ at the top, and $n$ at the bottom,) and $i$ is the order of the circle with in a row (from $1$ to $r$.) The construction is color the red circles with coordinates $(1,1), (2,1), (3,3), \hdots, (2^i,1), (2^i+1,3), \hdots (2^i+j, 2j+1), \hdots (2^{i+1}-1,2^{i+1}-1), \hdots$. Notice that for any $i$ such that $2^i > n$, any ninja paths can pass at most one circle in the row between $2^i$ and $2^{i+1}-1,$ inclusively. Hence, the number of red cells in the ninja paths are at most $m$ where $2^{m-1} \leq n <2^{m}$. Now we will prove that there is a ninja paths that passes through $k$ red circles. For each circle, label it with a positive integer $x$, the maximum number of red circles of the ninja paths from top of the japanese triangle to that circle. Claim. Suppoes that the circles in the $i$-th row are labeled with the number $x_1,x_2,\hdots, x_i$, then \[\sum_{j=1}^i 2^{-x_j} \leq 1- 2^{-\max\{x_1,x_2,\hdots,x_i\}}.\]The base case is obviously true because the only circle has a label $1$, the sum of the weight is $1-\frac{1}{2}\leq \frac{1}{2}$. Let the number labeled on circles on the $i-\text{th}$ row are $x_1,x_2,\hdots,x_i$, and those on the $i+1$-th row are $y_1,y_2,\hdots, y_{i+1}$. Define $M = \max\{x_1,x_2,\hdots,x_i\},\ N = \max\{y_1,y_2,\hdots,y_{i+1}\}$. At first, we will assume that there is NO red circles in the $(i+1)-\text{th}$ row, yet. Here, we will use the label $y'_j$ instead of $y_j$ for the circles on the $(i+1)-\text{th}$. In fact, we know that $y'_j = y_j$ for every circle but one that will be the red circle which will satisfy the relation $y'_j = y_j - 1$ because it add itself as the red circles in the path. Observe that $y'_1 = x_1,\ y'_i = x_i$, and $y'_j = \max\{x_{j-1},x_j\}$. Let $a$ be the index for which $x_a = M$. The idea is that the label on the $(i+1)-\text{th}$ row must be "at least" the label on the $i-\text{th}$ row. Hence, the desired sum should increase. [asy][asy] unitsize(20); defaultpen(fontsize(10pt)); string[] x={"$x_1$","$x_2$","$\cdots$","$x_{a-1}$","$M$","$x_{a+1}$","$\cdots$","$x_i$"}; string[] y={"$\geq x_1$","$\geq x_2$","$\cdots$","$\geq x_{a-1}$","$M$","$M$","$\geq x_{a+1}$","$\cdots$","$\geq x_i$"}; for (int i = 0; i < 8; ++i){ if ((i != 2) && (i != 6)) dot((2*i+1,1)); label((2*i+1,1),x[i],N); } for (int i = 0; i < 9; ++i){ label((2*i,0),y[i],S); if ((i == 2) || (i == 7)) continue; if (i < 5) draw((2*i+1,1)--(2*i,0),EndArrow(5)); else draw((2*i-1,1)--(2*i,0),EndArrow(5)); dot((2*i,0)); } [/asy][/asy] By induction hypothesis, \[\sum_{j=1}^{i+1} 2^{-y'_j} \leq \sum_{j=1}^{a} 2^{-x_j} + 2^{-M}+ \sum_{j=a+2}^{i} 2^{-x_{j-1}}\leq 1.\] However the sum we would like to compute has the red circle, which means that its actual label should be $y_i = y'_i+1$ since it counts that circle in the path as well. Hence, the actual sum must be $1 - 2^{-y_i} \leq 1 - 2^{-N}$ as desired. Now, on the last row, we can choose the cell labeled with $x_j$ such that $\frac{1}{2^{x_j}} < \frac{1}{n}\implies 2^{x_j} > n \geq 2^{k-1}$, implying the result. Otherwise, if we cannot choose such index $j$, then $\sum_{j=1}^n 2^{-x_j} \geq \frac{n}{n} = 1,$ contradiction.

Edit: This falls apart. Will fix soon Ok here is a solution which might have been found by many doing competitive programming. Let $f(i, j)$ be the max number of zeros collected starting from $j$th circle in $i$th row and continuing. Let $c_{ij} = 1$ is there is red circle at the corresponding position The recursion is $$f(i,j) = \max(f(i+1,j), f(i+1, j+1) + c_{ij}$$So its same as following game. We start with $n$ numbers $(a_1, a_2, \cdots a_n)$ initially all $0$. At a step we add $1$ to exactly one of the $a_i$ and the next sequence will be $(\max(a_1, a_2), \max(a_2, a_3) \cdots \max(a_{n-1}, a_n))$. Goal is to minimize the number obtained in the end. But now all we need to observe is that $\max(a_i)$ can't remain the same for more than $\lfloor n/2 \rfloor$ steps. This is because the max element keeps consuming the elements to left and right and hence when max is at extreme, at the next step, there will be two less elements who are strictly less than it. Hence there will be a $2$ after $\lfloor n/2 \rfloor$ steps, a $3$ after $\lfloor \lfloor n/2 \rfloor /2 \rfloor $ more steps and so on. This yields the required logarithmic bound. A greedy strategy of increasing the leftmost smallest element achieves the bound ($00000 \mapsto 1000 \mapsto 110 \mapsto 11 \mapsto 2$ etc)

I wonder, the problem is proposed from Japan. Because Ninjya is Japanese culture like Samurai, Bushi etc.

Kunihiko_Chikaya wrote: I wonder, the problem is proposed from Japan. Because Ninjya is Japanese culture like Samurai, Bushi etc. Perhaps the fact that this IMO was held in Japan had some connection with it ?

Need not be. Its in fact IMO's culture to have a problem with special word dedicated to the hosting country. For example, in some IMO hosted in Argentina, there was a problem mentioning "silver" squares, reference to the word "Argentum".

kapilpavase wrote: Ok here is a solution which might have been found by many doing competitive programming. Let $f(i, j)$ be the max number of zeros collected starting from $j$th circle in $i$th row and continuing. Let $c_{ij} = 1$ is there is red circle at the corresponding position The recursion is $$f(i,j) = \max(f(i+1,j), f(i+1, j+1) + c_{ij}$$So its same as following game. We start with $n$ numbers $(a_1, a_2, \cdots a_n)$ initially all $0$. At a step we add $1$ to exactly one of the $a_i$ and the next sequence will be $(\max(a_1, a_2), \max(a_2, a_3) \cdots \max(a_{n-1}, a_n))$. Goal is to minimize the number obtained in the end. But now all we need to observe is that $\max(a_i)$ can't remain the same for more than $\lfloor n/2 \rfloor$ steps. This is because the max element keeps consuming the elements to left and right and hence when max is at extreme, at the next step, there will be two less elements who are strictly less than it. Hence there will be a $2$ after $\lfloor n/2 \rfloor$ steps, a $3$ after $\lfloor \lfloor n/2 \rfloor /2 \rfloor $ more steps and so on. This yields the required logarithmic bound. A greedy strategy of increasing the leftmost smallest element achieves the bound ($00000 \mapsto 1000 \mapsto 110 \mapsto 11 \mapsto 2$ etc) As much as I would like this elegant solution to be correct, it does not seem to be . If the maximum value reaches one of the two ends then the number of non-maximums drops by only one instead of two per an iteration and the argument falls apart

It is just poorly written. The case you mentioned happens for even $n$ and we are fine $n = 4$ is $00000 \mapsto 1000 \mapsto 110 \mapsto 11 \mapsto 2$ so $1$ survived $4/2$ steps $n = 5$ is $000000 \mapsto 10000 \mapsto 1100 \mapsto 111 \mapsto 21$ so $1$ survived $\lfloor 5/2 \rfloor$ steps It just corresponds to the construction in one of the top posts (I am not in academia anymore so I take liberty to write handwavy arguments )

kapilpavase wrote: It is just poorly written. The case you mentioned happens for even $n$ and we are fine $n = 4$ is $00000 \mapsto 1000 \mapsto 110 \mapsto 11 \mapsto 2$ so $1$ survived $4/2$ steps $n = 5$ is $000000 \mapsto 10000 \mapsto 1100 \mapsto 111 \mapsto 21$ so $1$ survived $\lfloor 5/2 \rfloor$ steps It just corresponds to the construction in one of the top posts (I am not in academia anymore so I take liberty to write handwavy arguments ) Ok, I already understand the solution, but it has a pretty big writeup mistake. You want to claim that the $min(a_i)$ increases, not $max(a_i)$. You can't pull off the argument for max, but you can for min EDIT: Actually, I retract that. The argument does not work for min either

Ah you mean a case like $311 \mapsto 32 \mapsto 3$ right. My bad. It was an oversight. Thanks for catching it! I will rewrite the solution

Beautiful construction. I'd just like to highlight that wherever a path up to $2^j$ terminates, there's at least one red disk beneath it up to row $2\cdot 2^j$. The reason behind this is that removing the triangle under the terminal leaves two parallelograms with a total of fewer than $2^j$ rows. Note. After finding the construction, it should be obvious why $2^j\le n$ implies a ninja path with at least $j+1$ reds can always be found, and yet the idea I posted above is false. It's worth keeping track of the most reds that can be reached with a ninja path ending at the $i$-th position, $\rho_i$, where $i=1,2,\dots,n$. I claim that $\frac1{2^{\rho_1}}+\dots+\frac1{2^{\rho_n}}<1$, and I can prove this by induction. Going from $n$ to $n+1$, it's enough to see that the new values $\rho_1',\rho_2',\dots,\rho_n',\rho_{n+1}'$ are no smaller than either value over them, and so omitting any value in the sum, the sum remains less than one. In particular, the sum is at most $1-\frac1{2^{\rho'}}$, where $\rho'$ is the greatest of these values. This informs us that the sum is at most $1$, but equality cannot hold, as a new red has been placed.

Let's denote the circles as $(x,y)$ - the $y$th circle on the $x$th row, and let $f(x,y)$ denote the most red we can visit in a path finishing in $(x,y)$. We observe that adding a new row means that $f(x,y) = \max(f(x-1,y-1),f(x-1,y))$, and we need to find the smallest possible value of the largest number on the $n$th row. Claim: On row $2^z$, we have a circle with $f \geq z+1$, and the sum of all $f$ is at least $z \cdot 2^z + 1$. We will prove this by induction: Base: $n=1$ and $n=2$ $\Rightarrow$ OK Induction step: WLOG(let the largest $f$ on row $2^z$ be $(2^z,1)$). Adding $2^z$ rows means that $f(2^{z+1},i) = z+1$, where $i$ is from $1$ to $2^z+1$. (If $f(2^{z+1},i) \geq z+2$, then the induction is done.) The rest have a sum of at least $(z \cdot 2^z - z) + 2^z$ (We add $2^z$ because we have added that many rows, and each row we add, we increase the sum of a $f$ by $1$ because of a red circle). But by pigeonhole principle, we have $2^z-1$ numbers with a sum of $(z+1) \cdot 2^z - z = (z+1) \cdot (2^z-1) + 1$, which means at least one circle has $f \geq z+2$. Then, the sum of all the circles on row $2^{z+1}$ is at least $(z+1) \cdot (2^z-1) + 1 + (z+1) \cdot (2^z+1) = (z+1) \cdot 2^{z+1} + 1$, which satisfies the induction. Note: If we ever get $f \geq z+2$ earlier, then the same logic applies, and the sum still ends up $\geq (z+1) \cdot 2^{z+1} + 1$. This means for row $n$, we know the answer is $\geq \left\lfloor \log_2(n) \right\rfloor +1$. The example below shows that the answer can't be $\geq \left\lfloor \log_2(n) \right\rfloor +2$, so it's $\boxed{\left\lfloor \log_2(n) \right\rfloor + 1}$

Attachments:

Assign numbers to the circles as follows: The number in each circle is equal to the maximum number of red circles contained by some ninja path ending in it. First, some observations: Consider two consecutive circles in some row with labels $x,y$. Also consider the circle in the row beneath it which touches both these circles (let it be labeled $z$). It is easy to see that if $z$ is not red, $z =$ max$(x,y)$ (call this lemma 1) and if $z$ is red, $z =$ max$(x,y) + 1$. Note that in general, $z \geq x,y$ (call this lemma 2).. Let $S_i$ be the number of circles in the $i^{th}$ row. Claim 1: $S_{i+1} \geq S_i + $ (largest number in row i) $ + 1$ Proof: For simplicity's sake, let us first assume no circle in row i is red. Then we just want to prove $S_{i+1} \geq S_i + $ (largest number in row $i$). This is because the circle being red would have caused $S_{i+1}$ to increase by $1$. Note that in our simplified case, by lemma 1, the largest number in row $i + 1$ is equal to the largest number in row $i $. So our claim becomes $S_{i+1} \geq S_i + $ (largest number in row $i+1$). Now pick some circle in row $i+1$ that contains the largest circle in row $i+1$ and temporarily delete it. Now there are only $i $ circles in both rows $i$ and $i+1$. Label the numbers in them from left to right as $a_1,a_2, \ldots a_i$ and $b_1,b_2, \ldots b_i$ respectively. Clearly, for every $j $ from $1 $ to $i $, $b_j \geq a_j$ by lemma 2. So: $S_i = \sum_{j=1}^{i} a_j$ $S_{i+1} = \sum_{j=1}^{i} b_j + l$, where $l$ is the largest number in row $i+1$. $\Rightarrow S_i = \sum_{j=1}^{i} a_j \leq \sum_{j=1}^{i} b_j = S_{i+1} - l$ $\Rightarrow S_{i+1} \geq S_i + l$, which is what we wanted to show. (Actually $S_{i+1} \geq S_i + l + 1$.) Therefore Claim 1 is proven. Now we prove by induction that $k \geq \lfloor \log_2 n + 1 \rfloor$. For this we also prove that the sum of numbers in row $2^m \geq m \cdot 2^m + 1$. (Base cases $n = 1$ and $n = 2, m = 1$ are trivial.) Assume we have proven till $2^m $ for some $m$. So $\lfloor \log_2 2^m \rfloor = m+1$, and $($sum in row $2^m) \geq m \cdot 2^m + 1$. Also by our inductive assumption, the largest number in row $2^m$ is $\geq m +1$. So the largest number in each of the rows $2^m, 2^m +1 \ldots 2^{m+1} -1$ is $\geq m +1$. So we have: $S_{2^{m+1}} \geq S_{2^m} + 2^m \cdot$ (minimum increase per row, which is $m+2$ as shown by claim 1) $\geq m \cdot 2^m + 1 + 2^m \cdot (m+2)$ $ = 2^{m+1}\cdot(m+1) + 1$ (upon rearrangement) Number of circles in row $2^{m+1}$ = $2^{m+1}$ By strong PHP, at least one of the circles in row $2^{m+1}$ must have a number greater than or equal to $ \left \lceil \frac{2^{m+1}\cdot(m+1) + 1}{2^{m+1}} \right \rceil = m + 2$ Therefore, we have proven both parts by induction, till $2^{m+1}$. Now to prove that this value of $k$ is indeed our minimum, it suffices to give a construction where $k$ is exactly equal to $\lfloor \log_2 n + 1 \rfloor $, which is fairly easy. (To do this, we have to essentially make all the inequalities that we used hold strict equality.)

And yet another solution to this beautiful problem! Number the rows $0,1, \cdots , n-1$. Denote by $c_i$ the position of the red circle in the $i$th row. ($0\le c_i \le i$) Notice that we can get from a red circle $c_i$ to another one $c_j$ with $j>i$, if and only if $c_i-c_j\ge i-j$, that is if $i-c_i\ge j-c_j$. Let $y_i=i-c_i, 0\le y_i\le i$, we want to find $i_1<i_2<\cdots <i_k$ with $y_{i_1}\le \cdots \le y_{i_k}$. The problem becomes: > Let $(y_i)$ with $0\le i\le n-1$ be a sequence of integers such that $0\le y_i\le i$ (we'll call such a sequence a beautiful sequence of rank $n$). Find the maximal $k$ such that there must exists a nondecreasing subsequence of $y_i$ of size at least $k$. We omit the upper bound since it is similar to the other posts. As for the lower bound, we only need to prove it for powers of $2$, that is if we are given a beautiful sequence of rank $2^i$ then it must contain a nondecreasing subsequence of size $i+1$. We can argue this by induction. The case $n=1$ is trivial. Suppose we know the result for all smaller $<n$, and suppose for the sake of contradiction that there is a counterexample for $n$ The main claim is that for every $0\le i\le n-1$ every number $a \in [2^i, 2^{i+1}-1]$ must appear in the sequence for at most $n-i-1$ times. Otherwise, we can form an non-decreasing subsequence of length $n+1$ by taking a non-decreasing subsequence of length $i+1$ in $[0,2^i-1]$ followed by all occurrence of $a$ Summing the number of appearance over all such $a$, we conclude that the number of non-zero terms in the sequence is at most $\sum_{i = 0}^{n - 1} (n - i - 1) \cdot 2^i = \sum_{j = 0}^{n - 2} \sum_{i = 0}^j 2^i = \sum_{j = 0}^{n - 2} (2^{j + 1} - 1) = 2^n - n - 1.$ However, this means that $0$ must appear at least $n+1$ times, so all occurrence of $0$ forms a non-decreasing subsequence, contradiction. Source: https://math.stackexchange.com/questions/4752434/maximal-non-decreasing-subsequence

It is a stronger version of this problem.

\begin{align*} \MoveEqLeft \sum_{j=1}^{i+1} 2^{a_{i+1,j}} -\sum_{j=1}^{i} 2^{\max\{a_{i+1,j}, a_{i+1,j+1}\}} \\ &= \begin{multlined}[t] \left(i+1+\sum_{b=1}^\infty 2^{b-1} \lvert \{ j : a_{i+1,j} \geq b\}\rvert\right) \\ - \left(i+\sum_{b=1}^\infty 2^{b-1} \lvert \{ j : \max\{a_{i+1,j}, a_{i+1,j+1}\} \geq b\}\rvert\right)\end{multlined} \\ & = 1 + \sum_{b=1}^\infty 2^{b-1} (1+\lvert \{ j :\max\{a_{i+1,j}, a_{i+1,j+1}\} < b\}\rvert- \lvert \{ j : a_{i+1,j} < b\}\rvert) \\ &\leq 1 + \sum_{b = 1}^{\min_j \{a_{i+1,j}\}} 2^{b-1} \\ &= 2^{\min_j \{a_{i+1,j}\}}. \end{align*}

Who is the proposer?

Cool problem! Posting for storage... The answer is $k = \lfloor \log_2 n \rfloor + 1$. Examples showing this bound is tight is suggested in solutions like #8 already, so I'll only prove that there is ninja path pass through at least $k = \lfloor \log_2 n \rfloor + 1$ circles. It's sufficient to show that for $2^k\leq n< 2^{k+1}$, there is ninja path containing at least $k+1$ red circles. Let's prove it by induction. Level the rows $1$ to $n$ from top to bottom. Pick one red circle $C$, and define it's good ninja path as ninja path starting at top red circle and ends at $C$. Let length of $C$ as maximum number of red circles in ninja path among all good ninja paths of it. Claim. Number of length $t$ red circle is at most $2^{t-1}$ for all $1\leq t\leq k$. Proof. For $t=1$ it's obvious because only top red circle has length $1$. For $t\geq 2$, by induction there is red circle $C_0$ such that it's row number is at most $2^{t-1}$ and length is at least $t$(think row $1, ..., 2^{t-1}$). Let it's row number $s$, and in row $s$, there is $x$, $y$ circles in left/right side of $C_0$. Think about subtriangle such that top circle is $C_0$. And define $P_0$ the good ninja path of $C_0$ containing at least $t$ red circles. For each red circles in subtriangle different from $C_0$, think about ninja path from $C_0$ and ends at it. Combining this with $P_0$, we get good ninja path containing at least $t+1$ red circles. This means there is no red circles of length $t$ in subtriangle, other than $C_0$. Furthermore, think about $x$ leftmost rows parallel to left side of original triangle(we call it left rows), and $y$ rightmost rows parallel to right side of original triangle(we call it right rows). Since length $t$ red circle different from $C_0$ is in left row or right row, number of length $t$ red circle is at most $|($length t red circles in left rows$)|+|($length t red circles in right rows$)|+1$(as $C_0$ can be length $t$). But no two length $t$ red circles is in same left or right row, since it does, lower circle has length at least $t+1$(think good ninja path connects top red circle, upper circle, lower circle). So each left/right rows has at most $1$ length $t$ red circle. So number of length $t$ red circle is at most $x+y+1=(s-1)+1=s\leq 2^{t-1}$. So claim is proved. By claim, number of length $\leq k$ red circle is at most $2^0+2^1+...+2^{k-1}=2^k-1$. It is less than $n$ and since there is $n$ red circles, there must be red circle $C_1$ with length at least $k+1$. Pick good ninja path ends at $C_1$ and has at least $k+1$ red circles, we're done!!

Fibonacci_11235 wrote: Who is the proposer? Merlijn Staps.

Answer: $\lceil\log_2(n+1)\rceil$. Construction is same as others have done above. Now we prove the lower bound. Motivation is ISL 2019/C9 which uses the same function. For $1 \leq j \leq i \leq n$, let $a_{i,j}$ be the maximum number of red circles in any path starting from the top of the triangle and ends at the $j$th circle in the $i$th row. Claim. For every positive integer $n$, we have $\sum_{i=1}^n 2^{-a_{n,i}}<1$. Proof. By induction on $n$. The base case $n=1$ is true since $a_{1,1}=1$ so $2^{-a_{1,1}}=\frac{1}{2}<1$. For the induction step, assume the statement is true for $n$ and we will prove it for $n+1$. Observe that we have $$a_{n+1,i}=\max\{a_{n,i},a_{n,i-1}\}+r_{n+1,i},$$where $a_{n,0}=a_{n,n+1}=0$ and $r_{n+1,i}=1$ if the $i$-th ball in the $n+1$-th row is colored red, and $r_{n+1,i}=0$ otherwise. Let $p\in[1,n]$ such that $a_{n,p}=\max_{1\le i\le n}a_{n,i}$. Hence $\sum_{i=1}^n 2^{-a_{n,i}}\le 1-2^{-a_{n,p}}$. Since one of $r_{n+1,i}$ is strictly positive, we have: \begin{align*} \sum_{i=1}^{n+1}2^{-a_{n+1,i}}&\le\sum_{i=1}^p 2^{-a_{n,i}-r_{n+1,i}}+\sum_{i=p+1}^{n+1}2^{-a_{n,i-1}-r_{n+1,i}}\\ &<\sum_{i=1}^p 2^{-a_{n,i}}+\sum_{i=p+1}^{n+1}2^{-a_{n,i-1}}\\ &=\sum_{i=1}^n 2^{-a_{n,i}}+2^{-a_{n,p}}\\ &\le 1. \end{align*} This proves the induction step. $\square$ Now to prove the bound, let $n$ be a positive integer and let $M=\max_{1\le i\le n} a_{n,i}$. Then $$1>\sum_{i=1}^n 2^{-a_{n,i}}\ge\sum_{i=1}^n 2^{-M}= n 2^{-M}.$$Hence $2^M>n$ so $2^M\ge n+1$ and $M\ge\lceil\log_2(n+1)\rceil$.

We uploaded our solution https://calimath.org/pdf/IMO2023-5.pdf on youtube https://youtu.be/tL6-102WzmM.

Cali.Math wrote: We uploaded our solution https://calimath.org/pdf/IMO2023-5.pdf on youtube https://youtu.be/tL6-102WzmM. Great video! If you are planning on making a video going over probabilistic methods could you cover some of the topics involving variance as used in CTST 2023?

old sol uploaded now. We claim that $k = \left\lfloor \log_2(n) \right\rfloor$. Claim: This can be constructed. Proof. Disect the rows of the triangle into collections of rows $[2^k, 2^{k+1} - 1]$. Then for each collection, space the red circles such that the adjacent rows have elements spaced two apart. Then any ninja path only contains at most one element from each collection. $\blacksquare$ Claim: If $n = 2^a$, then some ninja path has $k$ elements. Proof. Add an $n+1$st row of just white circles. We write a number in each circle as follows, first writing a zero in each circle of the newly added row. Then for all other circles, write the maximum of the two circles below it, adding $1$ if this circle is also red. It remains to show that the top circle's number is at least $\left\lfloor \log_2(n) \right\rfloor$. Define $R_k$ as the multiset of $k$ numbers in the $k$th row. Order multisets $a_k \ge a_{k-1} \ge \dots \ge a_2 \ge a_1$ based off the ordinal $a_k \omega^k + a_{k-1} \omega^{k-1} + \dots + a_1 \omega$. We can model this by taking the following process: Start out with $C_{n+1}$ with $n+1$ zeros. Then to get $C_k$ from $C_{k+1}$, add $1$ to some element of $C_{k+1}$ then discard the smallest element of $C_k$. We can check that $R_k \ge C_k$ inductively for some process generating some $C_k$. It thus remains to show that $C_1$ contains an element at least $a$ than $C_n$ or $C_{2^a}$. We prove this inductively. Note that if we consider a processes starting at $C_k$ have the same number of elements, and some other $C_k' < C_k$ with the same sum, then there exists a process starting from $C_k$ that can be mimiced from $C_k'$ such that $C_i \ge C_i'$ for all $i = k-1, k-2, \dots, 1$. It then follows that we can WLOG assume that the process means that for $2^{a-1} \le i \le 2^a = n$, that $C_i$ consists of $2^a - i$ ones and $2i - 2^a$ zeros. Notably, it follows that $C_{2^{a-1}}$ is just $2^{a-1}$ ones. Inductively, the maximum element of $C_1$ is at least $a-1$ more than the maximum element of $C_{2^{a-1}}$, which finishes. $\blacksquare$

My solution is similar to many above so I won't post it but my motivation looks way too different, since I focused on $f(c)$ where $c$ is a circle in a japanese triangle to be a function that computes the maximal number of red circles that can be on a ninja path passing through $c$ in a scenario where the the given japanese triangle is meant to minimise $max(f)$ over the $i$-th row. You observe that the value of $f$ kind of "propagates" and increases by $1$ unescapably at rows $i=2^{t}$. From which follows a construction for an upper bound.

Good problem. Define a red circle to cover a target circle if a ninja path exists from the red circle to the target circle. Define a level to be a set of red circles that cover all red circles excluding themselves and any red circles that cover one of them. Note that a ninja path can pass through at most one red circle in a level, as no red circle in a level covers another red circle. Lemma: if a level contains a red circle on row $i$, then it contains at most $i$ red circles. Proof: In order to not cover each other, each red circle in the level must inhabit a unique diagonal not covered by the red circle on row $i$. There are only $i-1$ diagonals left, so there can only be $i-1$ additional red circles in the level. Claim: for a Japanese triangle of size $n$, we can partition the red circles into at least $\lfloor \log_2n\rfloor +1$ disjoint levels. Proof: First, we show a partition exists. We iteratively construct each level by taking the highest uncategorized red circle, and adding uncategorized red circles not covered by this level to the level as we move down the rows until there are none left to add. [asy][asy] size(7cm); pair X = dir(240); pair Y = dir(0); path c = scale(0.5)*unitcircle; int[] t = {0,1,1,3,0,3,0}; pen[] color = {lightred, lightgreen, lightblue, lightblue, lightgreen, orange, lightblue}; for (int i=0; i<=6; ++i) { for (int j=0; j<=i; ++j) { filldraw(shift(i*X+j*Y)*c, (t[i]==j) ? color[i] : white); draw(shift(i*X+j*Y)*c); } } draw((0,0)--(X+Y)--(2*X+Y)--(3*X+2*Y)--(4*X+2*Y)--(5*X+3*Y)--(6*X+3*Y),linewidth(1.5)); label("Level 0", (5, 0), p=red); label("Level 1", (5, 0) + X+Y*0.5, p=green); label("Level 2", (5, 0) + 2*X+Y, p=blue); label("Level 3", (5, 0) + 5*X+Y*2.5, p=orange); [/asy][/asy] Next we show that we can create at least $\lfloor \log_2n\rfloor +1$ disjoint levels. Label the levels as $0, 1, 2, \ldots$ ordered by their highest row. I claim level $k$ must start at row $2^k$ or higher. This can be seen inductively, as level $0$ starts unambiguously at row $2^0=1$, and if we assume level $k-1$ starts on row $r \le 2^{k-1}$, then by our lemma it can at best contain the next $r\le 2^{k-1}$ rows, leaving row $2r\le 2^k$ for level $k$ to claim. What this means for us is that when $n=2^k$, we must create a new level $k$ netting $k+1$ levels total. This solves to $\lfloor \log_2n\rfloor +1$ levels total. To finish off the proof, note that each level $i$, by definition, covers level $i+1$. Thus, for any red circle in level $i+1$, there exists a red circle in level $i$ that covers it; a.k.a there exists a ninja path starting at level $0$ that passes through one red circle from each level, for a total of $\lfloor \log_2n\rfloor +1$ red circles. Equality can be constructed by any setup where level $k$ contains red circles from rows $2^k, \ldots, 2^{k+1}-1$. Many examples have been given above.

The answer is $k = \lfloor \log_2 n \rfloor + 1$ red circles. The main idea is the following. For each circle in position $j$ of row $i$ (from now on we denote by $(i, j)$), define $g(i, j)$ to be the maximum number of red circles a ninja path terminating at $(i, j)$ may contain. In particular, $g(i, j) = \operatorname{max}(g(i-1, j-1), g(i-1, j))$ if $(i, j)$ is colored white, and $g(i, j) = \operatorname{max}(g(i-1, j-1), g(i-1, j)) + 1$ if $(i, j)$ is colored red. By convention, $g(i, j) = 0$ for $j = 0$ or $j = i+1$. Construction: In row $2^k + r$ for $ 0\leq r < 2^k$, color circle $\left(2^k+r, 2r+1\right)$ red. Calculating the values of $g(i, j)$ shows that $g(i, j) \leq k+1$ for row $2^k+r$. Bound: The bound is a delicious induction argument. For each $k$, let $f(k)$ denote the minimum positive integer $n$ such that in any Japanese triangle with $n$ rows, there exists a ninja path through at least $k$ red circles. The construction implies that $f(k) \geq 2^{k-1}$ for each $k$. I contend: Claim: In any Japanese triangle with $n= f(k)$ rows, the sum of $g(n, j)$ for all $1 \leq j \leq n$ is at least $n(k-1) + 1$. Proof: We prove the first claim by induction on $k$, with the base case $k=2$ clear. Consider any Japanese triangle with $2n$ rows, and let $S(n)$ denote the sum of $g(n, j)$ for all $1 \leq j \leq n$. For all $m \geq f(k)$, I claim that the inequality $S(m+1) \geq S(m) + k + 1$ holds. To see this, let $j$ be the maximal index such that $g(m, j) \geq k$. Then, before picking a red circle, $g(m+1, \ell) \geq g(m, \ell)$ for all $\ell \leq j$, $g(m+1, \ell+1) \geq g(m, \ell)$ for all $\ell > j$. Therefore \begin{align*} S(m+1) - S(m) &= \sum_{\ell=1}^j \left(g(m+1, \ell) - g(m, \ell)\right) + g(m+1, \ell + 1) + \sum_{\ell = j+1}^m \left(g(m+1, \ell + 1) - g(m, \ell)\right)\\ &\geq k + 1 \end{align*}because $g(m+1, \ell + 1) \geq k$ and $S$ increases by exactly one when we color a red circle. Thus, \[S(2n) \geq S(n) + n(k+1) = 2nk + 1. \ \ (*)\]So in any Japanese triangle with $2n$ rows, there exists a $g(2n, j) \geq k + 1$; so in fact, $f(k+1) \leq 2f(k)$ for every positive integer $k$. Because $f(2) = 2$ and $f(k) \geq 2^{k-1}$, it follows that $f(k) = 2^{k-1}$ precisely; thus in fact $f(k+1) = 2f(k)$, so $(*)$ reads the induction hypothesis for $f(k+1)$. The claim follows. $\blacksquare$ It is evident that the claim also solves the problem, so we are done. Remark: The induction argument in the bound proof is an example of strengthening the inductive hypothesis; but unlike most examples, it makes no explicit reference to what the size of $f(k+1)$ should be. In a sense, we take an inductive step into nowhere by picking $2n$, then realize that the inductive hypothesis itself proves to us that we have indeed landed at $f(k+1)$. Really cool stuff.

numbersandnumbers wrote: The answer is $k = \lfloor \log_2 n \rfloor + 1$. To prove that one can't do better, note that it suffices to find a construction for $n = 2^m-1$ that has no path with more than $m$ circles. This is doable by placing the red cells "diagonally" such that no path intersects more than one red cell in rows $1$, $2$, $3$ through $4$, ..., $2^{m-1}$ to $2^m - 1$. An example with $m = 4$ is shown below: [asy][asy] unitsize(5mm); for (int i = 1; i < 2; ++i) { int j = 2*(i-1); fill(shift(i*dir(240)+j*dir(0))*scale(0.5)*unitcircle,lightred); } for (int i = 2; i < 4; ++i) { int j = 2*(i-2); fill(shift(i*dir(240)+j*dir(0))*scale(0.5)*unitcircle,lightred); } for (int i = 4; i < 8; ++i) { int j = 2*(i-4); fill(shift(i*dir(240)+j*dir(0))*scale(0.5)*unitcircle,lightred); } for (int i = 8; i < 16; ++i) { int j = 2*(i-8); fill(shift(i*dir(240)+j*dir(0))*scale(0.5)*unitcircle,lightred); } for (int i = 1; i < 16; ++i) { for (int j = 0; j < i; ++j) { draw(shift(i*dir(240)+j*dir(0))*scale(0.5)*unitcircle); } } [/asy][/asy] Now we show that $k = \lfloor \log_2 n \rfloor + 1$ is always achievable. To do this, for $1 \leq j \leq i \leq n$, let $a_{i,j}$ be the maximum number of red circles in any path starting from the $j$th circle in the $i$th row and going to the bottom of the triangle. We have the recurrence \[a_{i,j} = \max\{a_{i+1,j}, a_{i+1,j+1}\} + \begin{cases*} 1 & the $j$th circle in the $i$th row is colored \\ 0 & else \end{cases*}\]and we wish to show that $a_{1,1} \geq \lfloor \log_2 n\rfloor + 1$. To do this, our main claim is that \[\sum_{j=1}^{i} 2^{a_{i,j}} \geq \sum_{j=1}^{i+1} 2^{a_{i+1,j}}\]for all $i$. This will finish, since we can compute that $\sum_{j=1}^{n} 2^{a_{n,j}} = n+1$, and chaining together these inequalities shows that $2^{a_{1,1}} \geq n+ 1$. To prove the inequality, pick a specific $i$. For a given $b$, the number of $j$ with $a_{i+1,j} < b$ is strictly greater than the number of $j$ with $\max\{a_{i+1,j}, a_{i+1,j+1}\} < b$, unless the former quantity is zero. Therefore \begin{align*} \MoveEqLeft \sum_{j=1}^{i+1} 2^{a_{i+1,j}} -\sum_{j=1}^{i} 2^{\max\{a_{i+1,j}, a_{i+1,j+1}\}} \\ &= \begin{multlined}[t] \left(i+1+\sum_{b=1}^\infty 2^{b-1} \lvert \{ j : a_{i+1,j} \geq b\}\rvert\right) \\ - \left(i+\sum_{b=1}^\infty 2^{b-1} \lvert \{ j : \max\{a_{i+1,j}, a_{i+1,j+1}\} \geq b\}\rvert\right)\end{multlined} \\ & = 1 + \sum_{b=1}^\infty 2^{b-1} (1+\lvert \{ j :\max\{a_{i+1,j}, a_{i+1,j+1}\} < b\}\rvert- \lvert \{ j : a_{i+1,j} < b\}\rvert) \\ &\leq 1 + \sum_{b = 1}^{\min_j \{a_{i+1,j}\}} 2^{b-1} \\ &= 2^{\min_j \{a_{i+1,j}\}}. \end{align*}On the other hand, if $j^*$ is the location of the colored circle in row $i$, \[ \sum_{j=1}^{i} 2^{a_{i,j}} -\sum_{j=1}^{i} 2^{\max\{a_{i+1,j}, a_{i+1,j+1}\}} = 2^{\max\{a_{i+1,j^*}, a_{i+1,j^*+1}\}} \geq 2^{\min_j \{a_{i+1,j}\}}.\]Subtracting these two inequalities yields the claim. crazy LaTeX