Let us assume that the statement is false. At each $k$'th iteration we will color the $k$'th walnut in pink. Observe that if the inequality $a<k<b$ doesn't hold, then we must have swapped walnuts of the same sort (either both uncolored or both pink). This implies that what happens to the colors is that at each iteration Jumpy just paints a certain uncolored walnut in pink. Now let's keep track of the number of pairs of adjacent walnuts which are both pink. At the start of the process it's $0$, and at the end it's $2021$. But observe that the parity of this quantity can change only when Jumpy colors a nut that has one pink and one uncolored neighbor. A contradiction! Q.E.D.

Dude awesome problem. In the $k^{\text{th}}$ move, color walnut $k$ green. Then it suffices to show a green walnut and a brown walnut are swapped at one point. For the sake of contradiction assume otherwise, that is, every swap swaps two walnuts of the same color. Then the state of the colors does not change after every swap, so we may reformulate the problem to the following: Reformulation wrote: There are $2021$ brown walnuts in a circle. In each move, Jumpy may choose one walnut whose neighbors are of the same color, and color it green. Show that Jumpy cannot color all walnuts green. First, consider a gap of $2n$ brown walnuts between two green walnuts on either side. It's impossible to color all these walnuts green. To see this, note that if $n = 1$, neither walnut can be colored (as both neighbors are of different colors). Otherwise, make one move (it cannot be on the first or last brown walnut). This move splits the brown walnuts into two groups, with $2n-1$ brown walnuts in total. Because this is odd, the groups are of different parities, so one group must have an even number of walnuts. Then keep splitting this group until you get a gap of two brown walnuts, at which point you can't color it. Now make two arbitrary moves; these divide the $2019$ brown walnuts into two groups. As $2019$ is odd, one of these groups must have an even number of walnuts, which you can't color all green. Yay! :DD

Call a walnut obedient if one of its neighbours is larger than it, and the other one is smaller. We call a process bad if the problem's condition is not satisfied. We want to prove that there are no bad processes. Lemma 1. The number of obedient walnuts is of the same parity as the number of walnuts.

Lemma 2. In a bad process, for any $j \in \{0,\ldots, 2021\}$, after $j$ moves, the number of obedient walnuts with labels greater than $j$ is odd.

Now, if a process is bad, after $2021$ moves there is an odd number of obedient walnuts greater than $2021$, which is a contradiction. Therefore, bad processes don't exist.

(Found a mistake in my solution, please disregard)

Solved with Isaac Zhu, Jeffery Chen, Kevin Wu, Albert Wang, Nacho Cho, Linus Hamilton, Sam Zhang. Assume for contradiction otherwise. On the $k$-th move, paint the $k$-th acorn red. The key observation due to the assumption at the beginning is that if we are swapping around acorn $k$, then both it's neighbors must be the same color: otherwise the problem would be finished. Now this gives a contradiction: if we draw an edge between every pair of adjacent red acorns, at each step we gain an even number of edges. But we're supposed to have $2021$ edges at the end, contradiction.

Write the number 0 on each walnut initially. Suppose we change the number on walnut k to 1 on turn k. Assume the problem statement is false, then the neighbors of walnut k at turn k have the same number, so swapping them has no effect on the number sequence. So we are changing a 0 to 1 at each step and we want to show at some point, we change a sequence like 100 to 110 or 001 to 011. At any given time, consider the maximal contiguous runs of 0. After the first move, there is one contiguous run of length 2020. I claim that given an initial configuration of 2k consecutive zeroes surroubded by 1s at the endpoints (i.e., $1 0^{2k} 1$) (*), if we change the 0's to 1's one by one, we must hit a forbidden configuration as mentioned above. For this we induct. Base case k=1 is trivial. For induction step note that if we change a 0 to 1 in a block of 2k consecutive 0s, we break this block into two blocks of size p,q where p+q=2k-1 is odd, so one of them must be even, say p. Induct on the block of length p. (*) We are "unwrapping" the circle here after the first move.

