Maths Olympiad Prep

Library / Philippine Mathematical Olympiad /99 of 114

Philippine Mathematical Olympiad

Algebra Difficulty 6.7 National Olympiad Prove it Philippines

Problem:

Determine, with proof, the least positive integer nn for which there exist nn distinct positive integers x1,x2,x3,…,xnx_{1}, x_{2}, x_{3}, \ldots, x_{n} such that
(1−1x1)(1−1x2)(1−1x3)⋯(1−1xn)=152013 \left(1-\frac{1}{x_{1}}\right)\left(1-\frac{1}{x_{2}}\right)\left(1-\frac{1}{x_{3}}\right) \cdots\left(1-\frac{1}{x_{n}}\right)=\frac{15}{2013}

Solution

Solution:

Suppose x1,x2,x3,…,xnx_{1}, x_{2}, x_{3}, \ldots, x_{n} are distinct positive integers that satisfy the given equation. Without loss of generality, we assume that x1<x2<x3<⋯<xnx_{1}<x_{2}<x_{3}<\cdots<x_{n}. Then
2≤x1≤x2−1≤x3−2≤⋯≤xn−(n−1) 2 \leq x_{1} \leq x_{2}-1 \leq x_{3}-2 \leq \cdots \leq x_{n}-(n-1)
and so xi≥i+1x_{i} \geq i+1 for 1≤i≤n1 \leq i \leq n.
152013=(1−1x1)(1−1x2)(1−1x3)⋯(1−1xn)≥(1−12)(1−13)(1−14)⋯(1−1n+1)=12⋅23⋅34⋯nn+1=1n+1 \begin{aligned} \frac{15}{2013} & =\left(1-\frac{1}{x_{1}}\right)\left(1-\frac{1}{x_{2}}\right)\left(1-\frac{1}{x_{3}}\right) \cdots\left(1-\frac{1}{x_{n}}\right) \\ & \geq\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{4}\right) \cdots\left(1-\frac{1}{n+1}\right) \\ & =\frac{1}{2} \cdot \frac{2}{3} \cdot \frac{3}{4} \cdots \frac{n}{n+1} \\ & =\frac{1}{n+1} \end{aligned}
The preceding computation gives n≥134n \geq 134.

It remains to show that n=134n=134 can be attained. Set xi=i+1x_{i}=i+1 for 1≤i≤1331 \leq i \leq 133, and x134=671x_{134}=671. Then
(1−1x1)(1−1x2)(1−1x3)⋯(1−1xn)=1134⋅670671=5671=152013 \left(1-\frac{1}{x_{1}}\right)\left(1-\frac{1}{x_{2}}\right)\left(1-\frac{1}{x_{3}}\right) \cdots\left(1-\frac{1}{x_{n}}\right)=\frac{1}{134} \cdot \frac{670}{671}=\frac{5}{671}=\frac{15}{2013}
Therefore, the required minimum value of nn is 134134.

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.