2017 USAMO Problems/Problem 4

Problem

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

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

Page

Toolbox

Search

2017 USAMO Problems/Problem 4

Problem

Solution