2017 USAMO Problems/Problem 4
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