Call a walnut \(k\) conservative if on the \(k\)th move Jumpy swaps walnuts \(a\) and \(b\) with \(a,b<k\), and call a walnut \(k\) liberal if on the \(k\)th move Jumpy swaps walnuts \(a\) and \(b\) with \(a,b>k\). Assume for contradiction every walnut is either conservative or liberal. Claim: If walnut \(k\) is conservative, then it does not move after the \(k\)th move. Proof. Indeed, I contend the neighbors of \(k\) will always be smaller than the move number. After the \(k\)th move, the neighbors of \(k\) are \(a,b<k\) by design. If on move \(t\), a neighbor of \(k\) is swapped out, since the original neighbor was less than \(t\), the new neighbor is also less than \(t\). \(\blacksquare\) Claim: If \(k\) is conservative, then its neighbors in the final position are not conservative. Proof. If the \(k\)th move swaps \(a\) and \(b\), with \(a,b<k\), then \(a\) and \(b\) are not conservative since they move on the \(k\)th move. Whenever either neighbor of \(k\) is replaced, each resulting neighbor \(i\) is not conservative, since it is swapped after the \(i\)th move. \(\blacksquare\) It follows that there are at most 1010 conservative walnuts. Analogously there are at most 1010 liberal walnuts, contradicting that all walnuts are either conservative or liberal.

Assume for a contradiction that Jumpy never swaps two walnuts $a,b$ with $a<k<b$ in the $k$-th move. Before Jumpy can swap walnuts, Bushy woke up and observed Jumpy from afar. Bushy is angry upon discovering that Jumpy randomly swaps his beautifully arranged walnuts, so after the $k$-th move, Bushy steps in and removes the walnut $k$ from the hole. Observe that from what we assumed, a vacant hole cannot become occupied with walnut and vice versa. After Bushy removes the walnut $1$, the remaining walnuts become a single contiguous segment of $2020$ walnuts, which is even. Therefore, when a walnut is removed from this segment, it will be split into an odd and an even segment; we keep our eyes on this even segment. Considering this even segment further, we see that it will eventually be divided to a smaller even segment. Thus, by repeating this argument, eventually, we will get a segment of length $2$ that Bushy cannot take away any either walnut, a contradiction.

I expected this problem to be NT, since P1 was either Algebra or combo. So has the PSC dropped the method of P1, P2, P4 & P5 being a permutation of A, C, G & N?

No, P1 was NT.

Wu On the $k$th move, color walnut $k$ black, and let the other walnuts remain brown. We count the number of pairs of adjacent black walnuts. It’s easy to see that if the opposite is assumed, then the change in the quantity is even. But we require the quantity to become $2021$ which is odd at the end.

My solution is similar with the others.

A typical problem where everything depends on the point of view! Forget about the trajectory of the swapped walnuts and focus on the disposition of the consecutive numbers. Suppose at every move we mark the $k$-th walnut $k=1,2,\dots, 2021.$ Focus on the process of marking that eventually exhaust all walnuts. If there is a position where we mark a walnut and only one of its two adjacent ones is already marked then we are done. Indeed, in this case the walnut that has already been marked has a smaller number than the current one and the one that has not yet been marked has a larger number than the current one. Call this marking a good marking. We claim such a position will arise sooner or later, due to the fact $2021$ is an odd number. Note that any marking that is not good retains the disposition of the marked walnuts, that is, after the swapping that follows, the disposition of the marked walnuts is the same. Every time we mark a walnut, either it is a good marking or after that there is a block of even number (not zero) consecutive unmarked walnuts surrounded by marked ones. Thus, sooner or later if we avoid good marking, we would arrive at a position of two consecutive unmarked walnuts, surrounded by marked ones. So, when it comes to mark any of them it would be a good marking.

Remark: Inspired by EGMO 2016/1. I hope this isn't a fakesolve, it looks very different from the other solutions in this thread which makes me nervous. Edit: This is in fact a fakesolve, Bullet 3 Part 2 fails. Call a walnut $k$ cracked if one neighbor is larger than it, and one neighbor is smaller than it. Note that for all states, there exists at least one cracked walnut since 2021 is odd. AFTSOC that we never swap at a cracked walnut. We claim that the index of the largest cracked walnut after $k-1$ moves is nondecreasing, and this index is $\geq k$. At any step, consider the largest cracked walnut $d$ with neighbors $a,b, c<d<e$. If we're selecting walnut $k$, by the inductive hypothesis, $d\geq k$. We now do casework. If $k=d$ we win. If $k=c$, then if $b<c$, win. Otherwise, $b>c$, and post-swap: $a,d>c<b<e$, and $b>c=k\Rightarrow b\geq k+1$ so our inductive hypothesis holds If $k=b$. Case 1, if $b>c$. If $a>b$ we win; and if $a<b=k\leq d$, our new set is $c,b,a<d<e$. This satisfes since $d>b=k\rightarrow d\geq k+1$ Case 2, if $b<c$, if $a<b$ we win. Then $a>b$, and we get $c>b<a,d<e$, and since there are an odd number of steps from $c\to e$ in the other direction, there exists a cracked walnut there which is $>c>b$ so it holds. If $k\neq b,c,d$, note that $k\neq e$ since $e>d\geq k$. Thus, $d>k$ so we're good. Note we will not end up affecting the walnut at $d$, and since we increment by 1 at a time we will never miss $d$. Thus, we have shown that the index of the largest cracked walnut cannot decrease (or we win at some intermediate point), so eventually $k$ will get large enough to hit the $k=d$ case and we win. (Alternatively after 2021 moves the if we haven't won yet, then the index of the largest cracked walnut should be 2021, which is absurd.)

