Define the score of an ordering to be the number of arcs $R_i\to B_i$ that pass through $(1,0)$. My solution is broken into two parts. 1. Show that swapping two consecutive red points, i.e. $R_i$ and $R_{i+1}$, does not affect the score. This we call a transposition of consecutive points. Straightforward check (somewhat). 2. Show that any permutation of $R_1R_2\cdots R_n$ can be obtained by composition of transpositions in Part 1 (a.k.a. the transpositions of the form $(i\;\; i+1)$ generate $S_n$), and hence has the same score as $R_1R_2\cdots R_n$. There's a very intuitive way to do it that easily translates into a solution. There's some detail checking here and there, with part 1 being significantly more work than part 2 (which is basically trivial; I just described an algorithm), but overall very simple.

You can show that if you swap $R_i$ and $R_{i+1}$, then by looking at three cases the number of arcs $(1,0)$ is in stays the same.

Visually, if we draw all the segments $R_i \to B_i$ then we obtain a set of $n$ chords. Say a chord is inverted if satisfies the problem condition, and stable otherwise. The problem contends that the number of stable/inverted chords depends only on the layout of the points and not on the choice of chords. [asy][asy]size(6cm); pair A(int i) { return dir(22.5+45*i); } draw(unitcircle, grey); dot("$(1,0)$", dir(0), dir(0)); dotfactor *= 2; draw(A(7)--A(0), EndArrow, Margins); draw(A(1)--A(2), EndArrow, Margins); draw(A(3)--A(5), EndArrow, Margins); draw(A(4)--A(6), EndArrow, Margins); dot("$-1$", A(0), A(0), blue); dot("$0$", A(1), A(1), red); dot("$-1$", A(2), A(2), blue); dot("$0$", A(3), A(3), red); dot("$+1$", A(4), A(4), red); dot("$0$", A(5), A(5), blue); dot("$-1$", A(6), A(6), blue); dot("$+1$", A(7), A(7), red); [/asy][/asy] In fact we'll describe the number of inverted chords explicitly. Starting from $(1,0)$ we keep a running tally of $R-B$; in other words we start the counter at $0$ and decrement by $1$ at each blue point and increment by $1$ at each red point. Let $x \le 0$ be the lowest number ever recorded. Then: Claim: The number of inverted chords is $-x$ (and hence independent of the choice of chords). This is by induction on $n$. I think the easiest thing is to delete chord $R_1 B_1$; note that the arc cut out by this chord contains no blue points. So if the chord was stable certainly no change to $x$. On the other hand, if the chord is inverted, then in particular the last point before $(1,0)$ was red, and so $x < 0$. In this situation one sees that deleting the chord changes $x$ to $x+1$, as desired. (EDIT: I messed up the induction initially, trying to find a nice stable chord to delete. It seems easier to just delete $R_1 B_1$ and deal with the two cases.)

wait does extremal work

hamup1 wrote: Define the score of an ordering to be the number of arcs $R_i\to B_i$ that pass through $(1,0)$. My solution is broken into two parts. 1. Show that exchanging two red points that are consecutive, i.e. $R_i$ for $R_{i+1}$, does not affect the score. This we call a transposition of consecutive points. Straightforward check. 2. Show that any permutation of $R_1R_2\cdots R_n$ can be obtained by composition of transpositions in Part 1 (a.k.a. the transpositions of the form $(i\, j)$ generate $S_n$), and hence has the same score as $R_1R_2\cdots R_n$. There's a very intuitive way to do it that easily translates into a solution. There's some detail checking here and there, but overall this is the main idea. Can someone comment on if I forgot anything or misread the problem (*shudders*)? This is pretty much exactly what I did. Just to be safe I used monovariants for your step 2

Generic_Username wrote: wait does extremal work what i mean is first induct then consider closest point to $(1,0)$ going clockwise do casework on color; if its red then it always produces a good arc and if its blue otherwise regardless of indexing so use inductive hypothesis gg

DrMath wrote: You can show that if you swap $R_i$ and $R_{i+1}$, then by looking at three cases the number of arcs $(1,0)$ is in stays the same. This is exactly what I did

