Difference between revisions of "2012 USAJMO Problems/Problem 4"
(→Solution) |
Willwin4sure (talk | contribs) m (→Solution) |
||
(5 intermediate revisions by 3 users not shown) | |||
Line 4: | Line 4: | ||
=== Solution=== | === Solution=== | ||
− | Use mathematical induction. For <math>n=3</math> it is true because one point can't be closest to <math>P_3</math> in both ways, and that <math>1+2\le 3</math>. Suppose that for some <math>n</math>, the nearest adjacent points <math>P_a</math> and <math>P_b</math> on either side of <math>P_n</math> satisfy <math>a+b \le n</math>. Then consider the nearest adjacent points <math>P_c</math> and <math>P_d</math> on either side of <math>P_{n+1}</math>. It is by the assumption of the nearness we can see that either <math>(c,d)=(a+1,b+1)</math> still holds, or <math>P_1</math> jumps into the interior of the arc <math>P_{a+1}P_{n}P_{b+1}</math>, so that <math>c</math> or <math>d</math> equals | + | Use mathematical induction. For <math>n=3</math> it is true because one point can't be closest to <math>P_3</math> in both ways, and that <math>1+2\le 3</math>. Suppose that for some <math>n</math>, the nearest adjacent points <math>P_a</math> and <math>P_b</math> on either side of <math>P_n</math> satisfy <math>a+b \le n</math>. Then consider the nearest adjacent points <math>P_c</math> and <math>P_d</math> on either side of <math>P_{n+1}</math>. It is by the assumption of the nearness we can see that either <math>(c,d)=(a+1,b+1)</math> still holds, or <math>P_1</math> jumps into the interior of the arc <math>P_{a+1}P_{n}P_{b+1}</math>, so that <math>c</math> or <math>d</math> equals to <math>1</math>. Let's consider the following two cases. |
(i) Suppose <math>a+b=n</math>. | (i) Suppose <math>a+b=n</math>. | ||
− | Since the length of the arc <math>P_nP_a</math> is <math>\{(a-n)\alpha\}</math> (where <math>\{x\}</math> equals to <math>x</math> subtracted by the greatest integer not exceeding <math>x</math>) and length of the arc <math>P_bP_n</math> is <math>\{(n-b)\alpha\} = \{a\alpha\}</math>, we now consider a point <math>P_0</math> which is defined by <math>P_1</math> traveling clockwise on the circle such that the length of arc <math>P_0P_1</math> is <math>\alpha</math>. We claim that <math>P_0</math> is in the interior of the arc <math>P_bP_nP_a</math>. Algebraically, it is equivalent to either <math> \{0-n\alpha\} < \{a\alpha-n\alpha\}</math> or <math>\{n\alpha -0 \} < \{n\alpha - b\alpha\} = \{a\alpha\}</math>. Suppose the | + | Since the length of the arc <math>P_nP_a</math> is <math>\{(a-n)\alpha\}</math> (where <math>\{x\}</math> equals to <math>x</math> subtracted by the greatest integer not exceeding <math>x</math>) and length of the arc <math>P_bP_n</math> is <math>\{(n-b)\alpha\} = \{a\alpha\}</math>, we now consider a point <math>P_0</math> which is defined by <math>P_1</math> traveling clockwise on the circle such that the length of arc <math>P_0P_1</math> is <math>\alpha</math>. We claim that <math>P_0</math> is in the interior of the arc <math>P_bP_nP_a</math>. Algebraically, it is equivalent to either <math> \{0-n\alpha\} < \{a\alpha-n\alpha\}</math> or <math>\{n\alpha -0 \} < \{n\alpha - b\alpha\} = \{a\alpha\}</math>. |
− | <cmath>\{n\alpha\} = \{-m_1-1 + (1 -r_1)\}=1-r_1</cmath> and <cmath>a\alpha = \{m_2-m_1-1 + (1- | + | |
+ | Suppose the latter fails, i.e. <math> \{n\alpha\} \ge \{a\alpha\}</math>. Then suppose <math>n\alpha = m_1 + r_1</math> and <math>a\alpha = m_2 + r_2</math>, where <math>m_1</math>, <math>m_2</math> are integers and <math>0< r_2\le r_1 <1</math> (<math>r_2</math> is not zero because <math>a\alpha</math> is irrational). We now have | ||
+ | <cmath>\{0-n\alpha\} = \{-m_1-1 + (1 -r_1)\}=1-r_1</cmath> and <cmath>\{a\alpha -n\alpha\} = \{m_2-m_1-1 + (1+r_2-r_1)\} = 1+r_2-r_1>1-r_1</cmath> | ||
+ | |||
Therefore <math>P_0</math> is either closer to <math>P_n</math> than <math>P_a</math> on the <math>P_a</math> side, or closer to <math>P_n</math> than <math>P_b</math> on the <math>P_b</math> side. In other words, <math>P_1</math> is the closest adjacent point of <math>P_{n+1}</math> on the <math>P_{a+1}</math> side, or the closest adjacent point of <math>P_{n+1}</math> on the <math>P_{b+1}</math> side. Hence <math>P_c</math> or <math>P_d</math> is <math>P_1</math>, therefore <math>c+d \le n+1</math>. | Therefore <math>P_0</math> is either closer to <math>P_n</math> than <math>P_a</math> on the <math>P_a</math> side, or closer to <math>P_n</math> than <math>P_b</math> on the <math>P_b</math> side. In other words, <math>P_1</math> is the closest adjacent point of <math>P_{n+1}</math> on the <math>P_{a+1}</math> side, or the closest adjacent point of <math>P_{n+1}</math> on the <math>P_{b+1}</math> side. Hence <math>P_c</math> or <math>P_d</math> is <math>P_1</math>, therefore <math>c+d \le n+1</math>. | ||
Line 22: | Line 25: | ||
*[[USAJMO Problems and Solutions]] | *[[USAJMO Problems and Solutions]] | ||
− | {{USAJMO newbox|year=2012|num-b=2|num-a= | + | {{USAJMO newbox|year=2012|num-b=2|num-a=5}} |
+ | {{MAA Notice}} |
Latest revision as of 08:23, 16 April 2017
Problem
Let be an irrational number with , and draw a circle in the plane whose circumference has length 1. Given any integer , define a sequence of points , , , as follows. First select any point on the circle, and for define as the point on the circle for which the length of arc is , when travelling counterclockwise around the circle from to . Supose that and are the nearest adjacent points on either side of . Prove that .
Solution
Use mathematical induction. For it is true because one point can't be closest to in both ways, and that . Suppose that for some , the nearest adjacent points and on either side of satisfy . Then consider the nearest adjacent points and on either side of . It is by the assumption of the nearness we can see that either still holds, or jumps into the interior of the arc , so that or equals to . Let's consider the following two cases.
(i) Suppose .
Since the length of the arc is (where equals to subtracted by the greatest integer not exceeding ) and length of the arc is , we now consider a point which is defined by traveling clockwise on the circle such that the length of arc is . We claim that is in the interior of the arc . Algebraically, it is equivalent to either or .
Suppose the latter fails, i.e. . Then suppose and , where , are integers and ( is not zero because is irrational). We now have and
Therefore is either closer to than on the side, or closer to than on the side. In other words, is the closest adjacent point of on the side, or the closest adjacent point of on the side. Hence or is , therefore .
(ii) Suppose Then either when and , or when one of or is .
In either case, is true.
--Lightest 20:27, 6 May 2012 (EDT)
See Also
2012 USAJMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.