Maths Olympiad Prep

Library / /395 of 397

Algebra Difficulty 7.6 National Olympiad, round 2 Prove it Taiwan

Let N,Z,Q\mathbb{N}, \mathbb{Z}, \mathbb{Q} denote the set of all positive integers, integers and rational numbers respectively. Determine all functions f:QZf : \mathbb{Q} \to \mathbb{Z} satisfying
f(f(x)+ab)=f(x+ab) f\left(\frac{f(x)+a}{b}\right) = f\left(\frac{x+a}{b}\right)
for all xQ,aZx \in \mathbb{Q}, a \in \mathbb{Z}, and bNb \in \mathbb{N}.

Solution

f=xf = \lfloor x \rfloor, f=xf = \lceil x \rceil, and constant functions.

We first verify that the above functions satisfy the problem's conditions. For all triples (x,a,b)Q×Z×N(x, a, b) \in \mathbb{Q} \times \mathbb{Z} \times \mathbb{N}, let
q=x+ab. q = \lfloor \frac{x+a}{b} \rfloor.
It is easy to see that bqx+a<b(q+1)bqx+a<b(q+1)bq \le x + a < b(q+1) \Rightarrow bq \le \lfloor x \rfloor + a < b(q+1), so
x+ab=x+ab. \lfloor \frac{\lfloor x \rfloor + a}{b} \rfloor = \lfloor \frac{x+a}{b} \rfloor.
Thus f=xf = \lfloor x \rfloor is indeed a solution. The other two solutions can be verified similarly.

Next we prove that these are all possible solutions. Consider the following two cases:

Case 1. There exists an integer mm such that f(m)mf(m) \neq m.

Let C=f(m)C = f(m). If m>Cm > C, then for all integers yy, substituting x=m,b=mC,a=ybCx = m, b = m-C, a = yb-C into the original equation gives f(y)=f(y+1)f(y) = f(y+1), so for all integers yy, f(y)=Cf(y) = C. If m<Cm < C, then instead taking b=Cmb = C-m, we likewise obtain f(y)=Cf(y) = C for all integers yy.

Now, for all rational numbers y=p/qy = p/q (where q>0q > 0), substituting (x,a,b)=(Cp,pC,q)(x, a, b) = (C - p, p - C, q) gives f(y)=f(0)=Cf(y) = f(0) = C. Hence ff is a constant function.

Case 2. For all integers mm, f(m)=mf(m) = m.

Taking b=1b = 1, we know that
f(x)+a=f(x+a)(1) f(x) + a = f(x + a) \quad (1)
holds for all (x,a)Q×Z(x, a) \in \mathbb{Q} \times \mathbb{Z}. Let ω=f(1/2)\omega = f(1/2).

Claim 1. ω{0,1}\omega \in \{0, 1\}.

Proof. If ω0\omega \le 0, substituting (x,a,b)=(1/2,ω,12ω)(x, a, b) = (1/2, -\omega, 1-2\omega) gives 0=f(0)=f(1/2)=ω0 = f(0) = f(1/2) = \omega. Similarly, if ω1\omega \ge 1, take (x,a,b)=(1/2,ω1,2ω1)(x, a, b) = (1/2, \omega-1, 2\omega-1).

Claim 2. For all rational numbers 0<x<10 < x < 1, f(x)=ωf(x) = \omega.

Proof. If not, there exists p/q(0,1)p/q \in (0, 1) with the smallest denominator such that f(p/q)ωf(p/q) \ne \omega. It is easy to see that gcd(p,q)=1\gcd(p, q) = 1, and q2q \ge 2. If qq is even, then pp must be odd, so substituting (x,a,b)=(12,p12,q2)(x, a, b) = (\frac{1}{2}, \frac{p-1}{2}, \frac{q}{2}) gives
f(ω+(p1)/2q/2)=f(p/q)ω. f\left(\frac{\omega + (p-1)/2}{q/2}\right) = f(p/q) \ne \omega.
But by Claim 1, ω=0\omega = 0 or 11, so the above equation in either case yields some p/q(0,1)p'/q' \in (0, 1) satisfying f(p/q)ωf(p'/q') \ne \omega with q<qq' < q. This contradicts the assumption that p/qp/q has the smallest denominator, a contradiction.

Therefore qq must be odd; let q=2k+1q = 2k + 1. Substituting (x,a,b)=(1/2,k,q)(x, a, b) = (1/2, k, q) gives
f(ω+kq)=f(12)=ω. f\left(\frac{\omega + k}{q}\right) = f\left(\frac{1}{2}\right) = \omega.
Since p,qp, q are coprime, there exist r{1,2,,q}r \in \{1, 2, \dots, q\} and an integer mm such that rpmq=k+ωrp - mq = k + \omega; moreover, since the right-hand side is not a multiple of qq, r<qr < q. And if m<0m < 0, then rpmq>qk+ωrp - mq > q \ge k + \omega, a contradiction, so m0m \ge 0. Similarly, if mrm \ge r, then rpmq<brbr=0rp - mq < br - br = 0. Hence, 0mr10 \le m \le r - 1. Now, taking (x,a,b)=(k+ωq,m,r)(x, a, b) = (\frac{k+\omega}{q}, m, r), we get
f(ω+mr)=f(p/q)ω. f\left(\frac{\omega + m}{r}\right) = f(p/q) \ne \omega.
This contradicts the minimality of qq, a contradiction!

Now, if ω=0\omega = 0, then by Claim 2, f(x)=xf(x) = \lfloor x \rfloor. Similarly, if ω=1\omega = 1, then by Claim 2, f(x)=xf(x) = \lceil x \rceil. This completes 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 translated into English from zh; metadata (topic, difficulty) added by this project.