Same as hamup1 but wasn't part 1 like the whole thing? The way I showed it felt really ugly and like common sense but I had to do a few cases. for part 2 I outlined an algorithm in which you can just switch Ri with R(i-1) where Ri is the one you want to turn into R1 and then repeat this process for the remaining (R2,...,Rn). edit same as amplreneo and DrMath. But it was so gross and having to define crap, at least for me.

Basically same, maybe different cases though?

Can't you just do induction on $n$?

DrMath wrote: You can show that if you swap $R_i$ and $R_{i+1}$, then by looking at three cases the number of arcs $(1,0)$ is in stays the same. 3 cases? I only found 2 ($B_i$ before or after $R_{i+1}$)

UrInvalid wrote: DrMath wrote: You can show that if you swap $R_i$ and $R_{i+1}$, then by looking at three cases the number of arcs $(1,0)$ is in stays the same. 3 cases? I only found 2 ($B_i$ before or after $R_{i+1}$) I think you split it based on where the $R_i$ and $R_{i+1}$ are relative to $(1,0)$, at least that's what I did. The cases are slightly different?

UrInvalid wrote: DrMath wrote: You can show that if you swap $R_i$ and $R_{i+1}$, then by looking at three cases the number of arcs $(1,0)$ is in stays the same. 3 cases? I only found 2 ($B_i$ before or after $R_{i+1}$) I had case 1 which was the trivial one and then a case 2 but case 2 i split into sub cases 2.1,2.2,2.3. Am I right in saying you could do the cases a lot of different ways?

UrInvalid wrote: DrMath wrote: You can show that if you swap $R_i$ and $R_{i+1}$, then by looking at three cases the number of arcs $(1,0)$ is in stays the same. 3 cases? I only found 2 ($B_i$ before or after $R_{i+1}$) I did the same thing. Unfortunately I may have missed some small details with the arc constants (I had to draw diagrams), hopefully not too many points off. Basically when you swap $R_i, R_{i+1}$, there is one case where $B_i, B_{i+1}$ remains the same, and one case where the B's swap.

Generic_Username wrote: Generic_Username wrote: wait does extremal work what i mean is first induct then consider closest point to $(1,0)$ going clockwise do casework on color; if its red then it always produces a good arc and if its blue otherwise regardless of indexing so use inductive hypothesis gg GUYS PLEASE ANSWER ME IF THIS WORKS THEN ITS A REALLY NICE SOLUTION

mathgenius64 wrote: UrInvalid wrote: DrMath wrote: You can show that if you swap $R_i$ and $R_{i+1}$, then by looking at three cases the number of arcs $(1,0)$ is in stays the same. 3 cases? I only found 2 ($B_i$ before or after $R_{i+1}$) I did the same thing. Unfortunately I may have missed some small details with the arc constants (I had to draw diagrams), hopefully not too many points off. Basically when you swap $R_i, R_{i+1}$, there is one case where $B_i, B_{i+1}$ remains the same, and one case where the B's swap. That is still only two cases, but I think it is sufficient.

mathguy623 wrote: UrInvalid wrote: DrMath wrote: You can show that if you swap $R_i$ and $R_{i+1}$, then by looking at three cases the number of arcs $(1,0)$ is in stays the same. 3 cases? I only found 2 ($B_i$ before or after $R_{i+1}$) I had case 1 which was the trivial one and then a case 2 but case 2 i split into sub cases 2.1,2.2,2.3. Am I right in saying you could do the cases a lot of different ways? i actually claimed constant-ness for all sub-arcs so i didn't have to deal with this oops

had a completely different solution than what's been posted, is it actually right?

I got a completely different solution is this valid

pi_kachu wrote: is this not just 2 choose 1? this is a USA(J)MO problem and most of these problems are proofs after all they give you 9 hours to do 6 problems(correct me if im wrong) so it shouldnt be as simple as a mathcounts question

Solved with jacoporizzo Lemma. Given $2n$ points in a circle, $n$ red and $n$ blue, it is possible to choose a blue point $X$ with the following property: when you trace clockwise from $X$ around the circle, the number of blue points seen (including $X$) is always at least the number of red points seen. Proof. Induct on $n$. We show that claim for $n=k+1$ is implied by the claim for $n=k$. Notice that we can always find a red point that is immediately clockwise from a blue point; else, all of the points must be blue or there are no blue points at all. Ignore these two points. Notice that the desired point $X$ for the $2k$ points remaining also works for the original $2k+2$ points! (When we trace clockwise from $X$, we will "hit" the blue point first, and then hit the red point.) [asy][asy] picture bdot; filldraw(bdot, circle((0,0),.15), lightblue); picture rdot; filldraw(rdot, circle((0,0),.15), red); int [] reds = {0, 1, 3, 6}; int [] blues = {2,4,5,7}; for(int i = 0; i<4; ++i){ add(shift(dir(reds[i]*45+22.5))*rdot); } for(int i = 0; i<4; ++i){ add(shift(dir(blues[i]*45+22.5))*bdot); } draw(arc((0,0),1,-100, -80)); label("$X$", dir(-112.5)); [/asy][/asy] Consider such a point $X$ on the original problem. The key property of $X$ is the following: no $R_iB_i$ arc intersects the smallest arc with $X$ as its clockwise-most point. Call this arc $\omega$. Label the points $X_0$, $X_1$, ... $X_{2n}$ with $X_0\equiv X$ and the $X_i$s going clockwise. We say that a point $X_i$ is in front of another point $X_j$ if $i<j$. Now, we label each red point $X_i$ with the following value $c_i$: the number of unpaired blue points in front of $X_i$ minus the number of unpaired red points in front of $X_i$. We claim that $c_i>0$ for each red point. The claim is obvious by the lemma for the original configuration, so we just show that it is preserved after each pairing. When we pair a red point $X_i$ with a blue point $X_j$ in front of it, this does not affect the $c$-value of any red point behind $X_i$. This also does not affect the $c$-value of any red point in front of $X_j$. Now, suppose that $X_k$ is a red point between $X_i$ and $X_j$. Then, $c_k\geq c_i +1$ since $X_k$ is in front of $X_i$ and by definition of pairings there is no blue point between $X_j$ and $X_i$. Since $X_k$ only goes down by $1$, it remains positive. This shows the claim. Now, we use this to show the "key property" of $X$ claimed earlier. Since the $c$-value of any red point remains positive the entire time, that means there is a blue point between that red point and $\omega$. Hence, the arc connecting the red point and its "clockwise-closest" blue point does not intersect $\omega$. This shows the key property. Finally, we show that this finishes the problem. Let the degree of an arc be the number of $R_iB_i$ arcs intersecting it. The degree of $X$, by the above property, is $0$. Now, notice that as we go counterclockwise around the circle, starting with arc $\omega$, the degree of the next small arc is one greater than the arc prior if the point in between them is red, else the degree of the next arc is one less than the arc prior if the point in between them is blue. Obviously, this uniquely determines the degree of each arc. Hence, the number of $R_iB_i$ arcs passing through $(1,0)$ is fixed. We're done.

very impressive solution @above

We proceed with strong induction. The base cases are trivial. Now suppose that the claim holds for $1,2,\cdots, n$. We prove it holds for $n+1$. Suppose we choose an arbitrary $R_1$ among the red points, which uniquely determines a $B_1$ among the blues. We will show the problem by showing that given any two orderings of the $R_i,$ the number of arcs that contain $(1,0)$ is constant. Case 1: The $R_1$ in the first ordering and the second ordering are the same. This case is trivial, as then the $B_1$ in both cases would be the same, and this would become the $n-1$ case(with the indices shifted up by 1) and by our inductive hypothesis, this is constant, regardless of whether $R_1B_1$ contains $(1,0)$ or not. Case 2: The $R_1$ in the first ordering and the second ordering are different. Case 2.1: While the $R_1$ in the first ordering and the second ordering are different, the $B_1$ are the same. In this case, we can remove the $R_1,B_1$ from both diagrams because they cannot be used anymore. Set $R_2$ in the first ordering as the $R_1$ in the second ordering and set the $R_2$ in the second ordering as the $R_1$ in the first ordering. Notice that this means that when the $B_1$(which are the same in both orderings) is removed, the next blue point moving counterclockwise from $B_1$ will be the $B_2$ of the $R_2$ in both arrangements. Therefore, we can remove these from the diagram too, and we are in the same $n-2$ case in both diagrams, thus this is constant. Case 2.2: The $R_1$ and $B_1$ in the first and second ordering are both different. In this case, notice we can just remove the $R_1, B_1$ from both diagrams because they cannot be used anymore. This becomes the $n-1$ case in both diagrams, so it does not matter what ordering $R_2, R_3\cdots$ we choose. Therefore, we can make $R_2$ in the first ordering equal to $R_1$ in the second ordering, which means that because the $B_1$ in the first ordering is not equal to the $B_1$ in the second ordering, that $B_2$ in the first ordering will now be equal to the $B_1$ in the second ordering. Similarly, we can make the $R_2$ in the second ordering equal to the $R_1$ in the first ordering and the $B_2$ as well. Regardless of whether these arcs pass through $(1,0),$ they are constant in both orderings, and both give the $n-2$ case, which by our strong inductive hypothesis, is constant, so we are done. Combining both cases 1 and 2, we have covered all cases, so we are done.

