Red and blue points

The post below has been deleted. Click to close.

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

6857 posts

#1 h Apr 20, 2017, 11:03 PM • 18 Y

Y by Generic_Username, artsolver, anantmudgal09, DaniyalQazi2, Davi-8191, Wizard_32, rashah76, OlympusHero, itslumi, v4913, HamstPan38825, hamburgerwhizz, samrocksnature, suvamkonar, Jc426, megarnie, diegoca1, Adventure10

Let $P_1$ , $P_2$ , $\dots$ , $P_{2n}$ be $2n$ distinct points on the unit circle $x^2+y^2=1$ , other than $(1,0)$ . Each point is colored either red or blue, with exactly $n$ red points and $n$ blue points. Let $R_1$ , $R_2$ , $\dots$ , $R_n$ be any ordering of the red points. Let $B_1$ be the nearest blue point to $R_1$ traveling counterclockwise around the circle starting from $R_1$ . Then let $B_2$ be the nearest of the remaining blue points to $R_2$ travelling counterclockwise around the circle from $R_2$ , and so on, until we have labeled all of the blue points $B_1, \dots, B_n$ . Show that the number of counterclockwise arcs of the form $R_i \to B_i$ that contain the point $(1,0)$ is independent of the way we chose the ordering $R_1, \dots, R_n$ of the red points.

This post has been edited 3 times. Last edited by DPatrick, Apr 20, 2017, 11:13 PM
Reason: minor LaTeX fix

Z K Y

The post below has been deleted. Click to close.

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

hamup1

380 posts

hamup1

#2 h Apr 20, 2017, 11:04 PM • 1 Y

Y by Adventure10

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.

This post has been edited 1 time. Last edited by hamup1, Apr 22, 2017, 12:09 AM
Reason: updating

Z K Y

The post below has been deleted. Click to close.

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

DrMath

2130 posts

DrMath

#3 h Apr 20, 2017, 11:04 PM • 7 Y

Y by FlakeLCR, canhhoang30011999, WorshipDrMath, myh2910, megarnie, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6857 posts

v_Enhance

#4 h Apr 20, 2017, 11:04 PM • 17 Y

Y by nosaj, mathtastic, fz0718, sicilianfan, Generic_Username, JasperL, A_Math_Lover, Cindy.tw, myh2910, v4913, HamstPan38825, hamburgerwhizz, suvamkonar, Jc426, Adventure10, Mango247, GeoKing

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

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

This post has been edited 2 times. Last edited by v_Enhance, Apr 21, 2017, 2:55 PM

Z K Y

The post below has been deleted. Click to close.

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

Generic_Username

1088 posts

Generic_Username

#5 h Apr 20, 2017, 11:04 PM • 2 Y

Y by Adventure10, Mango247

wait does extremal work

Z K Y

The post below has been deleted. Click to close.

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

zephyrcrush78

389 posts

zephyrcrush78

#6 h Apr 20, 2017, 11:05 PM • 2 Y

Y by Adventure10, Mango247

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

This post has been edited 1 time. Last edited by zephyrcrush78, Apr 20, 2017, 11:05 PM

Z K Y

The post below has been deleted. Click to close.

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

Generic_Username

1088 posts

Generic_Username

#7 h Apr 20, 2017, 11:06 PM • 1 Y

Y by Adventure10

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

Z K Y

The post below has been deleted. Click to close.

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

amplreneo

947 posts

amplreneo

#8 h Apr 20, 2017, 11:06 PM • 1 Y

Y by Adventure10

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

Z K Y

The post below has been deleted. Click to close.

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

mathguy623

1855 posts

mathguy623

#9 h Apr 20, 2017, 11:08 PM • 2 Y

Y by Adventure10, Mango247

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.

This post has been edited 1 time. Last edited by mathguy623, Apr 20, 2017, 11:09 PM

Z K Y

The post below has been deleted. Click to close.

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

atmchallenge

980 posts

atmchallenge

#10 h Apr 20, 2017, 11:08 PM • 2 Y

Y by Adventure10, Mango247

Basically same, maybe different cases though?
My Solution

Z K Y

The post below has been deleted. Click to close.

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

thedoge

626 posts

thedoge

#11 h Apr 20, 2017, 11:08 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

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

UrInvalid

627 posts

UrInvalid

#12 h Apr 20, 2017, 11:09 PM • 2 Y

Y by Adventure10, Mango247

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}$ )

Z K Y

The post below has been deleted. Click to close.

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

hamup1

380 posts

hamup1

#13 h Apr 20, 2017, 11:09 PM • 2 Y

Y by Adventure10, Mango247

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?

Z K Y

The post below has been deleted. Click to close.

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

mathguy623

1855 posts

mathguy623

#14 h Apr 20, 2017, 11:11 PM • 2 Y

Y by Adventure10, Mango247

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?

Z K Y

The post below has been deleted. Click to close.

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

mathgenius64

1332 posts

mathgenius64

#15 h Apr 20, 2017, 11:11 PM • 2 Y

Y by Adventure10, Mango247

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.

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

#100 h Apr 1, 2021, 11:13 PM • 1 Y

Y by jacoporizzo

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

This post has been edited 1 time. Last edited by PROA200, Apr 1, 2021, 11:13 PM

Z K Y

The post below has been deleted. Click to close.

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

631558

783 posts

631558

#101 h Apr 1, 2021, 11:58 PM

Y by

very impressive solution @above

Z K Y

The post below has been deleted. Click to close.

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

JustKeepRunning

2958 posts

JustKeepRunning

#102 h Apr 7, 2021, 3:13 PM • 3 Y

Y by Mango247, Mango247, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

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

Vitriol

113 posts

Vitriol

#103 h Apr 10, 2021, 2:06 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

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

Afo

1002 posts

Afo

#104 h Oct 25, 2021, 3:00 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

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

megarnie

5531 posts

megarnie

#105 h Feb 11, 2022, 3:34 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

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

jasperE3

11091 posts

jasperE3

#106 h Mar 30, 2022, 3:37 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

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

Iora

194 posts

Iora

#107 h Oct 29, 2022, 12:14 PM • 1 Y

Y by Mango247

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

Z K Y

The post below has been deleted. Click to close.

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

bever209

1522 posts

bever209

#108 h Mar 13, 2023, 9:28 PM

Y by

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.

This post has been edited 1 time. Last edited by bever209, Mar 13, 2023, 9:41 PM

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8844 posts

HamstPan38825

#109 h Aug 27, 2023, 2:50 PM

Y by

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.

This post has been edited 1 time. Last edited by HamstPan38825, Aug 27, 2023, 2:50 PM

Z K Y

The post below has been deleted. Click to close.

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

Infinity_Integral

306 posts

Infinity_Integral

#110 h Sep 10, 2023, 1:40 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

787 posts

shendrew7

#111 h Jan 10, 2024, 10:37 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

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

blackbluecar

302 posts

blackbluecar

#112 h Jan 18, 2024, 3:57 AM • 1 Y

Y by IAmTheHazard

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$

Z K Y

The post below has been deleted. Click to close.

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