Maths Olympiad Prep

Library / /80 of 397

Algebra Difficulty 5.2 AIME, harder Prove it Taiwan

Find the smallest positive integer nn satisfying the following condition:
There exists a set of distinct positive integers s1,s2,,sns_1, s_2, \dots, s_n such that
(11s1)(11s2)(11sn)=17670. (1 - \frac{1}{s_1})(1 - \frac{1}{s_2})\cdots(1 - \frac{1}{s_n}) = \frac{17}{670}.

Solution

Answer: n=39n = 39.

Without loss of generality, assume s1<s2<<sns_1 < s_2 < \cdots < s_n. Clearly, s1>1s_1 > 1, otherwise 11s1=01 - \frac{1}{s_1} = 0. Therefore, 2s1s21sn(n1)2 \le s_1 \le s_2 - 1 \le \cdots \le s_n - (n-1). Hence sii+1,i=1,,ns_i \ge i + 1, \forall i = 1, \cdots, n. From the given condition we obtain
17670=(11s1)(11s2)(11sn)(112)(113)(11n+1)=(112)(113)(11n+1)=1n+1n+167017>39n39. \begin{aligned} \frac{17}{670} &= (1 - \frac{1}{s_1})(1 - \frac{1}{s_2})\cdots(1 - \frac{1}{s_n}) \\ &\ge (1 - \frac{1}{2})(1 - \frac{1}{3})\cdots(1 - \frac{1}{n+1}) \\ &= (1 - \frac{1}{2})(1 - \frac{1}{3})\cdots(1 - \frac{1}{n+1}) = \frac{1}{n+1} \\ n + 1 &\ge \frac{670}{17} > 39 \\ n &\ge 39. \end{aligned}

Next we prove that n=39n = 39 satisfies the requirement.

Consider the 39 distinct positive integers: 2,3,,33,35,36,40,672, 3, \dots, 33, 35, 36, 40, 67. We obtain
12233233343539406667=1767. \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{32}{33} \cdot \frac{34}{35} \cdot \frac{39}{40} \cdot \frac{66}{67} = \frac{17}{67}.
This completes the proof.

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 translated into English from zh; metadata (topic, difficulty) added by this project.