Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /70 of 359

Taiwan IMO Selection Camp

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
(1−1s1)(1−1s2)⋯(1−1sn)=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 1−1s1=01 - \frac{1}{s_1} = 0. Therefore, 2≤s1≤s2−1≤⋯≤sn−(n−1)2 \le s_1 \le s_2 - 1 \le \cdots \le s_n - (n-1). Hence si≥i+1,∀i=1,⋯ ,ns_i \ge i + 1, \forall i = 1, \cdots, n. From the given condition we obtain
17670=(1−1s1)(1−1s2)⋯(1−1sn)≥(1−12)(1−13)⋯(1−1n+1)=(1−12)(1−13)⋯(1−1n+1)=1n+1n+1≥67017>39n≥39. \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
12⋅23⋅3233⋅3435⋅3940⋅6667=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,604 problems in a working order, from Junior Challenge 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.