Wording: There are $2022$ equally spaced points on a circular track $\gamma$ of circumference $2022$. The points are labeled $A_1, A_2, \ldots, A_{2022}$ in some order, each label used once. Initially, Bunbun the Bunny begins at $A_1$. She hops along $\gamma$ from $A_1$ to $A_2$, then from $A_2$ to $A_3$, until she reaches $A_{2022}$, after which she hops back to $A_1$. When hopping from $P$ to $Q$, she always hops along the shorter of the two arcs $\widehat{PQ}$ of $\gamma$; if $\overline{PQ}$ is a diameter of $\gamma$, she moves along either semicircle. Determine the maximal possible sum of the lengths of the $2022$ arcs which Bunbun traveled, over all possible labellings of the $2022$ points.Widehat is bad, but overarc is worse

The answer is $1011^2+1010^2+1 = \boxed{2042222}.$ Label points around the circle $P_1$ to $P_{2022}$ in circular order. WLOG $A_1 = P_1.$ Equality case: $P_1, P_{1012}, P_2, P_{1013}, \dots P_{1011}, P_{2022}$ then back to $P_{1}$. Consider sequence of points $A_{1} = P_1, A_{3}, \dots A_{2021}.$ Then the sum of the lengths of the $2022$ arcs is at most the sum of the (major) arcs $\widehat{A_1A_3}, \widehat{A_{3}A_{5}}, \dots \widehat{A_{2021}A_{1}}.$ This is $2022 \cdot 1011$ minus the sum of the (minor) arcs $\widehat{A_1A_3}, \widehat{A_{3}A_{5}}, \dots \widehat{A_{2021}A_{1}}$ (call this $S$). Obviously, $S$ is minimized when $A_1A_3 \dots A_{2021}$ is a convex polygon. If the polygon has point $P_{1012}$ or has points on both sides of diameter $P_{1}P_{1012},$ the sum of arc lengths is $2022.$ Otherwise it is $P_{1}P_{2}P_{3} \dots P_{1011}$ or $P_{1}P_{2022}P_{2021} \dots P_{1013}$ and the sum of arc lengths is $2020.$ Note $2022 \cdot 1011 - 2020 = 2042222.$ $\blacksquare$

mine! I was looking for a simple-looking concept that yielded a nontrivial problem and stumbled upon this arc-movement idea. For odd numbers of vertices the problem is too uninteresting, but the year happened to be even . My original solution was the same as the one written above. The official solution, though, is particularly nice: first consider the midpoints of arcs which form $1011$ diameters. Then the length of each arc is just the number of diameters it crosses, and one can show (1) each diameter is crossed an even number of times and (2) at most one diameter is crossed every time (both follow fairly quickly).

This was also #1 on USA TST for EGMO 2023.

Nice problem! Here's a solution with induction that I think is fairly neat (though not as much as the others). The answer is $2(1011^2-1011+1)=2042222$. Let the points in clockwise order be $P_0,\ldots,P_{2021}$, and label $P_i$ with $i$ because I'm lazy. To achieve this, Bunbun can travel to the points $0,1011,1,1012,\ldots,1010,2021,0$ in that order. For the bound, we induct on the general case with $2022$ replaced by $2n$ (so our bound is $2(n^2-n+1)$), with the claim holding for small $n$ by exhaustive search that I totally performed. Suppose we have some labelling of $2n$ points which achieves a distance of $D$. Draw segments $\overline{A_1A_2},\ldots,\overline{A_{2n}A_{2n+1}}$, and also draw a dot on the midpoint of arcs $\widehat{P_1P_2},\ldots,\widehat{P_{2n}P_{2n+1}}$. View the problem in terms of lengths of segments instead of arcs, where the length of a segment is not its Euclidean length but rather the number of dots intercepted by its minor arc (clearly these are equivalent definitions). The purpose of doing this is that we are now able to delete dots at will for our induction (and also because it's easier for me to think about). Arbitrarily select a pair of diametrically opposite points with a segment joining them, WLOG $0$ and $n$. Note that if there are no diameters drawn, then the sum of segment lengths is at most $2n(n-1)\leq 2(n^2-n+1)$, so we can always perform this selection. Then there are two cases based on the position of the two segments other than $\overline{P_0P_n}$ that have endpoint $0$ or $n$. Case 1 - if the two segments are on the same side of $\overline{P_0P_n}$, WLOG the side also containing $P_1$, then let them be $\overline{P_0P_a}$ and $\overline{P_nP_b}$ (with $0<a,b<n$, $a \neq b$). Erase these two segments along with $\overline{P_0P_n}$, and then draw $\overline{P_aP_b}$. The length of the segments then decreases by $n+a+(n-b)-|a-b|=2n+(a-b)-|a-b|$. If $a-b \leq 0$ then this quantity is at most $2n$, otherwise it's exactly $2n$. Case 2 - if the two segments are on opposite sides of $\overline{P_0P_n}$, then WLOG let them be $\overline{P_0P_a}$ and $\overline{P_nP_{n+b}}$, with $a\geq b$ (and $0<a,b<n$). Erasing the three segments as before and drawing $\overline{P_aP_{n+b}}$, the length of the segments decreases by $n+a+b-(n+b-a)=2a\leq 2n-2$. Note that both before and after this process, ignoring points $0$ and $n$, we maintain the condition that every point has two segments drawn, and furthermore the number of connected components will not change—i.e., it is still $1$, and Bunbun will visit every point (except for $0$ and $n$) by walking along the segments. Now delete points $0$ and $n$, and redraw the dots based on the points now on the circumference of the circle (so we will have dots at where $0$ and $n$ used to be but have two fewer dots total than before). This will decrease the length of a segment if and only if it crosses the former line $\overline{P_0P_n}$. In case 1, note that $\overline{P_aP_b}$ doesn't cross $\overline{P_0P_n}$. On the other hand, we have $2(n-1)$ segments now, and the number of segments crossing $\overline{P_0P_n}$ must be even, hence there are at least two segments not crossing it (including $\overline{P_aP_b})$. Thus the deletion decreases the length of the segments by at most $2n-4$. In case 2, we have no such restriction, so the length of segments is decreased by at most $2n-2$. In both cases, the net decrease in segment length is thus at most $4n-4$, so we have at least $D-4n-4$ length sum. On the other hand, post-deletion we essentially have a labelling of $2(n-1)$ points, so by inductive hypothesis $$D-(4n-4) \leq 2(n^2-3n+3) \implies D \leq 2(n^2-n+1)$$as desired. This completes the induction, so we are done. $\blacksquare$ Remark: Originally when solving this problem, after deciding that induction was worth a shot, I focused on the case where there wasn't a diameter instead because I thought it was simpler for whatever reason (of course $3<4$ so it "should" actually be the other way around—intuition gained?). I knew that there was the other case (which is now the only case in the induction) but I believed that it would be fairly simple: if every pair of diametrically opposite points has a segment between them, I originally suspected that we didn't even need induction and could just handle the case separately. Upon actually doing the writeup I realized that the case was quite hard to handle and would have to be dealt with separately. I wrote that case up first and began writing up my original case when I discovered that the segment replacing operation I had come up with earlier didn't always maintain connectivity, and trying to fix this would screw up the bound. I was quite dejected for a few minutes about this until I realized that in fact my "later case" was all that was necessary, since if it didn't apply then the desired bound was immediate without using induction. In other words, the final structure of the solution is fairly close to the reverse of what I had initially supposed it would be! I've had too many fakesolves that went down this route of some subtle condition being possibly discarded in the inductive step, so I'm glad that here not only did my solution not get killed by it (hopefully), but that it ended up being neater than it would've been.

v_Enhance wrote: This was also #1 on USA TST for EGMO 2023. Were there (publicly released) EGMO TSTs for 2021 and 2022? I know we sent teams those years, but I don't think the problems on the TST (if they exist) ever got posted. They tend to be pretty interesting, so I'd be curious to see them.

Remark: The solution is quite nice for $n=2k+1$. In this case, it is possible to get the maximum arc length, $k$, on every single jump, for a total of $k(2k+1)$. Main Solution: For an even number of vertices, it is impossible to get the optimal arc length on each jump, so we instead claim that the construction \[1\to 1012 \to 1013 \to \cdots k \to k+1011 \to \cdots 2020\to 1010 \to 2021 \to 1011 \to 2022 \to 1\]with $1011^2+1010^2 + 1 = 2022\cdot 1011 - 1010 - 1010 = 2022\cdot 1011 - 2020$ total distance is the maximum. We adopt $d(P,Q)$ to be the length of the shorter arc used in the problem statement. Then, the following fact significantly simplifies our computation: Lemma: For any $A,B,C$ on a circle that: \[d(A,B) + d(B,C) = 2022 - d(A,C)\]Proof: Obvious. Thus, the quantity in question can be rewritten as \begin{align*} d(A_1,A_2) + d(A_2,A_3) + \cdots &= (2022 - d(A_1,A_3)) + (2022 - d(A_3,A_5)) + \cdots (2022 - d(A_{2019},A_{2021}) + (2022 - d(A_{2021} ,A_1)\\ &= 2022\cdot 1011- \left(d(A_1,A_3) + d(A_3,A_5) + \cdots d(A_{2019},A_{2021}) + d(A_{2021}, A_1)\right)\\ \end{align*}So, now, we are left to minimize the perimeter of $A_1A_3\cdots A_{2021}$, a 1011-gon which we now denote as $ P = P_1P_2\cdots P_{1011}$. Claim: The perimeter of $P$ is at least 2020 Proof: We now consider a new polygon $Q$, where we take $P$, and remove any points which do not change the perimeter. If there are still $\geq 3$ points, this means that we go in a full cycle, for a perimeter of at least 2022. If we have 2 points (note that we cannot reduce further), the two points are at least $1009 + 1=1010$ apart to fit the other 1009 points in between them, for a total perimeter of at least 2020. $\square$ Thus, the maximum perimeter is $2022\cdot 1011 - 2020$ and we are done. $\blacksquare$.

Generalization: Suppose each arc is instead limited to a maximum length of $k$, where $k$ is a factor of $n$. Then, the maximum possible value is $kn-2(k-1)$.

IAmTheHazard wrote: v_Enhance wrote: This was also #1 on USA TST for EGMO 2023. Were there (publicly released) EGMO TSTs for 2021 and 2022? I know we sent teams those years, but I don't think the problems on the TST (if they exist) ever got posted. They tend to be pretty interesting, so I'd be curious to see them. No, because of the pandemic, there was just TSTST for those years.

Combo faster than geo OMG...10 MOHS? i'd say this is cute problem, i probably overcomplicated this. USA IMO TST 2023 Mock result 2/3, P1 took 40 mins. (All indices modulo 2022 btw) Definitions: Define the following functions: $$\text{minor}(A,B) \; \text{for points} \; A,B \in \gamma \; \text{this is the lenght of the minor arc} \; \widehat{AB}$$$$\text{mayor}(A,B) \; \text{for points} \; A,B \in \gamma \; \text{this is the lenght of the mayor arc} \; \widehat{AB}$$Clearly $\text{mayor}(A,B)+\text{minor}(A,B)=2022$ and $\text{mayor}(A,B)=\text{minor}(A,B)$ if $AB$ diameter, and now finally, define: $$\text{minor}(A,B)+\text{minor}(B,C)=f_B(A,C) \; \text{where} \; f_B(A,C)=\text{minor}(A,C) \; \text{if} \; \angle ABC \ge 90 \; \text{or} \; \text{mayor}(A,C) \; \text{if} \; \angle ABC \le 90$$The Key move: Now we want to get the maximun value of $$L=\sum_{n=1}^{2022} \text{minor}(A_n,A_{n+1})=\sum_{n=1}^{1011} f_{A_{2n}}(A_{2n-1},A_{2n+1})$$Which obviously happens when all the $f$'s are mayor's so now its enough to minimize $M$ where $L=2022 \cdot 1011-M$ $$M=\sum_{n=1}^{1011} \text{minor}(A_{2n-1},A_{2n+1})$$Clearly its minimun when $A_1A_3...A_{2021}$ is a convex polygon, and usualy one would think that by just espacing them 2 by 2 u get the minimun of 2022, however if u put all of them with minor distance of 1 then $\text{minor}(A_{2021},A_1)=1010$ so our minimun of $M$ is 2020. Hence the maximun of $L$ is $2022 \cdot 1011-2020$ One can achieve this by putting $(A_1,A_2), (A_3,A_4), ..., (A_{2021},A_{2022})$ as diameters and by setting $\text{minor}(A_n,A_{n+2})=1$ where $2020 \ge n \ge 1$ and $\text{minor}(A_{2021},A_1)=1010$ and $\text{minor}(A_{2022},A_1)=1$. Since we proved a maximun and showed a construction, we are done

Replace 2022 by an arbitrary even number $n \ge 4$. We claim that the answer is $\frac{n^2}{2} - n + 2$. Call a diameter of $\gamma$ a separator line if its endpoints are both halfway between two adjacent points in $A$. Clearly there are $n/2$ separator lines. In addition, notice that the distance travelled by moving between $A_i$ and $A_j$ is the number of separator lines that $A_iA_j$ crosses. Consider one separator line. Notice that during the bunny's journey, the line is crossed an even number of times (since each time the line is crossed, the bunny moves to a different side of it, and the bunny ends up back at its starting point in the end). Moreover, the line is crossed at most $n$ times, one for each one of the bunny's moves. Claim: Call a separator line good if it is crossed exactly $n$ times. Then there is at most one good separator line. Proof: Assume otherwise. Consider two good separator lines, which split the circle into four regions, each containing at least one point in $A$. Then the bunny must cross both lines on every move, so it could only visit two of the regions (the one $A_1$ is in and the one opposite of it), contradiction. Now, the total length the bunny travels is the sum of crossing counts over all separator lines. One such line can be crossed $n$ times; the remaining $\frac{n}{2} - 1$ lines can only be crossed up to $n-2$ times (since the number of crossings must be even). The sum of crossings over all lines is therefore at most $n + \left(\frac{n}{2} - 1\right)(n - 2) = \frac{n^2}{2} - n + 2$, proving the upper bound. The lower bound can be proven by considering the path \[A_1, A_{n/2 + 1}, A_2, A_{n/2 + 2}, A_3, A_{n/2 + 3}, \dots, A_{n/2}, A_{n}.\]Here, $n/2$ of the bunny's moves are of length $n/2$, $n/2 - 1$ moves are of length $n/2 -1$, and one move (from $A_n$ to $A_1$) is of length 1, giving the total length $\left(\frac{n}{2}\right)^2 + \left(\frac{n}{2} - 1\right)^2 + 1 = \frac{n^2}{2} - n + 2$, as desired.

The general answer for $2n$ points is $\boxed{2n^2 - 2n + 2}$. My construction is the same as that of others. Here's a sketch for proof: By EV, every construction with sum at least $2n^2-2n+1$ has to has have a triple $(A_{i-1}, A_i, A_{i+1})$ such that $A_{i-1}A_i$ and $A_iA_{i+1}$ are $n$ and $n-1$ in some order. The key towards inducting is to remove the point $A_i$, and merge the points $A_{i-1}$ and $A_{i+1}$ to one point—to reduce the problem to $2n-2$ points. Noting that every arc of the maximum $2n-2$ construction can be elongated by $1$ when applied to the $2n$ construction (if it crosses $A_{i-1}A_{i+1}$), we add $2n-2$. Yet, there has to be a jump that does not cross $A_{i-1}A_{i+1}$ (because basically one side has more points than the other), so minus one. In total, you get the bound of $$(2(n-1)^2-2(n-1)+1)+(2n-2) - 1 = 2n^2 - 2n + 2.$$

Remark: This idea of doing EV to get that something exists, remove that, and induct down is similar to that of Click to reveal hidden text

.

What is EV?

Plimpton322 wrote: What is EV? Expected value.

Thanks! Evan.

Answer: $2022\times 1011 - 2020 = 2042222$. Label the points $P_1, P_2,\ldots, P_{2022}$ clockwise and assume WLOG $A_1=P_{2022}=P_0$. To show attainability, let $A_1, A_2, \ldots, A_{2022}$ be $$P_0, P_{1011}, P_1, P_{1012}, P_2, \ldots, P_{1010}, P_{2021}, P_{2022}=P_0$$giving $\underbrace{(1011+1010)+(1011+1010)+\cdots+(1011+1010)}_{1010} + 1011+1 = 2022\times 1011 - 1010 - 1010$ as needed. Otherwise, notice that the sum of lengths travelled from $A_{2i-1}$ to $A_{2i+1}$ is at most $2022-x$, where $x$ is the minor arc distance of $\widehat{A_{2i-1}A_{2i+1}}$; if they travelled forwards and backwards the length would be $a+(a-x) \leq 1011+1011-x=2022-x$ and if they travelled in the same direction twice, the length would be $x\leq 2022-x$ or $2022-x$ as needed. But the points $A_1, A_3, \ldots, A_{2021}$ must be $1011$ distinct points so if $m\geq 1010$ is the minimal arc length covering all these points, the minimal value of $$\sum_{i=1}^{1011} \left\lvert \widehat{A_{2i-1}A_{2i+1}}\right\rvert \geq 2m \geq 2020$$so the total length travelled is at most: $$\sum_{i=1}^{1011} \left(2022 - \left\lvert \widehat{A_{2i-1}A_{2i+1}}\right\rvert\right)=2022\times 1011 - 2020$$as desired.

The answer is $\boxed{2042222}$. For construction, arrange the points as $A_1A_3A_5\ldots A_{2021}A_2A_4A_6\ldots A_{2022}A_1$ in a cyclic order. The length of the path obtained is: \[1011+1010+1011+1010+\cdots+1011+1010+1011+1=2021\times1010+1011+1=204222,\]as claimed. We now prove the bound. Note that for going from $A_i$ to $A_j$ the highest possible length of path is $1011|j-i|$ which can be obtained by going in semicircles. However, if $X,Y,Z$ are distinct points such that $X$ is the antipode $Y$, then $Z$ cannot be antipode of $Y$. So, the maximum length of path for bunny rabbit is $1011+1010=2021$. We can generalize this as \[\text{path length from }A_{2i-1}\text{ to }A_{2i+1}=2022-arc(A_{2i-1}A_{2i+1})\]Here $arc(XY)$ is length of minor arc $XY$. So, we want to minimize the sum $arc(A_1A_3)+arc(A_3A_5)+\cdots+arc(A_{2021}A_1)\geq2020$. Equality will hold when they are in order as $A_1A_3\ldots A_{2019}A_{2021}$ or a cyclic shift of the same. Hence, $\text{max path length}=2022\times1011-2020=2042222$.

I hate this bound. The answer is $1011^2+1010^2+1$ achieved by alternating moves of length $1011$ and $1010$ but on the last move do a $1$ length move to make it work. To prove the bound, consider the sequence by jumping $2$. Note that $A_1A_2+A_2A_3\leq 2022-A_1A_3$ where all distances are smaller arc lengths. Thus we minimize the length of the path $A_1A_3\dots A_{2021}A_1$. But on this path some two points must be at least $1010$ apart (if not, u can cross of points since one of each two diametrically opposite points must be chosen and u simply run out of choices). Thus, to get the full path you must travel at least $1010$ to that point and at least $1010$ to get back, so this path is at least $2020$ long. Therefore we get the total length is bounded above by \[2022\cdot 1011-2020=2022\cdot 1010+2=1011^2+1010^2+1.\]

I really didn't expect to solve this. But anyway, does anyone have any motivation about considering $A_1, A_3, ..., A_{2021}$? I tried small cases (even N, because odd is trivial) to get $2(x^2-x+1)$ where $x = \frac{N}{2}$, but then if you didn't notice that $A_1, A_3, ..., A_{2021}$ would give a good bound, what could you do?

Pretty sure I had the idea of considering the midpoint diagonals on my scratch paper, but it was found too early in my struggles and I thought it didn't do anything. Answer is $1011^2 + 1010^2 + 1$, attained with the greedy algorithm going clockwise. Let $\{P_1, \ldots, P_{2022}\} = \{A_1, \ldots, A_{2022}\}$ with $P_1, \ldots, P_{2022}$ in clockwise order, $P_1 = A_1$, and indices for the $P_i$ taken modulo $2022$. Take the function $f(\{P_i,P_j\})$ to be the number of times the rabbit touches an element of $\{P_i, P_j\}$ if neither $i$ nor $j$ is $1$, and one less than this value otherwise. The key claim is that $f(\{P_i, P_{i + 1011}\})\le 2021$, with equality attained for at most two diagonals. Since the rabbit can neither jump strictly over a diagonal more than $2019$ times nor touch the diagonal endpoints more than twice (minus the case where the rabbit starts on a diagonal point, but that is taken care of by the $-1$), the inequality follows. To show that equality can't be attained too frequently, first observe that if $P_i$ and $P_{i+1011}$ are not consecutive points in the rabbit's journey, then $f(\{P_i,P_{i+1011}\}) < 2021$ and if two consecutive points in the rabbit's journey are strictly on one side of the diagonal, then $f(\{P_i,P_{i+1011}\}) < 2021$. Now suppose, for the sake of contradiction, that $$f(\{P_a,P_{a+1011}\}) = f(\{P_b,P_{b+1011}\}) = f(\{P_c,P_{c+1011}\}) = 2021$$with $P_a$, $P_b$, and $P_c$ in clockwise order, as shown below. Without loss of generality suppose that the rabbit starts at point $P_a$. Because the rabbit makes an even number of moves to reach $P_a$ again, traverses both the $b$- and $c$-diagonals exactly once, and lands across the diagonal on the move after traversing it (otherwise, one side runs out of points too quickly), its last position before returning to $P_a$ must be on $\widehat{P_{c+1011}P_aP_b}$, which implies that the last move doesn't touch at least one of the diagonals. [asy][asy] size(5cm); defaultpen(fontsize(9pt)); pair PA = (0,5), PB=(4,3), PC=(5,0), A=-PA, B=-PB, C=-PC; draw(circle((0,0), 5), linewidth (0.8)+grey); draw(A--PA, linewidth(0.5)+red); draw(B--PB, linewidth(0.5)+green); draw(C--PC, linewidth(0.5)+blue); dot("$P_a$", PA, (0,1)); dot("$P_b$", PB, NE); dot("$P_c$", PC, (1,0)); dot("$P_{a+1011}$", A, (0,-1)); dot("$P_{b+1011}$", B, SW); dot("$P_{c+1011}$", C, (-1,0)); [/asy][/asy] Finally, the length sum is equal to one less than the sum of the number of times the rabbit touches each $P_i$, or just $$\sum_{i=1}^{1011} f(\{P_i,P_{i+1011}\}) \le 2020 \cdot 1009 + 2021\cdot 2 = 1011^2 + 1010^2 + 1.$$