A circus act consists of $2024$ bamboo sticks of pairwise different heights placed in some order, with a monkey standing atop one of them. The circus master can then give commands to the monkey as follows: ___$\bullet$ Left! : When given this command, the monkey locates the closest bamboo stick to the left taller than the one it is currently atop, and jumps to it. If there is no such stick, the monkey stays put. ___$\bullet$ Right! : When given this command, the monkey locates the closest bamboo stick to the right taller than the one it is currently atop, and jumps to it. If there is no such stick, the monkey stays put. The circus master claims that given any two bamboo sticks, if the monkey is originally atop the shorter stick, then after giving at most $c$ commands he can reposition the monkey atop the taller stick. What is the smallest possible value of $c$? Proposed by Archit Manas
Problem
Source: LMAO 2024 P2
Tags: combinatorics, lmao
01.06.2024 22:15
Redacted! @below got it, I misunderstood the problem.
01.06.2024 22:23
szpolska wrote: I think the answer should be 2023. I will post the proof if the answer is correct. No, it's pretty far from the answer. You probably have misunderstood the question. You need to find the smallest $c$ for which there is some configuration of sticks so that the circusmaster's claim can be valid. Also, the sticks are on a line. @above, no your claim is not correct, for example for 3 sticks, $2,1,3$ is a valid ordering of the sticks
02.06.2024 02:41
02.06.2024 09:40
@above unfortunately that is not close to the answer
02.06.2024 15:22
@below Indeed, you are right, will edit my proof.
02.06.2024 16:25
Consider n = 3 and the arrangement of sticks as 5, 4, 1, 2, 3, 6. c=2 works for this construction. @above
02.06.2024 22:44
Okay no forget what i said it is totally wrong.
02.06.2024 23:05
The answer is 63 @above.
02.06.2024 23:27
Okay, thanks.
03.06.2024 16:53
May be the last problem before CEE Very cute problem! Just imagine you are in the fairyland. A train passed by. At first, there is only one carriage where passenger $1$ sits. At the second station waits passenger $2$. He can only creates his own carriage at the headstock or the tailstock. It goes all the same at the station $3,4,\cdots,2024$. If $m$ forces a new carriage between two neighbours, their communication will be blocked by $m$. Now let's calculate the longest communication distance from $1$. Denote the train $0$ be the carriage $1$. Given train $i$, $i\ge 0$, the carriage in front of its headstock is $m$ and the one behind its tailstock is $n$. WLOG let $m\ge n$, then the train $(i+1)$ is $\{ m, train i, n, n+1, \cdots, m-1 \}$. Then we get a train sequence $0,1,\cdots, t$. Each step, if in the train $i$, we can get to train $(i+1)$ or stay at train $i$. So when we get to the train $0,1,\cdots, t$, the steps remained are at most $c,c-1,\cdots,1$ respectively. So the train $i$ has at most new $(c+1-i)$ carriages. Therefore, the number of carriages is not bigger than $1+2+3+\cdots +(c+1)=\frac{(c+1)(c+2)}{2}$, which boils down to the answer $63$. The construction is just like the construction of train $0$ to train $(c-1)$.
03.06.2024 17:47
In general, for $n$ sticks, the minimal $c$ is $c = \lceil k \rceil$. Where $k$ is the solution to the $\frac{k(k+3)}{2}= n$ (You can use the quadratic formula). For $n = 2024$, this gives an answer of $c = 63$ (Note before reading : I heavily used the word 'numbers' in the proof, which can lead to confusion, this simply corresponds to the sticks with labeled heights Label the sticks $S_1, S_2, \ldots S_{2n}$ and suppose without lost of generality that $S_i$ has height $i$. We first deduce some properties about the circus master configuration : Property 1 : If between two sticks $S_i, S_j$, there is a stick $S_n$ then $n \leq \max\{i,j\}$ Suppose by contradiction that there exists a stick that contradicts this property, and let $S_m$ be the tallest one contradicting the property and WLOG that $i \leq j$ When performing the moves to go from $S_i$ to $S_j$, the monkey will have to pass by $S_m$, but cannot go back to $S_j$ since it is taller than it, a contradiction to the circus master claim. Property 2 : Let $i \neq 1$, suppose $S_i$ and $S_1$ are not adjacent, then the sticks between $S_1$ and $S_i$ have strictly increasing height. (The stick closest to $S_1$ is the smallest one and the one closest to $S_i$ is the biggest one) If there $0$ or $1$ stick between the two there is nothing to prove. Suppose by contradiction that there exists two sticks $S_n, S_m$, such that $S_n$is closest to $S_1$ than $S_m$ but that $S_n$ is taller than $S_m$, then there exists a stick $S_m$ between $S_1, S_n$ such that $m \geq \max\{1,n\} = n$, a contradiction to property 1. Claim 1 : $c \geq \lceil k \rceil$ We will show that we need such a valid of $c$ for the monkey to cover all the numbers. Here's the idea: At the first move, starting from $S_1$, the monkey can reach exactly two sticks, we will show that at the second move, the monkey can reach three new sticks, and in general at the $i - 1$ moves, that he can reach at most $i$ new sticks. We will prove this by induction, the case from $S_1$ to the two new sticks is clear. Suppose this was true as the $i-1$ move, we prove this for the $i $ move. Suppose the monkey is on the left of $S_1$ and is not on the left-most of the $i$ sticks, then jumping left will lead him to get on one of the $i$ possible sticks (call it $S_v$), else, the monkey will jump on another stick $S_u$ such that $u \leq v$ (This is true, because of Property 2, recall that the sticks are in increasing order, but then going a step back, the monkey needed to reach $S_u$ first before reaching $S_v$, which is a contradiction. Do the same for the left. So each stick, except the right-most and left-most of the $i$ sticks can only reach one new stick. Now consider the closest two of the $i$ sticks to $S_1$, and call the one with maximal value out of the two $S_u$ and suppose it is on the left. Then one of the sticks on the right when jumping to the left, will reach $S_u$, else, they all have heights superior to $S_u$, which contradicts the maximality argument (Since for example, just the closest on the right have shorter height that $S_u$). Thus this decreases our possible moves by $1$. So, summarizing, each of the $i - 2$ sticks (not on the extremities), can get $1$ move, the extremities can get at most $2$, and we removed $1$, hence $i - 2 + 2\times 2 - 1=i +1$ as wanted. Hence at the $k$ move, the monkey has been able to reach $2 + 3 + \ldots + (k+1)= \frac{(k+3)(k)}{2}$ But he needs to reach a total of $n - 1$ numbers ($0$th move is also counted). Thus $\frac{(k+3)(k)}{2} \geq n $. Thus the minimal possible $c$ (We have not given the construction just yet) satisfying this inequality is $\lceil k \rceil$. where $k$ is the solution to $\frac{(k+3)(k)}{2} = n $ The Construction First, solve the equation for any case you want to get the value of $\lceil k \rceil$ The construction is as follow : Put the shortest stick $S_1$ first, and append to its left (In increasing order, respecting Property 2) the first $\lceil k \rceil$ shortest sticks which are taller than $S_1$, then to the right, append $S_{\lceil k \rceil + 2}$, in a second step append to the left the next $\lceil k \rceil - 1$ shortest sticks taller than $S_{\lceil k \rceil + 2}$, then append to the right $S_{2\lceil k \rceil + 2}$, in a third step append to the left the next $\lceil k \rceil - 3$ shortest sticks taller than $S_{2\lceil k \rceil + 2}$, then append to the right $S_{3\lceil k \rceil + 1}$, and do this inductively until no number is left. Proof that it works : We call those $\lceil k \rceil - i$ arrangements of numbers to the left a station, and for this one, station $i$, basically. Notice that when we apppended station $i$ to the left, we also appended a number to the right to reach a station, so each of the $i$th appended number can make the monkey reach station $i +1$ in the next move, the monkey needs to perform $i -1$ moves to the left (This can be zero), then make a jump to the right, which will make him reach station $i$ due to our height construction, and he can parcour all the number of the station he wants in (at most) $\lceil k \rceil - i - 1$ moves (Since he's already on the first number), which makes a total of $\lceil k \rceil $ moves as wanted. Remark : It may not be clear at all why our construction even corresponds to our $c$, this comes from the fact that when summing stations and the numbers on the left (Including $1$) in function of $k$, we get a total of $\frac{(k+3)(k)}{2}$ numbers, which contain our $n$ numbers, this was actually the main motivation behind Claim 1. An example for $n = 14$, which correspond to a perfect integer solution of $k = 4$, is given below : Arrangement of sticks : $14 -12 -11 -9 -8- 7- 5 -4 -3 -2 -1 -6 -10 -13$, you can check manually that the monkey can go between any pair of sticks in at most $4$ moves
07.06.2024 15:53
Put $n$ instead of $2024$. Enumerate the sticks as $0,2,\dots,n-1$ in increasing order of their lengths. Focus on the stick number $0$ (the stick with the smallest length). Clearly, the numbers on its right, resp. left, side must be in increasing order, otherwise the circus master's claim will be false. Look upon this configuration as if we first have the sequence $0,1,\dots,n-1$ arranged left to right, and then we color some of these numbers $0=a_0<a_1<a_2<\dots<a_k$ red and the remaining numbers we color blue (fig. 1). The jumping of the monkey can be viewed in the following way. If, at some moment, we are at the number $i$, at the next step we can access directly either the next red point or the next black point to the right side of $i$. Let us arrange the points (sticks/numbers) as on fig.2. We place each segment of points $[a_i,a_{i+1}-1]$ one on top of the other in a coordinate system $Oxy$. Consider the line $x+y=c$. We claim that we can rearrange some of the blue points (if needed) so that all the points lie on or bellow this line. Indeed, assume that the first row that crosses the line $x+y=c$ on the right corresponds to $a_j$, that is, it's $j$-th row with coordinates $y=j$. Let it contains the points $(c-j+1,j),\dots ,(c-j+k, j)$. The shortest path starting at $(0,0)$ and ending at $(c-j+k,j)$ must have at most $c$ steps. The only way to jump up over a row is when this row consists of only one red point. So, we must have at least $k$ rows that consist of single red point. So, we must have at least $k$ rows that consist of single red point. This allows us to move the blue points $(c-j+1,j),\dots, (c-j+k, j)$ vertically down, below $(1,j)$. We proceed in the same way with the following rows. The number of integer points in the triangle $(0,0), (c,0), (0,c)$ (including its contour) is equal to $1+2+\dots+(c+1)=(c+1)(c+2)/2$. Hence $$n\le \frac{(c+1)(c+2)}{2}$$which yields $c^2+3c+2-2n\ge 0$ and $$c\ge \left \lceil\frac{\sqrt{8n+1}-3}{2}\right \rceil \qquad(1).$$On the other hand, if $c$ equals the right hand side of $(1)$, we can arrange the points like on fig. 2. For $n=2024$, it gives $c=63$.