Difference between revisions of "2012 USAJMO Problems/Problem 4"
(Created page with "== Problem == Let <math>\alpha</math> be an irrational number with <math>0 < \alpha < 1</math>, and draw a circle in the plane whose circumference has length 1. Given any integ...") |
(→Solution) |
||
Line 3: | Line 3: | ||
Let <math>\alpha</math> be an irrational number with <math>0 < \alpha < 1</math>, and draw a circle in the plane whose circumference has length 1. Given any integer <math>n \ge 3</math>, define a sequence of points <math>P_1</math>, <math>P_2</math>, <math>\dots</math>, <math>P_n</math> as follows. First select any point <math>P_1</math> on the circle, and for <math>2 \le k \le n</math> define <math>P_k</math> as the point on the circle for which the length of arc <math>P_{k - 1} P_k</math> is <math>\alpha</math>, when travelling counterclockwise around the circle from <math>P_{k - 1}</math> to <math>P_k</math>. Supose that <math>P_a</math> and <math>P_b</math> are the nearest adjacent points on either side of <math>P_n</math>. Prove that <math>a + b \le n</math>. | Let <math>\alpha</math> be an irrational number with <math>0 < \alpha < 1</math>, and draw a circle in the plane whose circumference has length 1. Given any integer <math>n \ge 3</math>, define a sequence of points <math>P_1</math>, <math>P_2</math>, <math>\dots</math>, <math>P_n</math> as follows. First select any point <math>P_1</math> on the circle, and for <math>2 \le k \le n</math> define <math>P_k</math> as the point on the circle for which the length of arc <math>P_{k - 1} P_k</math> is <math>\alpha</math>, when travelling counterclockwise around the circle from <math>P_{k - 1}</math> to <math>P_k</math>. Supose that <math>P_a</math> and <math>P_b</math> are the nearest adjacent points on either side of <math>P_n</math>. Prove that <math>a + b \le n</math>. | ||
− | ==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=a+1</math>, <math>d=b+1</math>, or one of <math>c</math> or <math>d</math> equals two <math>1</math>. Let's consider the following two cases. | ||
+ | |||
+ | (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 either <math>P_0</math> is on the interior of the arc <math>P_nP_a</math> or on the interior of the arc <math>P_bP_n</math>. Algebraically, it is equivalent to either <math> \{0-n\alpha\} < \{(a-n)\alpha\}</math> or <math>\{n\alpha -0 \} < \{a\alpha\}</math>. Suppose the former fails, i.e. <math> \{0-n\alpha\} \ge \{(a-n)\alpha\}</math>. Then suppose <math>-n\alpha = m_1 + r_1</math> and <math>(a-n)\alpha = m_2 + r_2</math>, where <math>m_1</math>, <math>m_2</math> are integers and <math>1> r_1 \ge r_2 \ge 0</math>. We now have | ||
+ | <cmath>\{n\alpha\} = \{-m_1-1 + (1 -r_1)\}=1-r_1</cmath> and <cmath>a\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>. | ||
+ | |||
+ | (ii) Suppose <math>a+b\le n-1</math> | ||
+ | Then either <math>c+d = (a+1)+(b+1) \le n+1</math> when <math>c=a+1</math> and <math>d=b+1</math>, or <math>c+d \le 1+n</math> when one of <math>P_c</math> or <math>P_d</math> is <math>P_1</math>. | ||
+ | |||
+ | In either case, <math>c+d\le n+1</math> is true. | ||
+ | |||
+ | --[[User:Lightest|Lightest]] 20:27, 6 May 2012 (EDT) | ||
==See Also== | ==See Also== |
Revision as of 19:27, 6 May 2012
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
,
, or one of
or
equals two
. 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 either
is on the interior of the arc
or on the interior of the arc
. Algebraically, it is equivalent to either
or
. Suppose the former fails, i.e.
. Then suppose
and
, where
,
are integers and
. 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 4 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |