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, \ldots , 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$. Suppose that $P_a$ and $P_b$ are the nearest adjacent points on either side of $P_n$. Prove that $a+b\le n$.
Problem
Source: 2012 USAJMO Day 2 #4
Tags: floor function, induction, analytic geometry, irrational number, AMC, USAJMO
26.04.2012 01:06
This was a fun problem. It took like 15 minutes of staring at it but there's a really easy solution
26.04.2012 01:09
gurev wrote: This was a fun problem. It took like 15 minutes of staring at it but there's a really easy solution
How do you know such a point P(a+b-n) exists?
26.04.2012 01:10
because I assumed a+b>n
26.04.2012 01:11
@above, that's the point. It's a proof by contradiction.
26.04.2012 01:16
Hm. I proved that if $\lfloor \alpha n\rfloor<2$, then it works, and then vaguely cited induction for the rest. Fail.
26.04.2012 01:19
26.04.2012 01:35
proved that if k*alpha < 1 < (k+1)*alpha, it works for up to P_2k. Did some vague algebra and stuff with intervals that may or may not have got me more than 2 points.
26.04.2012 01:41
26.04.2012 04:48
gurev's solution works. i did something similar, but mine involved several cases... and i left out some minor details. if only i had your brain gurev xD
26.04.2012 06:12
26.04.2012 06:32
lol so i saw this and thought of steinhaus conjecture/three-gap theorem.
26.04.2012 07:14
Maxmk, I might be wrong, dont think your solution works. While one can shift the point P1 to 0 or Pn to 0, they can't both be 0, and so Px+y doesn't have to be between Px and Py. What would work is Pa+b-n(see solution above). Also, x + y can be equal to n, consider n=3, which must have 1 and 2 as the the two adjacent numbers. You only have to prove that x+y is not greater than n.
26.04.2012 07:49
gurev wrote: Maxmk, I might be wrong, dont think your solution works. While one can shift the point P1 to 0 or Pn to 0, they can't both be 0, and so Px+y doesn't have to be between Px and Py. What would work is Pa+b-n(see solution above). Also, x + y can be equal to n, consider n=3, which must have 1 and 2 as the the two adjacent numbers. You only have to prove that x+y is not greater than n. I see why this may be confusing. I was inducting on $n$ here, as well. I first proved that, for $P_x$ and $P_y$, the points closest to $0$, that $x+y\geq n$. Then, I turned that around to $a$ and $b$. $P_{x+y} = \{(x+y)\alpha\} = \{P_x + P_y\}$. Since $ P_x < P_x + P_y < 1 + P_y$, $P_{x+y}$ is in between the two. Later, I define $a = n-x$ and $b = n-y$.
26.04.2012 07:53
It's on a circle, so isn't any point "in between" any two other points?
26.04.2012 08:12
Yes. I mean that it is closer to $0$ than at least one of the other points. "In between" means "on the arc with $P_x$, $0$, and $P_y$" in this case.
26.04.2012 16:55
That makes sense
30.04.2012 05:41
n is between A and B. So the average (A+B) is close to 2N. Oh look, (A+B-N) is therefore even closer. GG.
08.05.2012 18:36
I used P_(a+b-n) also. I really liked this one and wish there was/will be more such (intuitive) combo.
01.04.2013 19:25
28.02.2014 15:57
gurev wrote: This was a fun problem. It took like 15 minutes of staring at it but there's a really easy solution Suppose $a+b>n$. Consider the point $P_{a+b-n}$. This is the equivalent of taking point $a$ and pushing it forward a distance of $y$ How do you know that $P_{a+b-n}$ is $P_a$ pushed forward by $y$?
17.04.2014 07:52
hi could someone answer this thanks
16.04.2016 21:05
supercomputer wrote: gurev wrote: This was a fun problem. It took like 15 minutes of staring at it but there's a really easy solution Suppose $a+b>n$. Consider the point $P_{a+b-n}$. This is the equivalent of taking point $a$ and pushing it forward a distance of $y$ How do you know that $P_{a+b-n}$ is $P_a$ pushed forward by $y$? Hello, I would also like the answer to this question. Thanks
10.04.2017 00:43
supercomputer wrote: gurev wrote: This was a fun problem. It took like 15 minutes of staring at it but there's a really easy solution Suppose $a+b>n$. Consider the point $P_{a+b-n}$. This is the equivalent of taking point $a$ and pushing it forward a distance of $y$ How do you know that $P_{a+b-n}$ is $P_a$ pushed forward by $y$? Me too thanks.
10.04.2017 00:46
wu2481632 wrote: supercomputer wrote: gurev wrote: This was a fun problem. It took like 15 minutes of staring at it but there's a really easy solution Suppose $a+b>n$. Consider the point $P_{a+b-n}$. This is the equivalent of taking point $a$ and pushing it forward a distance of $y$ How do you know that $P_{a+b-n}$ is $P_a$ pushed forward by $y$? Me too thanks. Me three thanks.
10.04.2017 03:13
The distance from $P_a$ to $P_{a+b-n}$ is $\alpha * [(a+b-n)-a]=\alpha *(b-n)$ which is the distance from $P_b$ to $P_n$ which is y.(Previously defined)
03.08.2017 23:33
This is basically Gurev's solution, but I feel it helps me to type it up. Let the top of the circle be $P_0$. WLOG, let $P_a$ be the farthest from $P_0$ (going clockwise), followed by $P_n$, and finally $P_b$. We now define $P_i$ to be the negative of the distance from $P_i$ to $P_0$. With this is mind, let $P_b=-z$, $P_n=-y-z$, and $P_a=-x-y-z$, where $x$, $y$ and $z$ are the distances between $P_a$ and $P_n$, $P_n$ and $P_b$, and $P_b$ and $P_0$. Assume, for purpose of contradiction, that $a+b>n$. We can now consider the point $P_{a+b-n}$. We have that $P_{a+b-n}=P_a+P_b-P_n=(-x-y-z)+(-z)-(-y-z)=-x-z$. Since $-x-z$ is between $P_a$ and $P_b$, we have a contradiction, hence $a+b\leq n$ as desired. $\square$
24.05.2018 21:29
If $a + b > n$ then $\overline{P_aP_b} \parallel \overline{P_nP_{a + b - n}}$ (note $a + b - n < n$) so $P_{a+b-n}$ is on the arc $P_aP_nP_b$, contradiction. Thus $a + b \le n$.
21.06.2020 08:13
Let $P_b$ lie to the left of $P_n$ and $P_a$ to right. Note that the distance between $P_a$ and $P_n$ is: $$\{\alpha (n-a) \}$$The distance between $P_b$ and $P_n$ is: $$1-\{\alpha (n-b) \}$$Assume by sake of contradiction $a+b > n$; the distance between $P_{a+b-n}$ and $P_n$ is: $$ \{ \alpha(a+b-n - n) \} = 1 - \{\alpha (2n-a-b) \}$$which is the difference between the distance of $P_b$ and $P_n$ between the distance of $P_a$ and $P_n$. Therefore, $P_{a+b-n}$ must lie between $P_a$ and $P_b$ which is a contradiction. Hence, $a+b \le n$.
25.09.2021 04:18
Pretty nice problem. Assume $a+b>n$. Define $P_0$ to be $\alpha$ clockwise of $P_1$. The main idea is the following: If $P_k$ is a counterclockwise arclength $x$ ahead of $P_0$, then for any $d$, $P_{d+k}$ is a counterclockwise arclength $x$ ahead of $P_d$, and $P_{d-k}$ is a counterclockwise arclength $x$ behind $P_d$. Suppose $P_a$ is ahead of $P_0$ by an arclength of $x$, and $P_n$ ahead of $P_a$ by $y_1$, and $P_b$ ahead of $P_n$ by $y_2$. Then $P_{a+b}$ will be ahead of $P_b$ by $x$ as well. Since $P_n$ is ahead of $P_0$ by $x+y_1$, we have $P_{a+b}$ is ahead of $P_n$ by $x+y_1$ too. But since $P_{a+b}$ is ahead of $P_0$ by $2x+y_1+y_2$, we will have $P_{a+b-n}$ be $(2x+y_1+y_2)-(x+y_1)=x+y_2$ ahead of $P_0$. But $x < x + y_2 < x+y_1+y_2$, so $P_{a+b-n}$ is between $P_a$ and $P_b$ along with $P_n$, contradiction.
21.10.2021 00:15
CantonMathGuy wrote: If $a + b > n$ then $\overline{P_aP_b} \parallel \overline{P_nP_{a + b - n}}$ (note $a + b - n < n$) so $P_{a+b-n}$ is on the arc $P_aP_nP_b$, contradiction. Thus $a + b \le n$. How do you know that $\overline{P_aP_b} \parallel \overline{P_nP_{a + b - n}}$?
23.11.2021 17:27
thinker123 wrote: CantonMathGuy wrote: If $a + b > n$ then $\overline{P_aP_b} \parallel \overline{P_nP_{a + b - n}}$ (note $a + b - n < n$) so $P_{a+b-n}$ is on the arc $P_aP_nP_b$, contradiction. Thus $a + b \le n$. How do you know that $\overline{P_aP_b} \parallel \overline{P_nP_{a + b - n}}$? Draw a neat picture yourself and you'll see.
12.02.2022 17:20
Suppose $a+b>n$. Let the distances between $P_a$ and $P_b$ to $n$ be $x$ and $y$, respectively. WLOG $x\ge y$. Note that $a+b<2n$. So consider the point $P_{a+b-n}$. Basically we start at point $P_a$ and go $y$ units along the circle toward $P_n$. If $x=y$, then we reach point $P_n$, which is a contradiction as $\alpha$ is irrational. If $x>y$, then the distance to $n$ is less than $x$ and $P_{a+b-n}$ is on the side of $P_a$, a contradiction.
19.12.2022 05:20
The key to the problem is the following rephrasing: Claim. If $P_a$ and $P_b$ are the two nearest adjacent points on either side of $P_1$, then it suffices to show that $a+b \geq n$. Notice that $P_a$ and $P_{n-a}$ are symmetric around the arc midpoint of $P_0P_n$, and similarly for $P_b$ and $P_{n-b}$. The result follows. $\blacksquare$ Now, assume for the sake of contradiction that $a+b < n$. Consider the point $P_{a+b}$, which is strictly between $P_a$ and $P_b$ (as it is the sum of the displacements), which contradicts the condition.
15.11.2023 23:03
Minamoto wrote:
Does this solution work?
01.08.2024 04:17
Complex For the sake of contradiction assume $a + b > n$. Scale the circle to a unit circle and suppose $\alpha$ along the circumference of the original circle corresponds to an angle of $\theta$ on our new circle. Note that $P_a$ is just $e^{i \theta a}$ and $P_b$ is $e^{i \theta b}$. Now note that $P_{a + b - n}$ must be a point, and since $$e^{i (\theta a + b - n)} \cdot e^{i \theta n} = e^{i \theta a} \cdot e^{i \theta b}$$we know that $P_{a + b - n}$ is simply the reflection of $P_n$ across the perpendicular bisector of segment $P_a P_b$. Now we cannot have $P_n = P_{a + b - n}$ since the indices cannot be the same since $a, b < n$, and the points cannot coincide since $\alpha$ is irrational. So $P_{a + b - n}$ is closer to one of $P_a$ or $P_b$ than $P_n$, we are done.
03.11.2024 04:37
We will use contradiction. Suppose that $a+b>n$. In this case, the point $P_{a+b-n}$ exists. Since $P_aP_b$ is parallel to $P_nP_{a+b-n}$, the closest points to $P$ are no longer $a$ and $b$ (since $P_{a+b-n}$ is closer for one of $P_a$, $P_b$). We are done.