Difference between revisions of "2012 USAJMO Problems/Problem 4"

(Solution)
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 two <math>1</math>. Let's consider the following two cases.
+
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 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  
+
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-r_2+r_1)\} = 1-r_2+r_1>1-r_1</cmath>
+
 
 +
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=4}}
+
{{USAJMO newbox|year=2012|num-b=2|num-a=5}}
 +
{{MAA Notice}}

Latest revision as of 08:23, 16 April 2017

Problem

Let $\alpha$ be an irrational number with $0 < \alpha < 1$, and draw a circle in the plane whose circumference has length 1. Given any integer $n \ge 3$, define a sequence of points $P_1$, $P_2$, $\dots$, $P_n$ as follows. First select any point $P_1$ on the circle, and for $2 \le k \le n$ define $P_k$ as the point on the circle for which the length of arc $P_{k - 1} P_k$ is $\alpha$, when travelling counterclockwise around the circle from $P_{k - 1}$ to $P_k$. Supose that $P_a$ and $P_b$ are the nearest adjacent points on either side of $P_n$. Prove that $a + b \le n$.

Solution

Use mathematical induction. For $n=3$ it is true because one point can't be closest to $P_3$ in both ways, and that $1+2\le 3$. Suppose that for some $n$, the nearest adjacent points $P_a$ and $P_b$ on either side of $P_n$ satisfy $a+b \le n$. Then consider the nearest adjacent points $P_c$ and $P_d$ on either side of $P_{n+1}$. It is by the assumption of the nearness we can see that either $(c,d)=(a+1,b+1)$ still holds, or $P_1$ jumps into the interior of the arc $P_{a+1}P_{n}P_{b+1}$, so that $c$ or $d$ equals to $1$. Let's consider the following two cases.

(i) Suppose $a+b=n$.

Since the length of the arc $P_nP_a$ is $\{(a-n)\alpha\}$ (where $\{x\}$ equals to $x$ subtracted by the greatest integer not exceeding $x$) and length of the arc $P_bP_n$ is $\{(n-b)\alpha\} = \{a\alpha\}$, we now consider a point $P_0$ which is defined by $P_1$ traveling clockwise on the circle such that the length of arc $P_0P_1$ is $\alpha$. We claim that $P_0$ is in the interior of the arc $P_bP_nP_a$. Algebraically, it is equivalent to either $\{0-n\alpha\} < \{a\alpha-n\alpha\}$ or $\{n\alpha -0 \} < \{n\alpha - b\alpha\} = \{a\alpha\}$.

Suppose the latter fails, i.e. $\{n\alpha\} \ge \{a\alpha\}$. Then suppose $n\alpha = m_1 + r_1$ and $a\alpha = m_2 + r_2$, where $m_1$, $m_2$ are integers and $0< r_2\le r_1 <1$ ($r_2$ is not zero because $a\alpha$ is irrational). We now have \[\{0-n\alpha\} = \{-m_1-1 + (1 -r_1)\}=1-r_1\] and \[\{a\alpha -n\alpha\} = \{m_2-m_1-1 + (1+r_2-r_1)\} = 1+r_2-r_1>1-r_1\]

Therefore $P_0$ is either closer to $P_n$ than $P_a$ on the $P_a$ side, or closer to $P_n$ than $P_b$ on the $P_b$ side. In other words, $P_1$ is the closest adjacent point of $P_{n+1}$ on the $P_{a+1}$ side, or the closest adjacent point of $P_{n+1}$ on the $P_{b+1}$ side. Hence $P_c$ or $P_d$ is $P_1$, therefore $c+d \le n+1$.

(ii) Suppose $a+b\le n-1$ Then either $c+d = (a+1)+(b+1) \le n+1$ when $c=a+1$ and $d=b+1$, or $c+d \le 1+n$ when one of $P_c$ or $P_d$ is $P_1$.

In either case, $c+d\le n+1$ is true.

--Lightest 20:27, 6 May 2012 (EDT)

See Also

2012 USAJMO (ProblemsResources)
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. AMC logo.png