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: ___∙ 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. ___∙ 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_nis 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 (0th 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 ith 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.