Maths Olympiad Prep

Library / /26 of 26

, 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 xy<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α+(nxn)β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<xnyn<2025n20252<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β+n20252(αβ)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+1znz_{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=n2x_{n}=\left\lceil\frac{n}{2}\right\rceil and yn=n2y_{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α+n12β=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<βα<α+β=20αβ<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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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