Also Indian TST D1 P3

Label the stones with number $1,2,...,n$. We will give more condition that Sisyphus only moves the stone with maximum number in that square. If $m$ is number labeled on stone which Sisyphus moves then the number of stones in that square must less than or equal to $m$. So, stone that label number $m$ can only move at most $m$ squares on the right. We get that stone labeled $m$ need at least $\left\lceil\frac{n}{m}\right\rceil$. Since, Sisyphus can move 1 stone in each turn. Hence, the number of turns is at least $$\left\lceil\frac{n}{1}\right\rceil+\left\lceil\frac{n}{2}\right\rceil+\cdots+\left\lceil\frac{n}{n}\right\rceil.$$

Also South Korean TST D1 P1. Lots of contestants struggled with it.

In fact I'll show the goal is $\Theta(n \log n)$; the shortlist problem is just lower bound. Lower bound We will prove that Steve requires at least \[ \left\lceil \frac n1 \right\rceil + \left\lceil \frac n2 \right\rceil + \left\lceil \frac n3 \right\rceil + \dots + \left\lceil \frac nn \right\rceil \]moves, which is $O(n) + n \left( \frac11+\dots+\frac1n \right) = n \log n + O(n)$. We break symmetry by labeling the stones $1$, $2$, \dots, $n$. Then we modify the operation such that when moving a stone from a cell, we always move the highest numbered stone in that cell. Thus, when the stone labeled $k$ moves, there are at most $k$ stones in the cell from which it moved, hence it moves at most $k$ spaces. Therefore, the stone labeled $k$ must move at least $\left\lceil n/k \right\rceil$ times, as desired. (This bound is actually sharp for $n=1,2,3,4,5,7$, so it is a good estimate!) Upper bound We show that $a_n = (1+o(1)) n \log_2 n$, using the merge-sort recursion. Suppose $x + y = n$. Then: One makes $x$ moves to jump $x$ of the stones by $y$, then make $a_y$ moves to move the remaining $y$ stones to cell $y$. Thus all stones are now in cell $y$. Then, one makes $y$ moves to jump $y$ of the stones by $x$, and finally makes $a_x$ moves to move the remaining $x$ stones to cell $n$. Hence \[ a_n \le (x+a_y) + (y+a_x) = n + a_x + a_y \]for any $x+y = n$. This is the merge sort recursion, so $a_n = (1+o(1)) n \log_2 n$.

v_Enhance wrote: In fact I'll show the goal is $\Omega(n \log n)$; the shortlist problem is just lower bound. Lower bound We will prove that Steve requires at least \[ \left\lceil \frac n1 \right\rceil + \left\lceil \frac n2 \right\rceil + \left\lceil \frac n3 \right\rceil + \dots + \left\lceil \frac nn \right\rceil \]moves, which is $O(n) + n \left( \frac11+\dots+\frac1n \right) = n \log n + O(n)$. We break symmetry by labeling the stones $1$, $2$, \dots, $n$. Then we modify the operation such that when moving a stone from a cell, we always move the highest numbered stone in that cell. Thus, when the stone labeled $k$ moves, there are at most $k$ stones in the cell from which it moved, hence it moves at most $k$ spaces. Therefore, the stone labeled $k$ must move at least $\left\lceil n/k \right\rceil$ times, as desired. (This bound is actually sharp for $n=1,2,3,4,5,7$, so it is a good estimate!) Upper bound We show that $a_n = (1+o(1)) n \log_2 n$, using the merge-sort recursion. Suppose $x + y = n$. Then: One makes $x$ moves to jump $x$ of the stones by $y$, then make $a_y$ moves to move the remaining $y$ stones to cell $y$. Thus all stones are now in cell $y$. Then, one makes $y$ moves to jump $y$ of the stones by $x$, and finally makes $a_x$ moves to move the remaining $x$ stones to cell $n$. Hence \[ a_n \le (x+a_y) + (y+a_x) = n + a_x + a_y \]for any $x+y = n$. This is the merge sort recursion, so $a_n = (1+o(1)) n \log_2 n$. Do you mean $\Theta(n\log n)$? I thought $\Omega$ refers only to the lower bound part?

