Maths Olympiad Prep

Library / Thailand Mathematical Olympiad /2 of 15

Thailand Mathematical Olympiad

Algebra Difficulty 4.9 AIME Prove it Thailand

Let MM be a positive integer, and A={1,2,…,M+1}A = \{1, 2, \dots, M+1\}. Show that if ff is a bijection from AA to AA then
∑n=1M1f(n)+f(n+1)>MM+3. \sum_{n=1}^{M} \frac{1}{f(n) + f(n+1)} > \frac{M}{M+3}.

Solution

From the AM-HM inequality
∑n=1M1f(n)+f(n+1)>M2∑n=1M(f(n)+f(n+1))=M22∑n=1M+1f(n)−f(1)−f(M+1). \sum_{n=1}^{M} \frac{1}{f(n) + f(n+1)} > \frac{M^2}{\sum_{n=1}^{M} (f(n) + f(n+1))} = \frac{M^2}{2 \sum_{n=1}^{M+1} f(n) - f(1) - f(M+1)}.

Since ff is a bijection we have
∑n=1M+1f(n)=∑n=1M+1n=(M+1)(M+2)2. \sum_{n=1}^{M+1} f(n) = \sum_{n=1}^{M+1} n = \frac{(M+1)(M+2)}{2}.

Note that
f(1)+f(M+1)>2 f(1) + f(M+1) > 2
hence,
∑n=1M1f(n)+f(n+1)>M2(M+1)(M+2)−2=MM+3. \sum_{n=1}^{M} \frac{1}{f(n) + f(n+1)} > \frac{M^2}{(M+1)(M+2) - 2} = \frac{M}{M+3}.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.