Maths Olympiad Prep

Library / /111 of 128

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
(11x1)(11x2)(11x3)(11xn)=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
2x1x21x32xn(n1) 2 \leq x_{1} \leq x_{2}-1 \leq x_{3}-2 \leq \cdots \leq x_{n}-(n-1)
and so xii+1x_{i} \geq i+1 for 1in1 \leq i \leq n.
152013=(11x1)(11x2)(11x3)(11xn)(112)(113)(114)(11n+1)=122334nn+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 n134n \geq 134.

It remains to show that n=134n=134 can be attained. Set xi=i+1x_{i}=i+1 for 1i1331 \leq i \leq 133, and x134=671x_{134}=671. Then
(11x1)(11x2)(11x3)(11xn)=1134670671=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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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