Olympiad Maths Prep

Track / Stage 6 / 366 of 400 #1366 of 2000

Problem 1366

National olympiad, first round
Algebra Difficulty 6.8 Prove it 2023 數學奧林匹亞競賽第一階段選訓營 · Taiwan · 2023

令 Q>1Q_{>1} 為所有大於 1 的有理數所成的集合。假設函數 f:Q>1→Zf: Q_{>1} \to \mathbb{Z} 滿足
f(q)={q−3若 q 為整數,⌈q⌉−3+f(1⌈q⌉−q)若 q 不為整數. f(q) = \begin{cases} q - 3 & \text{若 } q \text{ 為整數,} \\ \lceil q \rceil - 3 + f\left(\frac{1}{\lceil q \rceil - q}\right) & \text{若 } q \text{ 不為整數.} \end{cases}
證明：對於任意滿足 1a+1b=1\frac{1}{a} + \frac{1}{b} = 1 的 a,b∈Q>1a, b \in Q_{>1}, 必有 f(a)+f(b)=−2f(a) + f(b) = -2.

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, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

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