Maths Olympiad Prep

Library / /258 of 397

Algebra Difficulty 6.2 National Olympiad Prove it Taiwan

Let Q+Q^+ be the set of all positive rational numbers. Find all functions f:Q+Q+f : Q^+ \to Q^+ satisfying f(1)=1f(1) = 1 and
f(x+n)=f(x)+nf(1x)f(x+n) = f(x) + n f(\frac{1}{x}) for all positive integers nn and xQ+\forall x \in Q^+.

Solution

First, for a pair of positive integers (a,b)(a, b) (where aba \neq b), define one operation on it as replacing the larger number with the remainder obtained by dividing it by the smaller number. (For example (2,5)(2, 5) becomes (2,1)(2, 1), (5,2)(5, 2) becomes (1,2)(1, 2))
Let g:Q+N0g: Q^+ \to N_0 be such that for every positive rational number pq\frac{p}{q} (where p,qp, q are coprime positive integers), the following holds:
after performing the operation on the pair (p,q)(p, q) a total of g(pq)g(\frac{p}{q}) times, one of the two numbers becomes 1 and the other is not 0.
First, since p,qp, q are coprime, gg exists for every positive rational number. Moreover, once one of them becomes 1, the next operation will make the other one become 0, and after that no further operation can be performed, so gg is unique. Hence gg is well-defined.
Next, it is not hard to see that g(x)=g(x1)g(x) = g(x^{-1}). And when 0<x<10 < x < 1,
g(x+n)=g(x)+1.(1) g(x+n) = g(x) + 1. \tag{1}
Here nn is a positive integer.

Next, we prove by mathematical induction that f(pq)=pf(\frac{p}{q}) = p, where p,qp, q are coprime positive integers. We induct on g(pq)g(\frac{p}{q}).

If g(pq)=0g(\frac{p}{q}) = 0, then p=1p = 1 or q=1q = 1.
If q=1q = 1, substituting (x,n)=(1,p1)(x, n) = (1, p-1) into the original equation gives
f(p)=p.(2) f(p) = p. \tag{2}
If p=1p = 1, substituting (q,1)(q, 1) into the original equation and combining with (2) gives f(1q)=1f(\frac{1}{q}) = 1.
Thus the statement holds when g(pq)=0g(\frac{p}{q}) = 0.

Suppose the statement holds when g(pq)=i1g(\frac{p}{q}) = i - 1; then when g(pq)=ig(\frac{p}{q}) = i, we discuss two cases.

Case (1): pq>1\frac{p}{q} > 1. Let n=pqn = \lfloor \frac{p}{q} \rfloor, then by (1) we know g(pnqq)=i1g(\frac{p-nq}{q}) = i-1. Substituting (pnqq,n)(\frac{p-nq}{q}, n) into the original equation and combining with (1) and the induction hypothesis, we get
f(pq)=(pnq)+nq=p.(3) f(\frac{p}{q}) = (p-nq) + nq = p. \tag{3}

Case (2): pq<1\frac{p}{q} < 1. Since qp>1\frac{q}{p} > 1, by (1) we know g(p+qp)=g(qp)=ig(\frac{p+q}{p}) = g(\frac{q}{p}) = i.
Also p+qp>qp>1\frac{p+q}{p} > \frac{q}{p} > 1, so by (3) we know f(p+qp)=p+qf(\frac{p+q}{p}) = p+q, f(qp)=qf(\frac{q}{p}) = q
Substituting (qp,1)(\frac{q}{p}, 1) into the original equation gives f(pq)=(p+q)q=pf(\frac{p}{q}) = (p+q) - q = p.
Combining the above, the statement holds when g(pq)=ig(\frac{p}{q}) = i. Hence by mathematical induction the statement always holds.
Therefore, f(pq)=pf(\frac{p}{q}) = p, where p,qp, q are any coprime positive integers.

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.