Let the depth of a particular point on the unit circle be the number of clockwise arcs of the form $R_i \to B_i$ that contain that point. Consider the following process. Start from $(1, 0)$ and move along the circle counterclockwise one full circle. During this, we will keep a counter $\ell$ that starts at $0$, increments by $1$ when we hit a red point, and decrements by $1$ when we hit a blue point. Let $P$ be a point where $\ell$ reaches its minimum. Now notice that if we start this process again but at $P$ and keep a counter $\ell'$ instead, $\ell'$ stays nonnegative. We claim that $\ell'$ is always equal to the depth, which solves the problem since $\ell'$ is clearly independent of the ordering of $R_1, R_2, \dots, R_n$. Proceed with induction on $n$. The base case $n=1$ is trivial. The points must be in counterclockwise order of $P, R_1, B_1$, and here $\ell'$ and the depth are $1$ between $R_1 \to B_1$ and $0$ otherwise. Now notice that inside $R_1 \to B_1$, $\ell'$ is at least $1$ since was at least $0$ before we crossed $R_1$ during the process, and there are no blue points between $R_1$ and $B_1$. Then, we may simply remove $R_1$ and $B_1$. This is simply the inductive hypothesis on $n-1$ since $\ell'$ is still always nonnegative, and furthermore the depth and $\ell'$ both decrease by $1$ inside $R_1 \to B_1$, so the fact that $\ell'$ and the depth are always the same still holds. Thus, our induction is complete, and we are done. $\blacksquare$

Behold! Ladies and gentlemen, I present to you, an 80 IQ solution. We'll rephrase the question since it's weirdly worded: Copied from #95 wrote: Let $\omega$ be a circle, and let $P_1,P_2,\ldots, P_{2n}$ be $2n$ distinct points on $\omega$. The coloring step is the same. Show that for any point $Q$ which is not equal to $P_i$ for any $1 \leq i \leq 2n$, the number of counterclockwise arcs of the form $R_i \to B_i$ that contain $Q$ does not depend on the choice of the ordering of the red points. Here's a sketch just to get an idea of the following solution. Sketch. 1. We show that there is a point $X\neq P_i$ such that the number of counterclockwise arcs is $0$ regardless of the ordering $R_1,\dots,R_n$. 2. Prove that for any point $Y\neq P_i$ the number of counterclockwise arcs through $Y$ is purely dependent on the number of points between $X$ and $Y$ and how many of them are red (or blue). Solution. Define $f(P)$ as the point adjacent to $P$ in the counterclockwise direction. Define $f^k(p)$ as $k$ times applying $f$ to $P$. Define $f^0(P)=P$. We assign a value of $1$ if the point is red, and $-1$ if the point is blue. Claim 1. There's a point $X$ such that $$\sum_{i = 0}^{j}f^{i}(X) \ge 0$$for all $j = 0,1, \dots, 2n-1$. Proof. We use strong induction. It's true for $2$ points. Assume that it's true for $2,\dots,2n$ points where $n\ge 1$. We show that it's true for $2n+2$ points. Start at any red point $F$. It's obvious that there exist a $k> 0$ such that $\sum_{i = 0}^{k}f^{i}(F) = 0$. Use the induction hypothesis on the remaining $2n+2 - (k+1) = \text{even}$ points, and we're done. $\blacksquare$. Claim 2. Define $X$ as in Claim 1. Then regardless of the ordering $R_1,\dots,R_n$, the number of counterclockwise arcs through $X$ is $0$. Proof. We use induction on the number of points. The base case is $2$ points which is trivial. Assume that it's true for $2n$ points where $n\ge 1$. Say we have $2n+2$ points. It's not hard to see that by the definition of $X$, the point adjacent to $X$ in the counterclockwise direction must be red, while the point adjacent to $X$ in the clockwise direction must be blue. Thus the arc $R_1B_1$ doesn't go through $X$, so by removing the two points and applying the induction hypothesis to the remaining $2n$ points and adding back $R_1,B_1$, the $2n+2$ works. $\blacksquare$. Claim 3. Define $Y = (1,0)$ and $X$ as in Claim 1. Define $A$ as the number of red points between $Y$ and $X$ in the counterclockwise direction starting from $X$. Define $B$ as the number of blue points between $Y$ and $X$ in the counterclockwise direction starting from $X$. Then the number of arcs through $Y$ is $B-A$. Proof. Since there is no counterclockwise arc through $X$, the number of arcs though $Y$ is $B-A$ since we need to "neutralize" the red points.

