Difference between revisions of "2017 USAJMO Problems/Problem 6"
William122 (talk | contribs) (→Solution) |
William122 (talk | contribs) (→Solution) |
||
Line 5: | Line 5: | ||
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. | 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: | 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>BBR_1RRB_1\imply B_2BRR_2\imply 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> | 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> |
Revision as of 08:17, 22 April 2017
Problem
Let be
distinct points on the unit circle
other than
. Each point is colored either red or blue, with exactly
of them red and exactly
of them blue. 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
traveling counterclockwise around the circle from
, and so on, until we have labeled all 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 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:
$BBR_1RRB_1\imply B_2BRR_2\imply B_3R_3$ (Error compiling LaTeX. Unknown error_msg)
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
or
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, so
. Note that this arc does intersect
, and
must be a terminating
. 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
. In addition, 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 (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 |