v_Enhance wrote: We will prove that Steve requires at least \[ \left\lceil \frac n1 \right\rceil + \left\lceil \frac n2 \right\rceil + \left\lceil \frac n3 \right\rceil + \dots + \left\lceil \frac nn \right\rceil \]moves Hi, also, who is Steve?

Iteratively, for each $i=1, 2, \dots, n$, we will play through Sisyphus's complete sequence of turns. Along the way, we will (for some of his turns) change the stone that he moves from his chosen square. This will not change the number of stones in each square at any point in time, and it will not change the number of moves he makes; it only changes the identities of the moved stones. Our hope is to alter the moves in such a way so that the stones can be labeled $s_1, \dots, s_n$, with the property that $s_i$ always moves by steps of size at most $i$. Suppose we have already found and labeled $s_1, \dots, s_{i-1}$ and we are looking for a $s_i$. Make all $s_1, \dots, s_{i-1}$ invisible, and let us observe the movements of the visible stones. For any point in time, call the leftmost square containing a visible stone square $m$. Before Sisyphus starts his procedure, pick a stone $s_i$ in square $m$ and require him to never move $s_i$ unless it is the only visible stone in its square. When he obeys, $s_i$ is moved only when there are at most $i$ stones in square $m$ (i.e. at most $i-1$ invisible ones), meaning $s_i$ always moves by at most $i$, as desired. At the end of $n$ iterations, we successfully find $s_1, \dots, s_n$. Conclude since each $s_i$ must be moved at least $\lceil n/i \rceil$ times.

Easy for a C3 tbh. IndoMathXdZ wrote: Let $n$ be a given positive integer. Sisyphus performs a sequence of turns on a board consisting of $n + 1$ squares in a row, numbered $0$ to $n$ from left to right. Initially, $n$ stones are put into square $0$, and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with $k$ stones, takes one of these stones and moves it to the right by at most $k$ squares (the stone should say within the board). Sisyphus' aim is to move all $n$ stones to square $n$. Prove that Sisyphus cannot reach the aim in less than \[ \left \lceil \frac{n}{1} \right \rceil + \left \lceil \frac{n}{2} \right \rceil + \left \lceil \frac{n}{3} \right \rceil + \dots + \left \lceil \frac{n}{n} \right \rceil \]turns. (As usual, $\lceil x \rceil$ stands for the least integer not smaller than $x$. ) Label the stones from $1$ to $n$ in any order. Since the pebbles are indistinguishable, hence we can "add a game rule" that if a square currently has greater than $1$ pebbles, then the pebble with the largest label is moved first from that square. By this definition itself, it is easy to see that the pebble with label $i$ can cover atmost $i$ squares in one move, and so needs to be moved at least $\left \lceil \frac{n}{i} \right \rceil$ times. $\blacksquare$

Assign the stones weights $1,...,n$. Each time take the lightest stone from a pile. Observe the movement of stone with weight $k$: whenever it makes a move there are $\le n-k$ stones below it, so its step-size is $\le n-k+1$. Therefore the total number of steps is at least $$\sum_{k=1}^n \lceil\frac{n}{n-k+1}\rceil$$as desired.

Too easy for C3? Label the stones as $1, 2, \dots , n$. Each time Sisyphus moves, WLOG let him take the stone with the highest number. Then stone $i$ can only move by at most $i$ each time; this means that we need at least $\lceil \frac{n}{i} \rceil$ moves, and we're done.

like everyone else, bit surprised when I saw this was C3. who else here is going through all the imo shortlist problems in quarantine?

Number the stones from $1$ to $n$. WLOG, each time we move a stone from a particular square, we move the stone with the highest number. Now, consider stone $j$. Each time it is moved, there are at most $j$ stones in the same square as it (since each stone $i$ in the same square as $j$ satisfies $i \leq j$). Therefore, each time stone $j$ is moved, it moves by forward by at most $j$ squares, implying that it must be moved at least $\left\lceil \frac{n}{j} \right\rceil$ times. Thus, summing over $j$, we find that the total number of moves is at least \begin{align*} \sum_{i = 1}^n \left\lceil \frac{n}{i} \right\rceil, \end{align*}as desired. $\Box$

