Difference between revisions of "2017 USAMO Problems/Problem 4"
(Created page with "==Problem== Let <math>P_1</math>, <math>P_2</math>, <math>\dots</math>, <math>P_{2n}</math> be <math>2n</math> distinct points on the unit circle <math>x^2+y^2=1</math>, other...") |
(→Problem) |
||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
Let <math>P_1</math>, <math>P_2</math>, <math>\dots</math>, <math>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> red points and <math>n</math> blue points. Let <math>R_1</math>, <math>R_2</math>, <math>\dots</math>, <math>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> travelling counterclockwise around the circle from <math>R_2</math>, and so on, until we have labeled all of the blue points <math>B_1, \dots, B_n</math>. Show that the number of counterclockwise arcs of the form <math>R_i \to B_i</math> that contain the point <math>(1,0)</math> is independent of the way we chose the ordering <math>R_1, \dots, R_n</math> of the red points. | Let <math>P_1</math>, <math>P_2</math>, <math>\dots</math>, <math>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> red points and <math>n</math> blue points. Let <math>R_1</math>, <math>R_2</math>, <math>\dots</math>, <math>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> travelling counterclockwise around the circle from <math>R_2</math>, and so on, until we have labeled all of the blue points <math>B_1, \dots, B_n</math>. Show that the number of counterclockwise arcs of the form <math>R_i \to B_i</math> that contain the point <math>(1,0)</math> is independent of the way we chose the ordering <math>R_1, \dots, R_n</math> of the red points. | ||
+ | |||
+ | ==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>. | ||
+ | |||
+ | 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 |
Revision as of 16:02, 22 December 2017
Problem
Let ,
,
,
be
distinct points on the unit circle
, other than
. Each point is colored either red or blue, with exactly
red points and
blue points. Let
,
,
,
be any ordering of the red points. Let
be the nearest blue point to
traveling counterclockwise around the circle starting from
. Then let
be the nearest of the remaining blue points to
travelling counterclockwise around the circle from
, and so on, until we have labeled all of the blue points
. Show that the number of counterclockwise arcs of the form
that contain the point
is independent of the way we chose the ordering
of the red points.
Solution
I define a sequence to be, starting at and tracing the circle counterclockwise, and writing the color of the points in that order - either R or B. For example, possible sequences include
,
,
,
, etc. Note that choosing an
is equivalent to choosing an
in a sequence, and
is defined as the
closest to
when moving rightwards. If no
s exist to the right of
, start from the far left. For example, if I have the above example
, and I define the 2nd
to be
, then the first
will be
. Because no
or
can be named twice, I can simply remove
and
from my sequence when I choose them. I define this to be a move. Hence, a possible move sequence of
is:
Note that, if, in a move, appears to the left of
, then
intersects
Now, I define a commencing to be a
which appears to the left of all
s, and a terminating
to be a
which appears to the right of all
s. Let the amount of commencing
s be
, and the amount of terminating
s be
, I claim that the number of arcs which cross
is constant, and it is equal to
. I will show this with induction.
Base case is when . In this case, there are only two possible sequences -
and
. In the first case,
does not cross
, but both
and
are
, so
. In the second example,
,
, so
.
crosses
since
appears to the left of
, so there is one arc which intersects. Hence, the base case is proved.
For the inductive step, suppose that for a positive number , the number of arcs which cross
is constant, and given by
for any configuration. Now, I will show it for
.
Suppose I first choose such that
is to the right of
in the sequence. This implies that
does not cross
. But, neither
nor
is a commencing
or terminating
. These numbers remain constant, and now after this move we have a sequence of length
. Hence, by assumption, the total amount of arcs is
.
Now suppose that appears to the right of
, but
is not a commencing
. This implies that there are no commencing
s in the series, because there are no
s to the left of
, so
. Note that this arc does intersect
, and
must be a terminating
.
must be a terminating
because there are no
s to the right of
, or else that
would be
. The
length sequence that remains has
commencing
s and
terminating
s. Hence, by assumption, the total amount of arcs is
.
Finally, suppose that appears to the right of
, and
is a commencing
. We know that this arc will cross
. Analogous to the previous case,
is a terminating
, so the
length sequence which remains has
commencing
s and
terminating
s. Hence, by assumption, the total amount of arcs is
.
There are no more possible cases, hence the induction is complete, and the number of arcs which intersect is indeed a constant which is given by
.
-william122