Bushy and Jumpy and the unhappy walnut reordering

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1098 posts

#1 h Jul 20, 2021, 8:39 PM • 17 Y

Y by Functional_equation, centslordm, InternetPerson10, Mathmick51, TheStrayCat, megarnie, Aritra12, 554183, adityaguharoy, Aopamy, yshk, deplasmanyollari, eggymath, Kingsbane2139, Rounak_iitr, Funcshun840, cubres

Two squirrels, Bushy and Jumpy, have collected 2021 walnuts for the winter. Jumpy numbers the walnuts from 1 through 2021, and digs 2021 little holes in a circular pattern in the ground around their favourite tree. The next morning Jumpy notices that Bushy had placed one walnut into each hole, but had paid no attention to the numbering. Unhappy, Jumpy decides to reorder the walnuts by performing a sequence of 2021 moves. In the $k$ -th move, Jumpy swaps the positions of the two walnuts adjacent to walnut $k$ .

Prove that there exists a value of $k$ such that, on the $k$ -th move, Jumpy swaps some walnuts $a$ and $b$ such that $a<k<b$ .

This post has been edited 2 times. Last edited by popcorn1, Jul 20, 2021, 8:40 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ComiCabE

25 posts

ComiCabE

#2 h Jul 20, 2021, 9:41 PM • 36 Y

Y by centslordm, Modesti, lahmacun, Mathmick51, InternetPerson10, TheStrayCat, megarnie, edfearay123, NumberX, Pitagar, oolite, guptaamitu1, VicKmath7, richrow12, CahitArf, Timmy456, Bobcats, PianoPlayer111, GioOrnikapa, WinterSecret, rayfish, FragileBonds, Aopamy, SPHS1234, jeteagle, Mehrshad, Dukejukem, Rexaria112, mathmax12, levifb, TheHimMan, Stuffybear, eggymath, Funcshun840, Kingsbane2139, cubres

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.

This post has been edited 2 times. Last edited by ComiCabE, Jul 20, 2021, 9:44 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

InternetPerson10

450 posts

InternetPerson10

#3 h Jul 21, 2021, 12:37 AM • 8 Y

Y by TheStrayCat, sarjinius, centslordm, skyguy88, ike.chen, eggymath, Rounak_iitr, cubres

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

square_root_of_3

78 posts

square_root_of_3

#4 h Jul 21, 2021, 1:21 AM • 5 Y

Y by centslordm, megarnie, PianoPlayer111, eggymath, cubres

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.
Proof
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.
Proof
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.

This post has been edited 3 times. Last edited by square_root_of_3, Jul 23, 2021, 12:02 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TheStrayCat

161 posts

TheStrayCat

#5 h Jul 21, 2021, 1:58 AM • 4 Y

Y by centslordm, megarnie, eggymath, cubres

(Found a mistake in my solution, please disregard)

This post has been edited 3 times. Last edited by TheStrayCat, Jul 21, 2021, 4:21 AM
Reason: Found a mistake

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SnowPanda

186 posts

SnowPanda

#6 h Jul 21, 2021, 2:07 AM • 4 Y

Y by centslordm, megarnie, eggymath, cubres

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

VulcanForge

626 posts

VulcanForge

#7 h Jul 21, 2021, 3:27 AM • 6 Y

Y by Inshaallahgoldmedal, centslordm, megarnie, eggymath, i3435, cubres

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AnonymousBunny

339 posts

AnonymousBunny

#8 h Jul 21, 2021, 3:40 AM • 3 Y

Y by centslordm, eggymath, cubres

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.

This post has been edited 1 time. Last edited by AnonymousBunny, Jul 21, 2021, 3:48 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TheUltimate123

1740 posts

TheUltimate123

#9 h Jul 21, 2021, 4:04 PM • 8 Y

Y by centslordm, HamstPan38825, sabkx, math_comb01, eggymath, Dissonant, Rounak_iitr, cubres

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.

This post has been edited 1 time. Last edited by TheUltimate123, Jul 22, 2021, 4:41 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MarkBcc168

1595 posts

MarkBcc168

#10 h Jul 21, 2021, 10:30 PM • 7 Y

Y by L567, centslordm, PIartist, sabkx, eggymath, Funcshun840, cubres

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.

This post has been edited 2 times. Last edited by MarkBcc168, Jul 21, 2021, 10:42 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Richangles

139 posts

Richangles

#11 h Jul 21, 2021, 11:13 PM • 2 Y

Y by centslordm, cubres

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jasperE3

11334 posts

jasperE3

#12 h Jul 21, 2021, 11:29 PM • 3 Y

Y by centslordm, eggymath, cubres

No, P1 was NT.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megarnie

5608 posts

megarnie

#13 h Jul 22, 2021, 2:06 AM • 4 Y

Y by centslordm, Han-htr, eggymath, cubres

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

554183

484 posts

554183

#14 h Jul 22, 2021, 3:26 AM • 3 Y

Y by centslordm, eggymath, cubres

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

starchan

1609 posts

starchan

#15 h Jul 22, 2021, 7:01 AM • 2 Y

Y by centslordm, cubres

Solution?

This post has been edited 1 time. Last edited by starchan, Jul 28, 2021, 9:52 AM
Reason: Fixed an error in my previous solution.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JAnatolGT_00

559 posts

JAnatolGT_00

#41 h Sep 23, 2022, 8:25 PM • 1 Y

Y by cubres

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

PROA200

1748 posts

PROA200

#42 h Mar 7, 2023, 6:42 AM • 3 Y

Y by sabkx, ike.chen, cubres

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.

This post has been edited 1 time. Last edited by PROA200, Mar 7, 2023, 6:43 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ihatemath123

3446 posts

ihatemath123

#43 h May 27, 2023, 7:30 PM • 1 Y

Y by cubres

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

huashiliao2020

1292 posts

huashiliao2020

#44 h Sep 9, 2023, 1:32 AM • 1 Y

Y by cubres

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. :surf:

Remark. Signature seems like such a common word to assign now, I've seen it in several problems lol

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pi271828

3371 posts

pi271828

#45 h Nov 22, 2023, 7:20 PM • 1 Y

Y by cubres

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Shreyasharma

682 posts

Shreyasharma

#46 h Dec 7, 2023, 2:48 AM • 2 Y

Y by eggymath, cubres

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RGB

19 posts

RGB

#47 h Dec 20, 2023, 11:12 AM • 2 Y

Y by eggymath, cubres

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cj13609517288

1919 posts

cj13609517288

#48 h Mar 25, 2024, 2:03 PM • 2 Y

Y by eggymath, cubres

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lnzhonglp

120 posts

lnzhonglp

#49 h Jun 6, 2024, 8:34 AM • 2 Y

Y by eggymath, cubres

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OronSH

1745 posts

OronSH

#50 h Jun 10, 2024, 2:03 PM • 4 Y

Y by megarnie, eggymath, ihatemath123, cubres

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dolphinday

1326 posts

dolphinday

#51 h Jun 14, 2024, 1:55 AM • 2 Y

Y by eggymath, cubres

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8866 posts

HamstPan38825

#52 h Jun 15, 2024, 12:17 AM • 1 Y

Y by cubres

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.

This post has been edited 1 time. Last edited by HamstPan38825, Jun 15, 2024, 12:18 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Martin2001

155 posts

Martin2001

#53 h Aug 26, 2024, 1:03 AM • 1 Y

Y by cubres

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$

This post has been edited 1 time. Last edited by Martin2001, Aug 26, 2024, 1:04 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mathandski

758 posts

Mathandski

#54 h Nov 26, 2024, 8:33 PM • 1 Y

Y by cubres

$\text{[math]}$

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Blast_S1

358 posts

Blast_S1

#55 h Apr 22, 2025, 2:30 AM • 1 Y

Y by cubres

Let $f(n)$ be $1$ if both neighbors of $n$ are greater, $-1$ if both are smaller, and $0$ otherwise. Since the sum of $f(n)$ over all $n$ is $0$ , and since $2021$ is odd, it follows that there exist an odd number of $n$ such that $f(n) = 0$ .

Consider the $k^\text{th}$ move. If $f(k) = 0$ , then we're done. If $f(k) = 1$ , then the move only affects $f(n)$ for $n > k$ . If $f(k) = -1$ , then the move only affects $f(n)$ for $n < k$ . The parity of the number of $n > k$ for which $f(n) = 0$ is invariant in the latter two cases. The end.

Z K Y