rip why is everyone's solution so nice WLOG suppose the stones are all stacked in a single column on each square. Then since the stones are all homogenous to Sisyphus, assume he takes the top stone each time, and moves it to the top of another column. For each stone $S$ let $f(S) = \left \lceil \frac{\text{number of squares to the right}}{\text{number of stones left, below or equal to it}} \right \rceil$. Let $\mathcal{S}$ be the set of all stones. Let $$X = \sum_{s \in \mathcal{S}} f(s).$$Then note that at the start, $X = \left \lceil \frac{n}{1} \right \rceil + \cdots + \left \lceil \frac nn \right \rceil$ and at the end $X = 0$. Suppose the red stone $R$ in the following diagram moves. Then the numerator of $f(R)$ decreases by at most as much as the denominator, and so $f(R)$ decreases by at most 1. For each green stone $g$, the numerator of $f(g)$ is constant but the denominator decreases. Hence $f(g)$ is either the same or increasing. For each black stone $b$ there is no change to $f(b)$. Thus the quantity $X$ decreases by at most one per move, and so there needs to be at least $\left \lceil \frac{n}{1} \right \rceil + \cdots + \left \lceil \frac nn \right \rceil$ moves to change it from the start value to $0$.

The stones are indistinguishable, and all have the same origin and the same final position. At any turn, after choosing a square, Sisyphus moves the stone with the largest number from this square. (So we can replace any two of them in each cell) 1: We will prove that there is such a stone that crosses all cells (it does not have to be 1 stone, it can be replaced with another one in any cell, but the path of the stone is 1 after 1). Proof: The $0$-cell will contain exactly 1 stone at some point, so by moving this stone 1 cell to the right, we get the same position as the starting one, and the $1$-cell will contain 1 stone at some point and so on. 2: We will prove that there is such a stone that crosses all 2nd cell. (at most each 2nd cell) Proof: At some point, the $0$-cell will contain exactly 2 stones (1 goes to the $2$-cell), and we need to prove that the $2$-cell will contain 2 stones at some point, but this is easy because we had a stone that crosses all cells and 1 from $0$-cell. Applying similar approaches, we get the solution.

Label the stones $1,2,\dots,n,$ and suppose Sisyphus always removes the highest-numbered stone from a square before removing the others. Then, the stone labelled $i$ clearly moves at most $i$ squares in any given turn, so the total number of turns is at least \[ \left \lceil \frac{n}{1} \right \rceil + \left \lceil \frac{n}{2} \right \rceil + \left \lceil \frac{n}{3} \right \rceil + \dots + \left \lceil \frac{n}{n} \right \rceil, \]as desired.

dame dame

I think the hardest idea in this problem is actually arriving at the idea of assigning weights and moving the minimal stone each time. After that it's just trivial. At any rate, without some experience I don't think this is easy by any means.

Pretty simple for a C3. Label the stones $1 - n$ and assume that every time he moves, he takes the stone with the largest label. Then for any label $k$, every time it moves it can only have a maximum of $k$ stones in a pile, meaning that it may move forward a maximum of $k$, hence the stone labeled $k$ needs a minimum of $\left \lceil \frac{n}{k} \right \rceil$ moves the reach the square $n$ as desired.

Label the stones $1$ to $n$ and wlog move the stone with the largest value in any square. We claim it takes the stone labeled $k$ at least $\lceil n/k \rceil$ moves. Indeed, we see that if $k$ is the largest stone it's square then that square must contain $\leq k$ stones. Thus, $k$ can travel at most $k$ square in any move. Proving the claim.

First, label the stones $1$ to $n$. Now WLOG every time we make a move, we will move the stone with the largest number in the square. Claim: It takes at least $\left \lceil \frac{n}{k} \right \rceil$ moves to move the stone numbered $k$ to the final square. Proof: If we move a stone with number $k$, then the square has at most $k$ stones in it. Now because of this, the stone can move at most $k$ squares to the right. Thus, since each turn it can move at most $k$ squares to the right, we have it requires at least $\left \lceil \frac{n}{k} \right \rceil$ moves to get to the final square. Now summing $k$ from $1$ to $n$ gives the desired bound.

