Difference between revisions of "2017 USAJMO Problems/Problem 6"
William122 (talk | contribs) m (→Solution) |
William122 (talk | contribs) (→Solution) |
||
Line 9: | Line 9: | ||
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> | ||
− | 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> | + | 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. | 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. | ||
Line 15: | Line 15: | ||
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>. | 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> | + | 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, 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>. | + | 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>. | + | 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>. | 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 |
− | |||
==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:39, 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 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
See also
2017 USAJMO (Problems • Resources) | ||
Preceded by Problem 2 |
Last Problem | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |