Japanese Triangles

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

297 posts

#1 h Jul 9, 2023, 4:56 AM • 17 Y

Y by Loppukilpailija, OronSH, GeoKing, Aopamy, Aops_2000, FourthRootOfX, kingu, ihatemath123, mathmax12, stayhomedomath, Supercali, DiaaSaid, Tastymooncake2, Sedro, vinyx, idkk, Rounak_iitr

Let $n$ be a positive integer. A Japanese triangle consists of $1 + 2 + \dots + n$ circles arranged in an equilateral triangular shape such that for each $i = 1$ , $2$ , $\dots$ , $n$ , the $i^{th}$ row contains exactly $i$ circles, exactly one of which is coloured 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. Here is an example of a Japanese triangle with $n = 6$ , along with a ninja path in that triangle containing two red circles.
$[asy] // credit to vEnhance for the diagram (which was better than my original asy): size(4cm); pair X = dir(240); pair Y = dir(0); path c = scale(0.5)*unitcircle; int[] t = {0,0,2,2,3,0}; for (int i=0; i<=5; ++i) { for (int j=0; j<=i; ++j) { filldraw(shift(i*X+j*Y)*c, (t[i]==j) ? lightred : 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+2*Y),linewidth(1.5)); path q = (3,-3sqrt(3))--(-3,-3sqrt(3)); draw(q,Arrows(TeXHead, 1)); label("$n = 6$", q, S); label("$n = 6$", q, S); [/asy]$
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.

This post has been edited 15 times. Last edited by pikapika007, Jun 7, 2024, 2:59 PM
Reason: credit to vEnhance for the diagram

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MS_Kekas

275 posts

MS_Kekas

#2 h Jul 9, 2023, 5:27 AM • 11 Y

Y by BlazingMuddy, Sumgato, TheStrayCat, GeoKing, Infinityfun, khina, ihatemath123, Snark_Graphique, Sedro, Tastymooncake2, kzguyfromd

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7326 posts

DottedCaculator

#6 h Jul 9, 2023, 5:39 AM

Y by

The answer is log2(n)+1.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Hyperabola

6 posts

Hyperabola

#7 h Jul 9, 2023, 5:43 AM • 2 Y

Y by eternity_maganize, GeoKing

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

Quite interesing.

This post has been edited 1 time. Last edited by Hyperabola, Jul 9, 2023, 5:44 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

numbersandnumbers

258 posts

numbersandnumbers

#8 h Jul 9, 2023, 5:44 AM • 7 Y

Y by eternity_maganize, GeoKing, xyz_g, jestrada, sabkx, c7h5n3o6_tnt, poirasss

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] 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]$

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.

This post has been edited 3 times. Last edited by numbersandnumbers, Jul 9, 2023, 7:05 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

khina

993 posts

khina

#9 h Jul 9, 2023, 6:02 AM • 2 Y

Y by everythingpi3141592, Simona_AlphaMusic

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.

This post has been edited 2 times. Last edited by khina, Jul 9, 2023, 6:06 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rtyu852

6 posts

rtyu852

#10 h Jul 9, 2023, 6:30 AM • 12 Y

Y by khina, Cty-circle, Supercali, Nguyenhuyhoang, everythingpi3141592, Aopamy, GeoKing, Gato_combinatorio, sabkx, CBMaster, DiaaSaid, cheesegrater12121

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

juckter

322 posts

juckter

#11 h Jul 9, 2023, 6:37 AM • 1 Y

Y by Liuzhiyuan

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.

This post has been edited 3 times. Last edited by juckter, Jul 9, 2023, 6:40 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Swistak

180 posts

Swistak

#12 h Jul 9, 2023, 11:09 AM • 5 Y

Y by carefully, gvole, GeoKing, Skywalker_v, mathleticguyyy

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).

This post has been edited 1 time. Last edited by Swistak, Jul 9, 2023, 12:43 PM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

psi241

49 posts

psi241

#13 h Jul 9, 2023, 12:31 PM • 2 Y

Y by MarkBcc168, GeoKing

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] 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]$
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.

This post has been edited 3 times. Last edited by psi241, Dec 16, 2023, 5:21 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kapilpavase

595 posts

kapilpavase

#14 h Jul 9, 2023, 12:32 PM

Y by

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)

This post has been edited 3 times. Last edited by kapilpavase, Jul 9, 2023, 2:38 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kunihiko_Chikaya

14512 posts

Kunihiko_Chikaya

#15 h Jul 9, 2023, 12:52 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Swistak

180 posts

Swistak

#16 h Jul 9, 2023, 12:56 PM • 4 Y

Y by Kunihiko_Chikaya, ostriches88, carefully, Dhruv777

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

?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kapilpavase

595 posts

kapilpavase

#17 h Jul 9, 2023, 12:56 PM

Y by

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".

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Swistak

180 posts

Swistak

#18 h Jul 9, 2023, 12:59 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZNatox

67 posts

ZNatox

#61 h Aug 16, 2023, 12:02 PM

Y by

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

This post has been edited 2 times. Last edited by ZNatox, Aug 17, 2023, 12:53 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math90

1474 posts

math90

#62 h Sep 12, 2023, 5:17 PM • 1 Y

Y by CT17

It is a stronger version of this problem.

This post has been edited 4 times. Last edited by math90, Sep 12, 2023, 5:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Joider

136 posts

Joider

#63 h Sep 15, 2023, 5:11 AM

Y by

$\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*}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Fibonacci_11235

43 posts

Fibonacci_11235

#66 h Dec 25, 2023, 9:25 PM

Y by

Who is the proposer?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CBMaster

85 posts

CBMaster

#67 h Apr 29, 2024, 3:27 AM

Y by

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!!

This post has been edited 12 times. Last edited by CBMaster, Apr 29, 2024, 5:52 AM
Reason: .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Phorphyrion

395 posts

Phorphyrion

#68 h Apr 29, 2024, 8:37 AM

Y by

Fibonacci_11235 wrote:

Who is the proposer?

Merlijn Staps.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math90

1474 posts

math90

#69 h Apr 29, 2024, 11:17 AM

Y by

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$ .

This post has been edited 8 times. Last edited by math90, May 10, 2024, 7:03 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Cali.Math

128 posts

Cali.Math

#70 h May 24, 2024, 7:05 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sami1618

881 posts

sami1618

#71 h May 26, 2024, 12:12 AM

Y by

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

YaoAOPS

1501 posts

YaoAOPS

#72 h Jun 7, 2024, 2:52 AM • 1 Y

Y by GeoKing

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alba_tross1867

44 posts

alba_tross1867

#74 h Aug 8, 2024, 7:40 PM

Y by

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.

This post has been edited 1 time. Last edited by alba_tross1867, Aug 8, 2024, 7:41 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bobthesmartypants

4337 posts

bobthesmartypants

#75 h Sep 22, 2024, 12:29 AM

Y by

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] 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]$

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8857 posts

HamstPan38825

#76 h Dec 11, 2024, 4:11 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lksb

164 posts

lksb

#77 h Dec 18, 2024, 12:45 AM

Y by

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] 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]$

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

quantam13

108 posts

quantam13

#78 h Apr 2, 2025, 10:48 AM

Y by

Amazing problem! I got quite a few solutions, but my favorite one is the following: Create a binary tree on the red circles in the obvious manner. Each vertex has atmost 2 children so the depth of the tree is atleast $1+\lfloor \log_2n\rfloor$ !! :cool:

Z K Y