Maths Olympiad Prep

Library / /8 of 8

, 2022

Algebra Difficulty 8.9 Shortlist Prove it China

If two real numbers α,β\alpha, \beta satisfy that k1αk2β\lfloor k_1\alpha \rfloor \neq \lfloor k_2\beta \rfloor for all positive integers k1,k2k_1, k_2, where x\lfloor x \rfloor denotes the maximal integer not exceeding xx.
Prove that there exist two positive integers m1,m2m_1, m_2 such that m1α+m2β=1\frac{m_1}{\alpha} + \frac{m_2}{\beta} = 1.

Solution

First note that βα\frac{\beta}{\alpha} is an irrational number (otherwise there are positive integers k1,k2k_1, k_2 such that k1α=k2βk_1\alpha = k_2\beta, which leads to a contradiction).
If α=qp\alpha = \frac{q}{p} is a rational number, then there is a positive integer k2k_2 such that the decimal part of k2βq\frac{k_2\beta}{q} is less than 1q\frac{1}{q}. Taking k1=pk2βqk_1 = p\lfloor\frac{k_2\beta}{q}\rfloor gives that
k1α=qk2βq<k2β<qk2βq+1, k_1\alpha = q \cdot \lfloor\frac{k_2\beta}{q}\rfloor < k_2\beta < q\lfloor\frac{k_2\beta}{q}\rfloor + 1,
which contradicts to the assumption. Thus α\alpha must be irrational. Similarly, β\beta must be irrational as well.

A pair of positive integers (a,b)(a, b) is called distinguished if 0<bβaα<10 < b\beta - a\alpha < 1. By our assumption, there is a unique positive integer tt such that aα<t<bβa\alpha < t < b\beta. Denoting u=taα,v=bβtu = t - a\alpha, v = b\beta - t, we say a distinguished pair (a,b)(a, b) corresponds to the intermediate number tt together with a distant pair (u,v)(u, v). We will prove the following.

Lemma. Assume two distinguished pairs (a1,b1)(a_1, b_1), (a2,b2)(a_2, b_2) correspond to distant pairs (u1,v1)(u_1, v_1), (u2,v2)(u_2, v_2), respectively. Then u1v1=u2v2\frac{u_1}{v_1} = \frac{u_2}{v_2}.

Proof of Lemma. Suppose that the intermediate numbers of these two distinguished pairs are t1,t2t_1, t_2, respectively. Assume for the sake of contradiction that u1v1>u2v2\frac{u_1}{v_1} > \frac{u_2}{v_2}. We also take ϵ=u1v2u2v12>0\epsilon = \frac{u_1v_2 - u_2v_1}{2} > 0.
Since βα\frac{\beta}{\alpha} is an irrational number, there are positive integers a0,b0a_0, b_0 such that 0<a0αb0β<ϵ0 < a_0\alpha - b_0\beta < \epsilon. On the other hand, our assumption implies that there is another integer t0t_0 satisfying b0β<t0<a0αb_0\beta < t_0 < a_0\alpha. Denote u0=a0αt0u_0 = a_0\alpha - t_0 and v0=t0b0βv_0 = t_0 - b_0\beta. If u1u0v1v0>1\frac{u_1}{u_0} - \frac{v_1}{v_0} > 1, then one can take L=v1v0+1L = \lfloor\frac{v_1}{v_0}\rfloor + 1 such that u1u0>L>v1v0\frac{u_1}{u_0} > L > \frac{v_1}{v_0}, i.e.,
u1Lu0=(t1+Lt0)(a1+La0)α>0,v1Lv0=(t1+Lt0)(b1+Lb0)β<0. \begin{aligned} u_1 - Lu_0 &= (t_1 + Lt_0) - (a_1 + La_0)\alpha > 0, \\ v_1 - Lv_0 &= (t_1 + Lt_0) - (b_1 + Lb_0)\beta < 0. \end{aligned}
Set k1=a1+La0k_1 = a_1 + La_0 and k2=b1+Lb0k_2 = b_1 + Lb_0. Then k1α=k2β=t1+Lt01\lfloor k_1\alpha \rfloor = \lfloor k_2\beta \rfloor = t_1 + Lt_0 - 1, which leads to a contradiction. This further implies that u1u0v1v01\frac{u_1}{u_0} - \frac{v_1}{v_0} \le 1. Using a similar argument, we can show that u2u0v2v01\frac{u_2}{u_0} - \frac{v_2}{v_0} \ge -1. Therefore,
u1u0v0v1u0,u2u0v0v2u0,u1v2u2v1u0(v1+v2)<2ϵ. u_1 - \frac{u_0}{v_0}v_1 \le u_0, \quad u_2 - \frac{u_0}{v_0}v_2 \ge -u_0, \quad \Rightarrow \quad u_1v_2 - u_2v_1 \le u_0(v_1 + v_2) < 2\epsilon.
However, this violates our choice of ϵ\epsilon. The lemma is proved.

