Maths Olympiad Prep

Track / Stage 6 / 365 of 400 #2005 of 2604

Problem 2005

National Olympiad, first round
Algebra Difficulty 6.8 Prove it Taiwan IMO Selection Camp · Taiwan · 2023

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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official 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.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty, ordering) added by this project.