Maths Olympiad Prep

Library / APMO /25 of 25

APMO, 2025

Combinatorics Difficulty 8.2 Shortlist Prove it Asia Pacific Mathematics Olympiad (APMO)

Let α\alpha and β\beta be positive real numbers. Emerald makes a trip in the coordinate plane, starting off from the origin (0,0)(0,0). Each minute she moves one unit up or one unit to the right, restricting herself to the region ∣x−y∣<2025|x-y|<2025, in the coordinate plane. By the time she visits a point ( x,yx, y ) she writes down the integer ⌊xα+yβ⌋\lfloor x \alpha+y \beta\rfloor on it. It turns out that Emerald wrote each non-negative integer exactly once. Find all the possible pairs (α,β)(\alpha, \beta) for which such a trip would be possible.

Solution

Let (xn,yn)(x_{n}, y_{n}) be the point that Emerald visits after nn minutes. Then (xn+1,yn+1)∈{(xn+1,yn),(xn,yn+1)}(x_{n+1}, y_{n+1}) \in \{(x_{n}+1, y_{n}), (x_{n}, y_{n}+1)\}. Either way, xn+1+yn+1=xn+yn+1x_{n+1}+y_{n+1}=x_{n}+y_{n}+1, and since x0+y0=0+0=0x_{0}+y_{0}=0+0=0, xn+yn=nx_{n}+y_{n}=n.

The nn-th number would be then
zn=⌊xnα+(n−xn)β⌋⟹nβ+xn(α−β)−1<zn<nβ+xn(α−β) z_{n}=\left\lfloor x_{n} \alpha+\left(n-x_{n}\right) \beta\right\rfloor \Longrightarrow n \beta+x_{n}(\alpha-\beta)-1<z_{n}<n \beta+x_{n}(\alpha-\beta)
in which
−2025<xn−yn<2025⟺n−20252<xn<n+20252. -2025<x_{n}-y_{n}<2025 \Longleftrightarrow \frac{n-2025}{2}<x_{n}<\frac{n+2025}{2} .
Suppose without loss of generality that α≥β\alpha \geq \beta. Then
nβ+n−20252(α−β)−1<zn<nβ+n+20252(α−β), n \beta+\frac{n-2025}{2}(\alpha-\beta)-1<z_{n}<n \beta+\frac{n+2025}{2}(\alpha-\beta),
which reduces to
∣zn−α+β2n∣<20252(α−β)+1. \left|z_{n}-\frac{\alpha+\beta}{2} n\right|<\frac{2025}{2}(\alpha-\beta)+1 .
On the other hand, zn+1=⌊xn+1α+yn+1β⌋∈{⌊xnα+ynβ+α⌋,⌊xnα+ynβ+β⌋}z_{n+1}=\left\lfloor x_{n+1} \alpha+y_{n+1} \beta\right\rfloor \in\{\left\lfloor x_{n} \alpha+y_{n} \beta+\alpha\right\rfloor,\left\lfloor x_{n} \alpha+y_{n} \beta+\beta\right\rfloor\}, which implies zn+1≥znz_{n+1} \geq z_{n}. Since every non-negative integer appears exactly once, in increasing order, it follows that zn=nz_{n}=n.

Therefore, for all positive integers nn,
∣n−α+β2n∣<20252(α−β)+1, \left|n-\frac{\alpha+\beta}{2} n\right|<\frac{2025}{2}(\alpha-\beta)+1,
which can only be possible if α+β=2\alpha+\beta=2; otherwise, the left hand side would be unbounded. If α+β=2\alpha+\beta=2, consider xn=⌈n2⌉x_{n}=\left\lceil\frac{n}{2}\right\rceil and yn=⌊n2⌋y_{n}=\left\lfloor\frac{n}{2}\right\rfloor. If nn is even,
zn=⌊n2α+n2β⌋=n; z_{n}=\left\lfloor\frac{n}{2} \alpha+\frac{n}{2} \beta\right\rfloor=n ;
if nn is odd,
zn=⌊n+12α+n−12β⌋=n+⌊α−β2⌋, z_{n}=\left\lfloor\frac{n+1}{2} \alpha+\frac{n-1}{2} \beta\right\rfloor=n+\left\lfloor\frac{\alpha-\beta}{2}\right\rfloor,
which equals nn because 0<β≤α<α+β=2⟹0≤α−β<20<\beta \leq \alpha<\alpha+\beta=2 \Longrightarrow 0 \leq \alpha-\beta<2.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.