Bump....

I will post my solution later.

We're glad you informed us

I posted that so that I don't forget xD

bumpity bump demmy wrote: Bump....

Here's the long awaited solution. Find the minimum number of moves that could have taken place between any two adjacent cells based on the remainder $\mod 20$ (doing all the 20-moves and then fix the remainder using 1-moves). Adding it all up we get at least 2023 moves, meaning these were exactly the moves played. Now just take the last position that you played a 20 move to the right (it is exactly 11 cells from the right). One of the tokens had to end up at least 9 places behind that cell, meaning it had to move back 9 times.

gvole wrote: Here's the long awaited solution. Find the minimum number of moves that could have taken place between any two adjacent cells based on the remainder $\mod 20$ (doing all the 20-moves and then fix the remainder using 1-moves). Adding it all up we get at least 2023 moves, meaning these were exactly the moves played. Now just take the last position that you played a 20 move to the right (it is exactly 11 cells from the right). One of the tokens had to end up at least 9 places behind that cell, meaning it had to move back 9 times. thanks

Alfombra12 wrote: For the sake of contradiction, assume that all tokens moved at most $8$ boxes to the left and let's try to find a lower bound for the number of moves needed. We can clearly see that the optimal strategy, i.e. the one which minimizes the moves needed, ought to place a token on the second and third boxes, then divide the remaining $200$ boxes on continuous segments of $20$ boxes, to each of this segments a set of $20$ tokens should be taken to later place a token on the remaining boxes of such segment efficiently. Let the $i-$th set of $20$ tokens be taken to the $j_i-$th place in the $i-$th segement. Note that, given our assumption and our intention of placing a token in least number of moves in the rest of boxes of each segement, $j_i \le 9$. We can now deduce that $$\text{Number of moves} \ge 3 \hspace{0.2cm} + \hspace{-0.4cm} \underbrace{10( 2+j_1) + 20(1+2+\ldots+9)}_{\text{Moves to place the sets of $20$ tokens on each segment.}} \hspace{-0.4cm} + \hspace{-1cm} \overbrace{\sum_{i=1}^{10} (\frac{(j_i-1)j_i}{2} + \frac{(20 - j_i)(21-j_i)}{2})}^{\text{Moves to place tokens on the rest of boxes of a segment efficiently.}} \hspace{-1 cm} \ge 2033$$$$\vspace{2 cm}$$A contradiction and thus a token must have moved to the left at least $9$ times. Furthermore, note that using this same strategy and letting $j_i = 10$ for all $i$ places a single token on every box on exactly $2023$ moves. This is not correct, because the blocks of $20$ tokens do not need to be disjoint. In fact, it is possible to reach the final position in $2024$ moves without any token moving to the left nine times. For simplicity, let us do this for $40$ tokens. Your bound would imply that $240$ moves are necessary, but actually $239$ are enough. The procedure is as follows: Take a block $B_1$ of $20$ tokens, move it to the $10$th cell. Take the remaining tokens $B_2$, and move them to the $9$th cell. Take a token $t_1\in B_1$, and move it one cell to the left. Take one token $t_2\in B_2$, and move it to the first cell. Take the $20$ tokens on the $9$th cell, and move them one cell to the right. Move $B_1$ to the $29$-th cell. Use the tokens in $B_2\setminus\{t_2\}$ to cover the cells $2$ to $20$. Use the tokens in $B_1$ to cover the cells $21$ to $40$, making sure that $t_1$ ends in the $40$th cell. That's a total of $239$ moves. For $203$ tokens, make $10$ blocks of $20$ tokens, and use the exchange trick (where you move $19$ tokens from one block and one from another) for every pair of consecutive blocks. The key to the problem is that the exchange is not possible with the last block.