I'm so happy I solved this problem under test conditions, a very nice problem! Color a walnut of value $k$ red after the $k$'th operation. Clearly, $a<k$ iff $a$ is red. Thus, we will show that the transposition of a red and brown walnut must occur. AFTSOC that no such transportation happens. Clearly, the only such operations switch either a red and red or a brown and brown. Thus, the only color change is the one with the value $k$. Let us prove the following claim... Claim: If Given 2021 walnuts around a circle, all brown, where an operation consists of taking a brown walnut with two neighbors of the same color and changing it to a red. We cannot make all the walnuts red. Lemma: $n$ consecutive brown walnuts surrounded by two red walnuts cannot be operated into all red walnuts if $n$ is even. We will proceed with strong induction. For our basis, we see RBBR cannot be transformed into RRRR. For the inductive step, we see operating on a red walnut splits the brown walnuts into one even and odd group. By the hypothesis, all smaller even brown groups cannot be transformed into all reds, proving the Lemma. Now, for the claim, we see making two walnuts red divides the brown walnuts into an even and odd group, which cannot be all red. Thus, we cannot only perform the given operation and yield all red walnuts. Contradiction.

AFTSOC that we never win. Denote $S_k$ to be the set of walnuts numbered $\leq k$ after $k$ moves. Let $D_k$ be the set representing the sizes of continuous runs of walnuts not in $S_k$. We claim that for all $k\geq 1$, there exists some positive even integer $M$ in $S_k$. We prove this by induction, note that for $k=1$, $D_{1} = 2020$. For the inductive step, consider even positive integer $m\in S_k$. Note that the swap will be done centered at some walnut not in $S_k$. If this swap isn't in the $m$-run, $m\in S_{k+1}$ and we're done. If the swap is on the edges of the $m$-run, contradiction because it's swapping one value that's $\leq k$ and one's $>k$. Otherwise, we add to $S_k$ some element in the $m$-run and split it into an $a$-run and $b$-run satisfying, $a+b=m-1$, so one of $a,b$ is even and we're done. (they're also positive because you can't swap at the edges) $\square$ Now, this means that $D_{2021}$ has a positive even integer, a contradiction because all walnuts are $\leq 2021$ and we're done.$\blacksquare$

Suppose Jumpy is so angry that Jumpy decides to put poison on the $k$th walnut on move $k$ in an attempt to give Bushy food poisoning. Then, suppose each time Jumpy reorders, that the two walnuts moved had the poison state. Then, the only time the configuration of poisons changes is when Jumpy adds the poison. Consider the number of adjacent poisoned pairs of walnuts. Note that if Jumpy is swapping $a,b$ about $k$ then when $(a,k)$ becomes a poisoned pair so does $(b,k)$, so the parity never changes. The number starts with $0$ and ends with $2021$, contradiction!

Assume the opposite. Firstly paint each walnut white, and on $k-$th move paint $k-$th walnut black. By assumption each move swaps walnuts of same color, in particular it preserves parity of number of adjacent pairs of both black walnuts, which is $0$ at the beginning and $2021$ at the end, contradiction.

Wow! It has been a while since I first saw this problem, but for some reason, I never had the confidence to legitimately think about it. Tag each walnut with a tag $t_i = 1$ at the beginning. The $1$s will represent the walnuts that have yet to be chosen as a value of $k$. Every move, we choose a walnut tagged with a $1$ and change the tag to a $0$, assuming for the sake of contradiction that the two walnuts adjacent to it are always both tagged with $1$s or $0$s (i.e., have either both not been chosen already or have both been chosen). Of course, in each case, we have that the sum (indices mod $2021$) \[\sum_i |t_i - t_{i+1}|\]changes by exactly $2$. But at the beginning, it's $0$, and at the end, it's $0$. This is a contradiction modulo $4$ -- after an odd number of moves, the sum should be $2\pmod 4$! This completes the proof.

