2012 USAJMO Problems/Problem 4

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 two $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 former fails, i.e. $\{0-n\alpha\} \ge \{(a-n)\alpha\}$ . Then suppose $-n\alpha = m_1 + r_1$ and $(a-n)\alpha = m_2 + r_2$ , where $m_1$ , $m_2$ are integers and $1> r_1 \ge r_2 \ge 0$ . We now have $\{n\alpha\} = \{-m_1-1 + (1 -r_1)\}=1-r_1$ and $a\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)

2012 USAJMO (Problems • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search

2012 USAJMO Problems/Problem 4

Problem

Solution

See Also