Keep a running total, starting from $(1,0)$ and moving counterclockwise, where we add by $1$ if we hit a red point and subtract by $1$ if we reach a blue point. Let $x$ be the lowest number ever written. Claim: The number of such arcs is $\boxed{-x}$ (finishes). Proof: We proceed by induction on $n$ (base cases are obvious). If the arc $R_1\to B_1$ does not contain $(1,0)$, then we can just delete those two points as it does not affect $x$, since there are no blue points in between them. This is the $n-1$ case, which works by the induction hypothesis. If the arc $R_1\to B_1$ does contain $(1,0)$, then if we delete the points, then $x$ will increase to $x+1$. Now we are at a $n-1$ case, so the number of arcs mentioned in the problem is just $-x-1$, so if we include $R_1$ and $B_1$ again, the number of total such arcs is $-x$, as desired. $\blacksquare$

Let $i$ be good if the arc $R_i\to B_i$ contains $(1,0)$, and bad otherwise. Suppose we swap $R_i$ and $R_{i+1}$, where $1\le i\le n-1$. First, we deal with the case $i>1$. For $1\le j\le i-1$ and $i+2\le j\le n$, the goodness of $j$ is unchanged. Then we just need to show that the goodness of $i$ and $i+1$ are unchanged. If $i$ and $i+1$ are both good before the swap, then afterwards $i$ and $i+1$ are both good. If $i$ is good and $i+1$ is bad before the swap, then afterwards $i$ is good and $i+1$ is bad. If $i$ is bad and $i+1$ is good before the swap, then afterwards $i$ is bad and $i+1$ is good. If $i$ is bad and $i+1$ is bad before the swap, then afterwards $i$ is bad and $i+1$ is bad. Then, since transpositions generate the symmetric group, we're done.

Call such arcs containing $(1,0)$ good arcs .If ordering does not matter, then swapping any two red points does not matter. The simpliest case is swapping neighbour points. Hence it motivates us to our claim. ( Note that indices are taken $ \mod n$) Claim . $R{i} \leftrightarrow R_{i+1}$ does not change number of good arcs. We have $3$ cases: 0,1,2 of blue points lies on arc $ R_i,R_{i+1}$. In either cases, coloring the arcs $R_iB_i, R_{i+1}B_{i+1} $ or $R_{i+1}B_i,R_iB_{i+1}$ that occupies the circle does not change, hence the conclusion. ( Note that there are no extra blue points in these arcs), hence conclusion. $\square$ Now, it is obvious that we can make any permutations by using our claim, hence we are done

Start at the point $(1,0)$ and work clockwise. Maintain the number $r$ red dots you see, and the number $b$ blue dots you see. I claim the answer is the maximum value of $r-b$. We proceed with contradiction: FTSOC, assume the answer $a$ is less than $r-b$. Then at the location where we achieve the maximum of $r-b$, there is a way to have fewer than $r-b$ arcs hitting $(1,0)$. However, this means that there are more than $r-(r-b)=b$ blue points between this point and $(1,0)$ a contradiction. FTSOC assume the answer $a$ is more than $r-b$. Then, at the location where we achieve the maximum of $r-b$, there is a way to have more than $r-b$ arcs hitting $(1,0)$. Note that there can be no arc containing a red point before where we achieve the maximum passing through $(1,0)$ as $r-b$ is the maximum such value. This implies that the number of red points is strictly greater than the number of blue points $b$ plus the number of arcs passing through $(1,0)$, which is more than $r-b$, so there are strictly more than $r-b+b=r$ red points from this point to $(1,0)$, a contradiction. Since $r-b$ doesn't depend on the ordering, we are done.