Stuttgarden wrote: This is not correct, because the blocks of $20$ tokens do not need to be disjoint. In fact, it is possible to reach the final position in $2024$ moves without any token moving to the left nine times. For simplicity, let us do this for $40$ tokens. Your bound would imply that $240$ moves are necessary, but actually $239$ are enough. The procedure is as follows: Take a block $B_1$ of $20$ tokens, move it to the $10$th cell. Take the remaining tokens $B_2$, and move them to the $9$th cell. Take a token $t_1\in B_1$, and move it one cell to the left. Take one token $t_2\in B_2$, and move it to the first cell. Take the $20$ tokens on the $9$th cell, and move them one cell to the right. Move $B_1$ to the $29$-th cell. Use the tokens in $B_2\setminus\{t_2\}$ to cover the cells $2$ to $20$. Use the tokens in $B_1$ to cover the cells $21$ to $40$, making sure that $t_1$ ends in the $40$th cell. That's a total of $239$ moves. For $203$ tokens, make $10$ blocks of $20$ tokens, and use the exchange trick (where you move $19$ tokens from one block and one from another) for every pair of consecutive blocks. The key to the problem is that the exchange is not possible with the last block. I wish AoPS notified you when someone replies to one of your posts, I would have answered sooner! Anyways, there is a huge chance of me being mistaken; nevertheless, I can't see where I went wrong this time. At first I thought that you had found a mistake in my procedure, but we were probably making the same arithmetic error. Note that, in your example, my procedure places the first set of $20$ tokens in the $10$th place and the second one in the $30$th place then we scatter the rest of the tokens in each disjoint set of $20$ bowls. This would take us $\color{red} 9 \color{black} \times 2 + 20 + 2 \times (9\times 10 / 2 + 10 \times 11 / 2) = 238$ moves (you, and so did I at first, probably wrote a $10$ instead of the $9$ coloured in red). Furthermore, note that the algorithm you propose is the same as mine, note that what you did is the same as placing the sets of $20$ tokens in the $10$th and $29$th places and the scattering the tokens among two disjoint sets of $20$ bowls, you just did that in a different order. This is why your algorithm takes $8+9+20+8 \times 9/2 + 11 \times 12/2 + 9\times 10/2 + 10 \times 11/2 = 239$ moves. Lastly, I will prove that my strategy is optimal (it is paramount to remember that this doesn't exclude procedures which, in essence, are the same but apply the steps in different order). Let there be $20a + b$ (with $b < 20$) bowls. We want to deliver a token to each of the last $20$ bowls, simple arithmetic reveals that this is best done by using a set of $20$ tokens instead of taking the tokens one by one and we can also see that placing the set of $20$ tokens in a place other than the last $20$ bowls is just a waste of moves, after placing it we just scatter the tokens. We have $20(a-1)+b$ left and taking a token to one of the last $20$ bowls is just a waste of moves. We can apply this arguement over and over and thus we conclude that it is best to take a set of $20$ tokens to each of the $a$ disjoint segments of $20$ contiguous bowls and latter scatter the tokens among the segment to which each set belongs. Finally, we trivially see that the least amount of steps needed to fill the first $b$ bowls are $(b-1)b/2$. P.D. Although the optimal strategy is somewhat intuitive, I would be glad to see alternative proofs for it minimizing the number of moves. (Alternatively, if I am mistaken don't hestitate to tell me so!)

Alfombra12 wrote: Furthermore, note that the algorithm you propose is the same as mine, note that what you did is the same as placing the sets of $20$ tokens in the $10$th and $29$th places and the scattering the tokens among two disjoint sets of $20$ bowls, you just did that in a different order. This is why your algorithm takes $8+9+20+8 \times 9/2 + 11 \times 12/2 + 9\times 10/2 + 10 \times 11/2 = 239$ moves. The difference is that if you do that with your algorithm, there is a token from the first set that moves to the left nine times, from the $10$th cell to the first. That is why you have the condition $j_i\leq 9$. In my algorithm, despite using the same number of moves, no token moves to the left nine times. The intended solution of this problem considers the boundary between each pair of adjacent cells. Each boundary must be crossed by a total of $202, 201, \dots, 1$ tokens. Then consider what is the minimum amount of moves that cross that boundary. For those whose residue is between $0$ and $10$ mod $20$, if $n=20k+r$, the optimal way is to use $k$ blocks of $20$ tokens and $r$ individual tokens, all to the right. But if it is between $11$ and $19$ mod $20$, then it is better to make $k+1$ moves of $20$ tokens to the right and then $20-r$ tokens to the left. This adds up to $2023$ moves. The key is that if you try to be optimal on the boundary crossed by $11$ tokens, you lose: of the $20$ tokens that you move at the same time (they MUST be different!), one of them must end the procedure at least on the $20$th cell from the right. But other boundaries do not have the same problem, because you can reuse tokens. This is why it is possible to complete the procedure in $2024$ moves without any token moving to the left nine times, rather than $2033$. In the case of $40$ coins, if you look at the boundary between the $9$th and $10$th cell, that boundary has to be crossed by $31$ tokens. The optimal way of doing it is by moving two blocks of $20$ right, and $9$ individual tokens left. But those two blocks of $20$ cannot use all $40$ tokens, otherwise the token that ends on the first cell moves to the left nine times.

I am starting to understand what you are trying to say, I appreciate the corrections. For me to fully grasp it, could you provide a full solution to the problem? Specially, could you further develop on this paragraph please? How would you prove that it is optimal? Stuttgarden wrote: The intended solution of this problem considers the boundary between each pair of adjacent cells. Each boundary must be crossed by a total of $202, 201, \dots, 1$ tokens. Then consider what is the minimum amount of moves that cross that boundary. For those whose residue is between $0$ and $10$ mod $20$, if $n=20k+r$, the optimal way is to use $k$ blocks of $20$ tokens and $r$ individual tokens, all to the right. But if it is between $11$ and $19$ mod $20$, then it is better to make $k+1$ moves of $20$ tokens to the right and then $20-r$ tokens to the left. This adds up to $2023$ moves.

Alfombra12 wrote: I am starting to understand what you are trying to say, I appreciate the corrections. For me to fully grasp it, could you provide a full solution to the problem? Specially, could you further develop on this paragraph please? How would you prove that it is optimal? Let us count the cells from right to left. Consider the boundary line between the $k$-th and the $k+1$-th cell. At the start of the procedure, all the tokens are to the left of this line. At the end of the procedure, exactly $k$ tokens are to the right of this line. Therefore, a total of $k$ tokens have jumped from left to right of this line. Observe that each move jumps over a single line. Therefore, by counting the minimum number of moves that is required to make $k$ tokens cross a line, and adding for $k$ between $1$ and $202$, we can get a lower bound on the number of moves required to achieve the final position. In order to achieve a total movement of $k$ coins with the minimum number of moves, it will never be optimal to make a move of a single coin to the left and a single coin to the right, as we could cancel these two moves and the total balance would be the same. Similarly, we can assume that we do not move $20$ tokens to the left and $20$ to the right. Finally, it will not be optimal to move $20$ tokens in the same direction individually, as moving them all at once uses $19$ fewer moves. Therefore, there are two options for how to make a total of $k$ tokens cross a line in the minimum possible number of moves. Either you move $\lfloor k/20\rfloor$ blocks of $20$ tokens to the right and then individual tokens to the right, or you move $\lceil k/20\rceil$ blocks of $20$ tokens to the right and then individual coins to the left. A simple count reveals that the former is optimal if the residue of $k$ mod $20$ is between $0$ and $10$, and the latter is optimal if the residue is between $11$ and $19$. Adding the resulting values, we get $2023$ as a lower bound for the number of moves required to achieve the final position. Now consider the boundary between the $11$th and the $12$th cells from the right. The minimum number of moves that could have crossed this boundary, by the argument above, is $10$, and this can only be achieved by sending a block of $20$ tokens to the right and then $9$ individual tokens to the left. Because the total number of moves matches the lower bound, we know that exactly $10$ moves crossed this boundary. Therefore, at some point there was a block of $20$ tokens that crossed this boundary and reached the $11$th cell from the right. Out of these $20$ tokens, one must have ended at least on the $20$th cell from the right, meaning that it moved to the left at least $9$ times, as we wanted to prove.