Now we see all distinguished pairs (a,b)(a, b) share the same ratio uv=taαbβt\frac{u}{v} = \frac{t - a\alpha}{b\beta - t}. Denote this common λ=vu+v(0,1)\lambda = \frac{v}{u+v} \in (0, 1); then we have an equality λaα+(1λ)bβ=tZ\lambda \cdot a\alpha + (1 - \lambda) \cdot b\beta = t \in \mathbb{Z}. We call linear combinations of distinguished pairs with integer coefficients nice pairs. For each nice pair (c,d)(c, d), it is not hard to see that
λcα+(1λ)dβ=cλα+d(1λ)βZ. \lambda \cdot c\alpha + (1 - \lambda) \cdot d\beta = c \cdot \lambda\alpha + d \cdot (1 - \lambda)\beta \in \mathbb{Z}.
Take a nice pair (a,b)(a, b) and set δ=bβaα(0,1)\delta = b\beta - a\alpha \in (0, 1). We claim that for all M>0M > 0, any pair (c,d)(c, d) of integers satisfying 0<dβcα<M0 < d\beta - c\alpha < M and c>aδMc > \frac{a}{\delta}M, is nice. Indeed, it suffices to take L=dβcαδ<Mδ<caL = \lfloor \frac{d\beta - c\alpha}{\delta} \rfloor < \frac{M}{\delta} < \frac{c}{a} so that (dLb)β(cLa)α=(dβcα)Lδ(0,δ)(0,1)(d - Lb)\beta - (c - La)\alpha = (d\beta - c\alpha) - L\delta \in (0, \delta) \subset (0, 1), and therefore the pair (cLa,dLb)(c - La, d - Lb) must be distinguished and the pair (c,d)=(cLa,dLb)+L(a,b)(c, d) = (c - La, d - Lb) + L \cdot (a, b) must be a nice pair.

Now take M=α+2βM = \alpha + 2\beta, and integers c0>aδM+1c_0 > \frac{a}{\delta}M + 1 and d0=c0αβd_0 = \lfloor \frac{c_0\alpha}{\beta} \rfloor satisfying the condition 0<d0βc0α<β0 < d_0\beta - c_0\alpha < \beta. Using the analysis above, (c0,d0)(c_0, d_0), (c0,d0+1)(c_0, d_0 + 1), and (c01,d0)(c_0 - 1, d_0) are nice pairs, and their linear combinations (0,1)(0, 1) and (1,0)(1, 0) are nice pairs as well. This implies in particular that λα\lambda\alpha and (1λ)β(1 - \lambda)\beta are (positive) integers. Taking positive integers m2=λαm_2 = \lambda\alpha and m1=(1λ)βm_1 = (1 - \lambda)\beta, we get m2α+m1β=λ+(1λ)=1\frac{m_2}{\alpha} + \frac{m_1}{\beta} = \lambda + (1 - \lambda) = 1, or equivalently m1α+m2β=αβm_1\alpha + m_2\beta = \alpha\beta. We conclude the proof.

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 and solution reproduced as published; topic and difficulty added by this site.