Here's the intuitive local solution. The idea is that when we swap the points $R_i$ and $R_{i+1}$, the number of arcs containing any point on the circumference remains the same. This follows by checking two main cases (if the red and blue points appear alternating, or if they appear together.) We will check just one of them; the other one follows similarly. In the case where the points $R_{i+1}, R_i, B_i, B_{i+1}$ appear in this order, notice that upon swapping $R_i$ and $R_{i+1}$, the arrow from $R_i$ points to the first available blue point, which must be $B_i$. (If there existed another blue point with index greater than $i$ on the arc $\widehat{R_{i+1}R_i}$, $R_{i+1}$ would have pointed to that point in the original setup; similar case for $\widehat{R_iB_i}$.) Similarly, the arrow from $R_{i+1}$ must also point to $B_{i+1}$. Hence one can notice that every point on the circumference is covered the same number of times before and after the swap. Now, notice that we can get from any permutation of indexes to a certain permutation via such a sequence of swaps, which implies the problem in the result.

Using a bubble sort algorithm we can prove that any ordering of red points can be reached only by swapping labels of pairs of red points. (You actually need not prove bubble sort but I did it in my full proof anyways). Then by considering cases for other points (depending on its relative position to the 2 swapped red points), we can get that swapping labels of any pair of red points makes the answer invariant So the answer is always invariant Full proof here: https://infinityintegral.substack.com/p/usajmo-2017-contest-review

We claim that the multiset of covered points by the $n$ counterclockwise arcs will remain fixed, which evidently finishes. Consider the outcome of swapping $R_k$ and $R_{k+1}$. Note that the new corresponding blue points will be the original $B_k$ and $B_{k+1}$ in some order, and all other arcs are fixed. There are only 3 scenarios for the result of this swap, none of which change the multiset, as desired. It remains to show that each configuration is obtainable from another through these swaps. This is easy, as we can always reach a position where $R_1 \ldots R_n$ are in counterclockwise order by first swapping $R_1$ to the "front", then $R_2$ behind $R_1$, and so on. $\blacksquare$

I think I have the worst solution. Let the counter-clockwise arcs in the form $R_i \to B_i$ be strings. We place a duck on the circle, which waddles counterclockwise. The duck initially has a score of zero, and every time the duck passes a red point, it adds $1$ to its score, and every time it passes a blue point it subtracts $1$ to its score. Note that by the truck lemma, there is an initial arc where the score of the duck will always remain non-negative while waddling around the circle, we will call such a path nice. Note that in all nice paths, the score is constant while walking along an arc. Let this constant be the "waddling number" of the arc. Claim: Waddling number is constant. given some arc $a$, the score of the duck as it walks across $a$ is the same for all paths where the duck's score is always non-negative. Let $A$ and $B$ be two points for which if the duck starts on that point, the resulting path will be nice. It is sufficient to show that if the duck starts at point $A$, its score will be $0$ at point $B$. Indeed, assume its score is $k>0$ at point $B$. This implies on the counter-clockwise arc $B \to A$ there are $k$ more blue points than red points. This implies that if the duck starts waddling at $B$, then its score will be $-k$ at $A$, which contradicts the path is nice. $\square$ Claim: The number of strings covering the arc is always equal to the waddling number, regardless of the initial numbering. First, we claim that some arc is covered by $0$ strings. Indeed, note that by the problem condition, given any two overlapping strings, one must entirely contain the other, call a set of overlapping strings a stack. Now, assume that every arc is covered by a string, notice that every blue point removes the smallest point from the stack. But, since there is at least one string covering each arc, this would imply that some string wraps around the whole circle. Thus, let that arc with $0$ strings be $a$. Note that if we start at $a$ and start moving counterclockwise, every time we pass over a red point the number of strings we are on increases by one, and blue points decrease by $1$. This is equivalent to the waddling number. $\square$ Since the waddling number is fixed over all numbering, we conclude the problem. $\blacksquare$