Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2017 USAJMO Problems/Problem 6"

(Created page with "==Problem== Let <math>P_1, \ldots, P_{2n}</math> be <math>2n</math> distinct points on the unit circle <math>x^2 + y^2 = 1</math> other than <math>(1,0)</math>. Each point is...")
 
(redirect 2017 USAMO #4 here as well)
 
(17 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 +
{{duplicate|[[2017 USAJMO Problems/Problem 6|2017 USAJMO #6]] and [[2017 USAMO Problems/Problem 4|2017 USAMO #4]]}}
 +
 
==Problem==
 
==Problem==
 
Let <math>P_1, \ldots, P_{2n}</math> be <math>2n</math> distinct points on the unit circle <math>x^2 + y^2 = 1</math> other than <math>(1,0)</math>. Each point is colored either red or blue, with exactly <math>n</math> of them red and exactly <math>n</math> of them blue. Let <math>R_1, \ldots, R_n</math> be any ordering of the red points. Let <math>B_1</math> be the nearest blue point to <math>R_1</math> traveling counterclockwise around the circle starting from <math>R_1</math>. Then let <math>B_2</math> be the nearest of the remaining blue points to <math>R_2</math> traveling counterclockwise around the circle from <math>R_2</math>, and so on, until we have labeled all the blue points <math>B_1, \ldots, B_n</math>. Show that the number of counterclockwise arcs of the form <math>R_i \rightarrow B_i</math> that contain the point <math>(1,0)</math> is independent of the way we chose the ordering <math>R_1, \ldots, R_n</math> of the red points.  
 
Let <math>P_1, \ldots, P_{2n}</math> be <math>2n</math> distinct points on the unit circle <math>x^2 + y^2 = 1</math> other than <math>(1,0)</math>. Each point is colored either red or blue, with exactly <math>n</math> of them red and exactly <math>n</math> of them blue. Let <math>R_1, \ldots, R_n</math> be any ordering of the red points. Let <math>B_1</math> be the nearest blue point to <math>R_1</math> traveling counterclockwise around the circle starting from <math>R_1</math>. Then let <math>B_2</math> be the nearest of the remaining blue points to <math>R_2</math> traveling counterclockwise around the circle from <math>R_2</math>, and so on, until we have labeled all the blue points <math>B_1, \ldots, B_n</math>. Show that the number of counterclockwise arcs of the form <math>R_i \rightarrow B_i</math> that contain the point <math>(1,0)</math> is independent of the way we chose the ordering <math>R_1, \ldots, R_n</math> of the red points.  
  
 
==Solution==
 
==Solution==
 +
I define a sequence to be, starting at <math>(1,0)</math> and tracing the circle counterclockwise, and writing the color of the points in that order - either R or B. For example, possible sequences include <math>RB</math>, <math>RBBR</math>, <math>BBRRRB</math>, <math>BRBRRBBR</math>, etc.
 +
Note that choosing an <math>R_1</math> is equivalent to choosing an <math>R</math> in a sequence, and <math>B_1</math> is defined as the <math>B</math> closest to <math>R_1</math> when moving rightwards. If no <math>B</math>s exist to the right of <math>R_1</math>, start from the far left. For example, if I have the above example <math>RBBR</math>, and I define the 2nd <math>R</math> to be <math>R_1</math>, then the first <math>B</math> will be <math>B_1</math>. Because no <math>R</math> or <math>B</math> can be named twice, I can simply remove <math>R_1</math> and <math>B_1</math> from my sequence when I choose them. I define this to be a move. Hence, a possible move sequence of <math>BBRRRB</math> is:
 +
<math>BBR_1RRB_1\implies B_2BRR_2\implies B_3R_3</math>
 +
---------
 +
Note that, if, in a move, <math>B_n</math> appears to the left of <math>R_n</math>, then <math>\stackrel{\frown}{R_nB_n}</math> intersects <math>(1,0)</math>
 +
 +
Now, I define a commencing <math>B</math> to be a <math>B</math> which appears to the left of all <math>R</math>s, and a terminating <math>R</math> to be a <math>R</math> which appears to the right of all <math>B</math>s. Let the amount of commencing <math>B</math>s be <math>j</math>, and the amount of terminating <math>R</math>s be <math>k</math>, I claim that the number of arcs which cross <math>(1,0)</math> is constant, and it is equal to <math>\text{max}(j,k)</math>. I will show this with induction.
 +
 +
Base case is when <math>n=1</math>. In this case, there are only two possible sequences - <math>RB</math> and <math>BR</math>. In the first case, <math>\stackrel{\frown}{R_1B_1}</math> does not cross <math>(1, 0)</math>, but both <math>j</math> and <math>k</math> are <math>0</math>, so <math>\text{max}(j,k)=0</math>. In the second example, <math>j=1</math>, <math>k=1</math>, so <math>\text{max}(j,k)=1</math>. <math>\stackrel{\frown}{R_1B_1}</math> crosses <math>(1,0)</math> since <math>B_1</math> appears to the left of <math>R_1</math>, so there is one arc which intersects. Hence, the base case is proved.
 +
 +
For the inductive step, suppose that for a positive number <math>n</math>, the number of arcs which cross <math>(1,0)</math> is constant, and given by <math>\text{max}(j, k)</math> for any configuration. Now, I will show it for <math>n+1</math>.
 +
 +
Suppose I first choose <math>R_1</math> such that <math>B_1</math> is to the right of <math>R_1</math> in the sequence. This implies that <math>\stackrel{\frown}{R_1B_1}</math> does not cross <math>(1,0)</math>. But, neither <math>R_1</math> nor <math>B_1</math> is a commencing <math>B</math> or terminating <math>R</math>. These numbers remain constant, and now after this move we have a sequence of length <math>2n</math>. Hence, by assumption, the total amount of arcs is <math>0+\text{max}(j,k)=\text{max}(j,k)</math>.
 +
 +
-------------------------
 +
*Here is a counter-case. <math>BRR_{1}B_{1}RR</math> : j = 1, k = 2 => <math>BRRR</math> : j = 1, k = 3. These numbers may not remain constant.
 +
Thus, this solution probably doesn't work.
 +
-------------------------
 +
 +
Now suppose that <math>R_1</math> appears to the right of <math>B_1</math>, but <math>B_1</math> is not a commencing <math>B</math>. This implies that there are no commencing <math>B</math>s in the series, because there are no <math>B</math>s to the left of <math>B_1</math>, so <math>j=0</math>. Note that this arc does intersect <math>(1,0)</math>, and <math>R_1</math> must be a terminating <math>R</math>. <math>R_1</math> must be a terminating <math>R</math> because there are no <math>B</math>s to the right of <math>R_1</math>, or else that <math>B</math> would be <math>B_1</math>. The <math>2n</math> length sequence that remains has <math>0</math> commencing <math>B</math>s and <math>k-1</math> terminating <math>R</math>s. Hence, by assumption, the total amount of arcs is <math>1+\text{max}(0,k-1)=1+k-1=k=\text{max}(j,k)</math>.
 +
 +
Finally, suppose that <math>R_1</math> appears to the right of <math>B_1</math>, and <math>B_1</math> is a commencing <math>B</math>. We know that this arc will cross <math>(1,0)</math>. Analogous to the previous case, <math>R_1</math> is a terminating <math>R</math>, so the <math>2n</math> length sequence which remains has <math>j-1</math> commencing <math>B</math>s and <math>k-1</math> terminating <math>R</math>s. Hence, by assumption, the total amount of arcs is <math>1+\text{max}(j-1,k-1)=1+\text{max}(j,k)-1=\text{max}(j,k)</math>.
 +
 +
There are no more possible cases, hence the induction is complete, and the number of arcs which intersect <math>(1,0)</math> is indeed a constant which is given by <math>\text{max}(j,k)</math>.
 +
 +
-william122
 +
 +
==Solution 2==
 +
Lemma: If we switch the ordering of two consecutive <math>R_k</math>, <math>R_{k+1}</math>, the number of arcs crossing <math>(1,0)</math> stays invariant.
 +
 +
Proof: There are two situations. If the two arcs don't cross this is simple because the actual arcs stay the same, and only the number order of the arcs change. Otherwise, if <math>B_k</math> is to the left of <math>R_{k+1}</math>, the two arcs will have some overlap. The order of the points counterclockwise must be RRBB or some rotation of it. Notice how in both the old and the new ordering, the arc between the second R and the first B is counted twice and the arcs between the same colors are only counted once. Thus no matter where <math>(1,0)</math> is the number of arcs containing it will stay invariant.
 +
 +
Lemma 2: We can swap the place of any two points <math>R_i</math> and <math>R_j</math> while keeping the number of crossings invariant.
 +
 +
Proof: By Lemma 1 we can use consecutive arc moves to swap <math>R_i</math> with <math>R_{i+1}</math>, then the new <math>R_{i+1}</math> with <math>R_{i+2}</math> and so on until it swaps with <math>R_j</math>. Now, we can do the reverse swaps to move the new <math>R_{j-1}</math> to <math>R_{j-2}</math>, and so on into the original position of <math>R_i</math>. Since the other points were moved once in one direction and once in the opposite, all the other points are kept in place.
 +
 +
Now, let <math>I</math> be the sequence where <math>R_1</math> through <math>R_n</math> is numbered counterclockwise. We show that any ordering has the same number of crossings as <math>I</math>. We can swap the current place of <math>R_1</math> with the desired position in <math>I</math>. Now we can ignore <math>R_1</math> and swap the currrent place of <math>R_2</math> with the place of <math>R_2</math> in <math>I</math>, and so on until all the points are in the desired position. Thus, all orderings of <math>R_1</math> to <math>R_n</math> have the same number of crossings as <math>I</math>.
 +
 +
-tigershark22
 +
 +
==See also==
 +
{{USAJMO newbox|year=2017|num-b=5|aftertext=|after=Last Problem}}

Latest revision as of 11:20, 24 October 2024

The following problem is from both the 2017 USAJMO #6 and 2017 USAMO #4, so both problems redirect to this page.

Problem

Let $P_1, \ldots, 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$ of them red and exactly $n$ of them blue. Let $R_1, \ldots, 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$ traveling counterclockwise around the circle from $R_2$, and so on, until we have labeled all the blue points $B_1, \ldots, B_n$. Show that the number of counterclockwise arcs of the form $R_i \rightarrow B_i$ that contain the point $(1,0)$ is independent of the way we chose the ordering $R_1, \ldots, R_n$ of the red points.

Solution

I define a sequence to be, starting at $(1,0)$ and tracing the circle counterclockwise, and writing the color of the points in that order - either R or B. For example, possible sequences include $RB$, $RBBR$, $BBRRRB$, $BRBRRBBR$, etc. Note that choosing an $R_1$ is equivalent to choosing an $R$ in a sequence, and $B_1$ is defined as the $B$ closest to $R_1$ when moving rightwards. If no $B$s exist to the right of $R_1$, start from the far left. For example, if I have the above example $RBBR$, and I define the 2nd $R$ to be $R_1$, then the first $B$ will be $B_1$. Because no $R$ or $B$ can be named twice, I can simply remove $R_1$ and $B_1$ from my sequence when I choose them. I define this to be a move. Hence, a possible move sequence of $BBRRRB$ is: $BBR_1RRB_1\implies B_2BRR_2\implies B_3R_3$

Note that, if, in a move, $B_n$ appears to the left of $R_n$, then $\stackrel{\frown}{R_nB_n}$ intersects $(1,0)$

Now, I define a commencing $B$ to be a $B$ which appears to the left of all $R$s, and a terminating $R$ to be a $R$ which appears to the right of all $B$s. Let the amount of commencing $B$s be $j$, and the amount of terminating $R$s be $k$, I claim that the number of arcs which cross $(1,0)$ is constant, and it is equal to $\text{max}(j,k)$. I will show this with induction.

Base case is when $n=1$. In this case, there are only two possible sequences - $RB$ and $BR$. In the first case, $\stackrel{\frown}{R_1B_1}$ does not cross $(1, 0)$, but both $j$ and $k$ are $0$, so $\text{max}(j,k)=0$. In the second example, $j=1$, $k=1$, so $\text{max}(j,k)=1$. $\stackrel{\frown}{R_1B_1}$ crosses $(1,0)$ since $B_1$ appears to the left of $R_1$, so there is one arc which intersects. Hence, the base case is proved.

For the inductive step, suppose that for a positive number $n$, the number of arcs which cross $(1,0)$ is constant, and given by $\text{max}(j, k)$ for any configuration. Now, I will show it for $n+1$.

Suppose I first choose $R_1$ such that $B_1$ is to the right of $R_1$ in the sequence. This implies that $\stackrel{\frown}{R_1B_1}$ does not cross $(1,0)$. But, neither $R_1$ nor $B_1$ is a commencing $B$ or terminating $R$. These numbers remain constant, and now after this move we have a sequence of length $2n$. Hence, by assumption, the total amount of arcs is $0+\text{max}(j,k)=\text{max}(j,k)$.

  • Here is a counter-case. $BRR_{1}B_{1}RR$ : j = 1, k = 2 => $BRRR$ : j = 1, k = 3. These numbers may not remain constant.

Thus, this solution probably doesn't work.

Now suppose that $R_1$ appears to the right of $B_1$, but $B_1$ is not a commencing $B$. This implies that there are no commencing $B$s in the series, because there are no $B$s to the left of $B_1$, so $j=0$. Note that this arc does intersect $(1,0)$, and $R_1$ must be a terminating $R$. $R_1$ must be a terminating $R$ because there are no $B$s to the right of $R_1$, or else that $B$ would be $B_1$. The $2n$ length sequence that remains has $0$ commencing $B$s and $k-1$ terminating $R$s. Hence, by assumption, the total amount of arcs is $1+\text{max}(0,k-1)=1+k-1=k=\text{max}(j,k)$.

Finally, suppose that $R_1$ appears to the right of $B_1$, and $B_1$ is a commencing $B$. We know that this arc will cross $(1,0)$. Analogous to the previous case, $R_1$ is a terminating $R$, so the $2n$ length sequence which remains has $j-1$ commencing $B$s and $k-1$ terminating $R$s. Hence, by assumption, the total amount of arcs is $1+\text{max}(j-1,k-1)=1+\text{max}(j,k)-1=\text{max}(j,k)$.

There are no more possible cases, hence the induction is complete, and the number of arcs which intersect $(1,0)$ is indeed a constant which is given by $\text{max}(j,k)$.

-william122

Solution 2

Lemma: If we switch the ordering of two consecutive $R_k$, $R_{k+1}$, the number of arcs crossing $(1,0)$ stays invariant.

Proof: There are two situations. If the two arcs don't cross this is simple because the actual arcs stay the same, and only the number order of the arcs change. Otherwise, if $B_k$ is to the left of $R_{k+1}$, the two arcs will have some overlap. The order of the points counterclockwise must be RRBB or some rotation of it. Notice how in both the old and the new ordering, the arc between the second R and the first B is counted twice and the arcs between the same colors are only counted once. Thus no matter where $(1,0)$ is the number of arcs containing it will stay invariant.

Lemma 2: We can swap the place of any two points $R_i$ and $R_j$ while keeping the number of crossings invariant.

Proof: By Lemma 1 we can use consecutive arc moves to swap $R_i$ with $R_{i+1}$, then the new $R_{i+1}$ with $R_{i+2}$ and so on until it swaps with $R_j$. Now, we can do the reverse swaps to move the new $R_{j-1}$ to $R_{j-2}$, and so on into the original position of $R_i$. Since the other points were moved once in one direction and once in the opposite, all the other points are kept in place.

Now, let $I$ be the sequence where $R_1$ through $R_n$ is numbered counterclockwise. We show that any ordering has the same number of crossings as $I$. We can swap the current place of $R_1$ with the desired position in $I$. Now we can ignore $R_1$ and swap the currrent place of $R_2$ with the place of $R_2$ in $I$, and so on until all the points are in the desired position. Thus, all orderings of $R_1$ to $R_n$ have the same number of crossings as $I$.

-tigershark22

See also

2017 USAJMO (Problems • Resources)
Preceded by
Problem 5 		Last Problem
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_USAJMO_Problems/Problem_6&oldid=230531"