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"

(→‎See also)
(→‎Solution)
Line 3: Line 3:
  
 
==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 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</math>
 +
<math>B_2BRR_2</math>
 +
<math>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>
  
−
{{MAA Notice}}
+
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>A</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> or <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>.
 +
 
 +
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, 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>. 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>. In addition, 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
 +
(Sorry for terrible solution, comments are welcome)
  
 
==See also==
 
==See also==
 
{{USAJMO newbox|year=2017|num-b=2|aftertext=|after=Last Problem}}
 
{{USAJMO newbox|year=2017|num-b=2|aftertext=|after=Last Problem}}

Revision as of 07:17, 22 April 2017

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 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$ $B_2BRR_2$ $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 $A$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$ or $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)$.

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, so $j=0$. Note that this arc does intersect $(1,0)$, and $R_1$ must be a terminating $R$. 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)$. In addition, 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 (Sorry for terrible solution, comments are welcome)

See also

2017 USAJMO (Problems • Resources)
Preceded by
Problem 2 		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=85365"