Call a walnut that has been the center of a move a "changed" walnut. For the sake of contradiction, assume that on every move, Jumpy swaps two walnuts that are either both less than the center one, or both greater. Then, Jumpy is either swapping two changed walnuts, or two yet-to-be-changed walnuts. Either way, one walnut becomes changed at each move, and the positions of the others remain constant. Number each hole in clockwise order: $1, 2, \dots, 2021$. Because of what we established before, once a hole contains a changed walnut, it will always contain a changed walnut. Therefore, we may refer to each hole as "changed" or "unchanged" - each move is equivalent to picking a hole and changing it. Set, WLOG, walnut $1$ in hole $1$. Then, at some point, we must change hole $2$ - before we do that though, hole $3$ has to be changed. When we change hole $3$, holes $2$ and $4$ must both be unchanged, so we also must change hole $3$ before hole $4$. So when we change hole $4$, both holes $3$ and holes $5$ must be changed. This pattern continues, until we have that hole $2022$ must be changed after hole $2021$, which is a contradiction, since hole $2022$ is hole $1$, which we assumed was changed first. Therefore, Jumpy must swap two walnuts $a$ and $b$ with $a < k < b$.

Assign a walnut a signature if it's been the center of a reordering the number 1, and 0 otherwise. AFTSOC Jumpy is swapping two walnuts that are both less or greater than the indice of the center walnut; in particular, Jumpy swaps two walnuts with the same signature, hence a hole never changes it's signature. WLOG set walnut 1 in hole 1 by shifting hole \#s; when we change hole 2, we must have that hole 3 had a signature of 1, since hole 1 has a signature of 1, whence hole 4 has a signature of 0 before changing hole 3, etc. We continue this way until we get that hole 2022=1 must have a signature of 0 before changing hole 2021, contradiction since we gave hole 1 a signature of 1 first. We conclude. Remark. Signature seems like such a common word to assign now, I've seen it in several problems lol

We assume the opposite for the sake of contradiction. Label a hole $k$ black on the kth move when it is chosen, and keep it black for the remaining of the process. Keep a hole white if it hasn't been chosen yet. Notice that on each move we should be swapping holes of the same color, and obviously we will turn the middle hole from white to black. Also note that once a slot holds a black hole, it must always hold a black hole otherwise the problem is proved. Now, simply consider an arc of the circle that is $B\underbrace{WW \dots WW}_{x}B$. The color of the endpoints of this arc can never be changed otherwise the problem is proved, so we shift our attention to the inner part. We prove by strong induction that if $2 \mid x$, then there must be a move that swaps two holes of opposite color. The base case of $x = 2$ is clear. Now assume that for an even $n$, that all evens less than $n$ follow the hypothesis. One of the inner $W$'s will be chosen and will be turned to a $B$. Now, we have $B\underbrace{W \dots W}_{a}B\underbrace{W \dots W}_{b}B$, where $a+b$ is odd, implying that one of $a$ and $b$ is even, so we have completed induction. Now, notice that after the first two moves, there must be an arc that will contain an even number of $W$'s that connects the two black holes because $2021$ is odd, so we are done.

Assume for the sake of contradiction otherwise. Rephrase the problem in terms of the color of a walnut. Color the $k$-th walnut red on the $k$-th turn. Note that as we swap two walnuts of the same color on the $k$-th term by assumption, the coloring remains the same. Clearly we begin with $0$ pairs of adjacent red walnuts and end with $2021$ pairs of adjacent red walnuts. Now on any given turn a walnut that changes color has two neighbors of the same color, so the pairs of adjacent red walnuts either goes up by $2$ or by $0$, a contradiction.

