Maths Olympiad Prep

Library / /336 of 397

, 2023

Algebra Difficulty 6.8 National Olympiad Prove it Taiwan

Let Q>1Q_{>1} be the set of rational numbers greater than 1. Let f:Q>1→Zf : Q_{>1} \to \mathbb{Z} be a function that satisfies
f(q)={q−3if q is an integer,⌈q⌉−3+f(1⌈q⌉−q)otherwise. f(q) = \begin{cases} q - 3 & \text{if } q \text{ is an integer,} \\ \lceil q \rceil - 3 + f\left(\frac{1}{\lceil q \rceil - q}\right) & \text{otherwise.} \end{cases}
Show that for any a,b∈Q>1a, b \in Q_{>1} with 1a+1b=1\frac{1}{a} + \frac{1}{b} = 1, there always holds f(a)+f(b)=−2f(a) + f(b) = -2.

Solution

Suppose that a=m/na = m/n and b=m/(m−n)b = m/(m-n) where gcd⁡(m,n)=1\gcd(m,n) = 1. If n=12mn = \frac{1}{2}m then (m,n)=(2,1)(m,n) = (2,1) and the statement clearly holds in this case as f(2)=−1f(2) = -1. Therefore from now on we assume that n≠12mn \neq \frac{1}{2}m, and without loss of generality assume n<12mn < \frac{1}{2}m. We will induct on mm.

Assume that m>2m > 2 and the statement holds for all smaller mm. Since we assume that m>2nm > 2n, we have
f(a)=⌈mn⌉−3+f(1⌈mn⌉−mn)=1+⌈m−nn⌉−3+f(1⌈m−nn⌉−m−nn)=1+f(m−nn). \begin{aligned} f(a) &= \left\lceil \frac{m}{n} \right\rceil - 3 + f\left(\frac{1}{\left\lceil \frac{m}{n} \right\rceil - \frac{m}{n}}\right) \\ &= 1 + \left\lceil \frac{m-n}{n} \right\rceil - 3 + f\left(\frac{1}{\left\lceil \frac{m-n}{n} \right\rceil - \frac{m-n}{n}}\right) \\ &= 1 + f\left(\frac{m-n}{n}\right). \end{aligned}
We also have
f(b)=−1+f(12−mm−n)=−1+f(m−nm−2n). f(b) = -1 + f\left(\frac{1}{2 - \frac{m}{m-n}}\right) = -1 + f\left(\frac{m-n}{m-2n}\right).
Therefore by the inductive hypothesis,
f(a)+f(b)=f(m−nn)+f(m−nm−2n)=−2, f(a) + f(b) = f\left(\frac{m-n}{n}\right) + f\left(\frac{m-n}{m-2n}\right) = -2,
as desired.

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.