Order the stones by coolness. Establish a stone hierarchical society where only the coolest stone in the stack gets to move and a lower class stone moving before a higher class one does is punishable by death. All the stones want to get to their workplace, but the nth stone can only take steps of up to size n. Since their step size is at most one more than the number of stones they are superior too, since otherwise, they aren't the coolest stone in the stack. So we are done.

Assign distinct weights to each of the $n$ blocks, with each weight being an integer from $1$ to $n$, with the condition that a stone may only be moved if it is the heaviest stone on its square. This will not affect the number of moves as the stones are by right indistinguishable. Consider the stone with weight $k$, where $1 \le k \le n$. It can only move if all the other stones on its square are lighter than it, hence there can be at most $k$ stones on that square. Thus, whenever it moves, it can only move a maximum of $k$ squares to the right, so it needs at least $\lceil \frac{n}{k} \rceil$ moves to reach the end. Summing, the conclusion follows. \end{solution}

Since the process is indistinguishable, we may label the stones with weights $1,2,...,n$ such that, at each step, we move forward the stone with greatest label in that square. In this way, the stone labeled with $k$ moves implies that there are at most $k$ stones on its cell. Hence, the stone $k$ moves at most $k$ cells forward. Therefore, stone $k$ needs at least $\left \lceil \frac{n}{k} \right \rceil$ steps to reach the last cell. Thus, Sisyphus needs at least $$ \left \lceil \frac{n}{1} \right \rceil + \left \lceil \frac{n}{2} \right \rceil + \left \lceil \frac{n}{3} \right \rceil + \dots + \left \lceil \frac{n}{n} \right \rceil $$to reach his goal. $\blacksquare$

I overcomplicated the solution again lol

Label the stones with numbers $1$ to $n$ such that whenever Sisyphus moves a stone from a square, he moves the stone with the highest number in that square. Then, the stone with label $k$ can move at most $k$ squares each time, so the stone $k$ takes at most $\left\lceil\frac nk\right\rceil$ moves to get to square $n$. By summing the moves for $1\le k\le n$ we solve the problem.

does anyone know how to get when equalities hold (it holds only in n=1,2,3,4,5,7 according to the official document on isl)

Let the stones be $1,2,\dots,n$. Suppose in each move Sisyphus moves the largest stone. If Sisyphus will move stone $k$, then that pile has at most $k$ stones, so each move, stone $k$ moves at most $k$ steps. Thus, it'll take at least $\left \lceil \frac{n}{k} \right \rceil$ steps for it to reach final pile. The result follows.

Numerate stones by $1,2,...,n.$ It doesn't matter which stone we move from square, so move the stone with maximal number. Note that we can move each stone $k$ by at most $k$ squares, and it's needed to perform $\left \lceil \frac nk \right \rceil$ steps for moving it to square $n.$ After summing this for $k=1,2,...,n$ we obtain the desired result.

First observe that from the first square, at least one stone must move $1$ space. The same holds for the space this stone lands on, and the same holds for the space this lands on, and so on. I'll assume WLOG it was the same stone. This gives us at least $n$ moves. Now ignore this stone and change the rules so each square with $k$ stones can have a stone pushed $k+1$ squares. Then we can repeat this argument. Some stone on the first square moves at most $2$ spaces, and some stone on the space that stone lands on moves at most $2$ spaces, and so on. Thus we can assume WLOG these were all the same stone. This gives us at least $\frac{n}{2}$ more moves. Delete this stone, and change the rules so the max range a stone can move is $k+2$. Repeatedly using this argument, and summing the number of moves it requires, we are done. Onto the 45 Mohs C4 :skull:

Arbitrarily label the stones $1, 2, \ldots, n$. We perform an analogous sequence of turns with the added stipulation that whenever a square with multiple stones is chosen, we move the stone with the highest label. It's clear that this produces an identical sequence of turns, as the original process treated all stones as indistinguishable. Moreover, the new condition ensures that stone $k$ can move at most $k$ squares to the right each turn. This means stone $k$ moves at least $\left\lceil \frac{n}{k} \right\rceil$ times, so summing across $k \in \{1, 2, \ldots, n\}$ finishes. $\blacksquare$ Remarks: I really need to un-wash myself right now, as this question took me multiple attempts over the course of a month. In retrospect, the easiest way to come up with the labeling idea is to use wishful thinking on the requested bound and try to define a labeling $s_1, s_2, \ldots, s_n$ such that $s_k$ can move by at most $k$ squares each move. One natural starting point is to label the stones $s_1, s_2, \ldots, s_n$ from back to front once all $n$ have left square $0$, with ties broken arbitrarily. This is somewhat nice because in the initial state, $s_k$ has exactly $k-1$ stones either behind or next to itself, so its moving power is at most $k$. However, issues clearly arise if $s_k$ ever leapfrogs $s_l$ for some $k < l$. On the other hand, by recalling how ties between stones were broken arbitrarily at the start, we can realize that in practice the moving power of $s_k$ can only possibly exceed $k$ if any stones with higher indices are in the same square as itself. At this point, arbitrarily breaking ties between the stones in this common square will enable the desired move length condition on each $s_i$ to hold. My final solution is just a much cleaner formulation of the framework deduced here.

Give the stones values $1, 2, \dots, n$. Only move a stone with value $k$ if all stones in the same spot with higher values have been moved. Now notice that a stone with value $k$ can only move $k$ spots at a time, meaning it must take at least $\left \lceil \frac{n}{k} \right \rceil$ for this stone to be moved to the end. Simply summing finishes.

Easy question. No idea why this was a India TST D1P3 Solution mostly same as @above. Let the stones be $1,2,\dots,n$. Assume in each move Sisyphus moves the largest stone. If Sisyphus will move stone $k$, then that pile has at most $k$ stones, so each move, stone $k$ moves at most $k$ steps. Thus, it'll take at least $\left \lceil \frac{n}{k} \right \rceil$ steps for it to reach final pile. The answer follows.

This felt hard? Label the stones $c_1$, $c_ 2$, $\dots$, $c_n$. Now assume that we only move the highest numbered stone in any given cell. Then it is clear that the minimum number of moves for stone $i$ is given by $\left\lceil \frac{n}{i} \right\rceil$ and we may sum to finish. Remarks: The idea of trying to assign each term of the form $\left\lceil \frac{n}{i} \right\rceil$ to each stone was kind of natural for me, but from there it felt extremely difficult to find the right argument. Namely the idea of numbering the stones and always moving the highest numbered stone in any given square felt difficult to find.

We can label the stones $1, \dots, n$ and if we have a choice between moving two stones we always move the stone with a higher value. So a stone of value $k$ can only be at most $k$ squares each time. This means this stone will take at least $\left\lceil \frac{n}{k} \right\rceil$ which gives the bound.

Label the stones $1$, $2$, $\dots$, $n$. WLOG, we can choose to move stones with higher labelings, if there are multiple in a square. Then stone $k$ can move at least $k$ squares each turn, so we get the lower bound $\left\lceil\frac{n}{1}\right\rceil+\left\lceil\frac{n}{2}\right\rceil+\cdots+\left\lceil\frac{n}{n}\right\rceil$.

We assign labels $1, 2, \dots, n$ to the stones and consider $S_i = \left \lceil\frac{x_i}i\right \rceil$ where $x_i$ is the position of the stone labeled $i$. Consider any set of moves $\mathcal S$. By always rearranging the labels among the stones in every position before every move in $\mathcal S$, we can guarantee that the largest labeled stone at a position always moves. Correspondingly, a stone labeled $k$ moves at most $k$ positions. So exactly one of the $S_i$ increases by at most $1$ every move and the result follows. Remark: This problem is much harder than the solution seems. The key is to notice that we only swap the labels within any spot (I had a solution where we rearrange all the labels after a move, which seems more intuitive but actually only proves the weaker bound $\left \lceil \frac n1+\frac n2+\cdots+\frac nn \right \rceil$.