Consider the process that happens after Jumpy rearranges the walnuts. Initially, each walnut has a unique position around the circular pattern of holes. After Jumpy's sequence of moves, some walnuts might return to their original positions, while others might have moved around. Now, let's imagine that none of the swaps involve a pair of walnuts where one walnut has a number smaller than $k$ and the other walnut has a number larger than $k$. This means that for every swap that occurs during Jumpy's sequence of moves, either both walnuts have numbers smaller than $k$, or both walnuts have numbers larger than $k$. Let's consider the total displacement of all the walnuts that have numbers smaller than $k$ after Jumpy's moves. Similarly, let's consider the total displacement of all the walnuts that have numbers larger than $k$ after Jumpy's moves. The sum of displacements of walnuts smaller than $k$ and walnuts larger than $k$ around the circle must be equal in magnitude but opposite in direction (due to the circular nature of the arrangement). This is because each swap results in a net displacement of $0$ for the overall circle, as each walnut returns to its original position after a full circle. If there were no swap that involves a pair of walnuts where one walnut has a number smaller than $k$ and the other walnut has a number larger than $k$, then the sum of displacements of walnuts smaller than $k$ and the sum of displacements of walnuts larger than $k$ would have to be different, leading to a contradiction. Therefore, there must be a swap involving a pair of walnuts $a$ and $b$ such that $a<k<b$ during Jumpy's sequence of moves.

Suppose that after the $m$-th move, walnut $m$'s value becomes $0$. If we can find a value of $k$ that works here, it must also work in the original problem as if $m<k$, then $0<k$, and if $m>k$, then $m$ hasn't turned into $0$ yet. Therefore, we now want to show that $0$ and something $\ne 0$ swapped during the process(call this a "forbidden move"). Suppose not. After the first move, there is a "contiguous chain" of $2020$ nonzero numbers. We can never have an end of a chain perform their swap unless the chain is of length $1$. Claim. An even chain will always cause a forbidden move. Proof. Let the chain be of length $2n$. We will strong induct on $n$. Base case $n=1$ is trivial, so assume that $1,2,\dots,n-1$ work. Then on the first move of that chain, the chain will be split into two parts of length $a$ and $2n-1-a$, one of which will have a smaller even length, which will cause a forbidden move. Thus our chain of $2020$ will cause a forbidden move, contradiction. $\blacksquare$

Suppose otherwise. On the $k$th turn, color the $k$th walnut red. Each walnut we color red must be between two walnuts of the same color. The number of pairs of adjacent red walnuts changes by $2$ or $0$, but we must go from $0$ to $2021$. Therefore, this is impossible.

Consider the same operation, but after a swap you add $2021$ to the label of the walnut just operated on. Every swap now satisfies $k<a,b.$ We want to then show that there is some swap that swaps a number $\le 2021$ and a number $>2021.$ This is doable iff at every step, between every two consecutive $>2021$ walnuts there is an odd number of $\le 2021$ walnuts (by induction), but this is false after the first step, since there are $2020$ walnuts between the one with label $2022$ and itself.

At the start, paint all walnuts white and then paint walnut $k$ on the $k$th turn black. Then notice that the condition $a < k < b$ is equivalent to swapping two walnuts of differing colors. So then FTSOC assume that throughout, we always swap two walnuts of the same color. However notice that the number of adjacent pairs of black walnuts is always $0 \pmod 2$ as we can only add a black walnut in between two black walnuts or in between two white walnuts. This is a contradiction as our final state with $2021$ black walnuts has an odd number, so we are done.

I found this very straightforward for IMO5? This is one of those ``quasi-invariant" problems where simplifying the structure inexplicably yields a neat solution. Call an acorn large if we have already performed a move on it and small otherwise. Assume for the sake of contradiction that there exists an ordering for which the condition is not true. Let the dynamic variable $k$ denote the number of groups between two consecutive large acorns that have an even number of small acorns between them. Claim. The parity of $k$ is constant. Proof. In any move that does not satisfy the condition, one small acorn surrounded by either two large or two small acorns is converted into a large acorn. If the acorn were originally part of an odd group, the first case eliminates this odd group, and the second case splits the odd group into two even or two odd groups. If the acorn were originally part of an even group, the first case is impossible, and the second case splits the even group into one even and one odd group. In both cases, the parity of $k$ does not change. $\blacksquare$ But after the first move, $k = 1$ is odd, and after all moves are complete, all acorns are large, so $k=0$. This yields a contradiction.

Rephrase the problem as so: Let there be $2021$ acorns arranged in a circle, and for each move we can color exactly one acorn red. We show that it is impossible to completely color all acorns red without coloring an acorn red where the immediately adjacent acorns are different colors. We show that it is impossible for a string with an even number of acorns, where both endpoints of the string start as red. Note that this is an easy induction starting from where there are $4$ acorns. Because the original circle of $2021$ acorns can be arranged as a string with $2022$ acorns with both endpoints starting as red, we're done$.\blacksquare$

$ $