Olympiad Maths Prep

Library / /49 of 60

Number theory Difficulty 6.5 National olympiad Prove it Ukraine

What is the maximum length of a sequence of positive integers a1,a2,,ana_1, a_2, \dots, a_n, if following conditions hold:
* a1>1a_1 > 1 is a prime number;
* for any i:2ini: 2 \le i \le n, aia1a2ai1a_i \vdash a_1 a_2 \dots a_{i-1} holds;
* an=22335577111113131717a_n = 2^2 \cdot 3^3 \cdot 5^5 \cdot 7^7 \cdot 11^{11} \cdot 13^{13} \cdot 17^{17}.

Solution

Let a1=pa_1 = p is prime. Then it is clear that
a2p,a3a2a1p2,a4a3a2a1p4,a5a4a3a2a1p8,a6a5a4a3a2a1p16. \begin{array}{ccc} a_2 \vdash p, & a_3 \vdash a_2 a_1 \vdash p^2, & a_4 \vdash a_3 a_2 a_1 \vdash p^4, \\ a_5 \vdash a_4 a_3 a_2 a_1 \vdash p^8, & a_6 \vdash a_5 a_4 a_3 a_2 a_1 \vdash p^{16}. \end{array}
Assume the length of the sequence is greater than 6, thus a7a6a5a4a3a2a1p32a_7 \vdash a_6 a_5 a_4 a_3 a_2 a_1 \vdash p^{32}, there is a prime number that divides a7a_7 and it is included with degree not less than 32. By conditions on ana_n that is not possible. Therefore, the maximum length is n=6n=6. The only prime number that is included with degree 16 in a6=22335577111113131717a_6 = 2^2 \cdot 3^3 \cdot 5^5 \cdot 7^7 \cdot 11^{11} \cdot 13^{13} \cdot 17^{17} is p=17p=17. This is the maximum value of a1a_1.

It suffices to show now, that such sequence exists. Take
a1=17, a2=17, a3=172, a4=174, a5=178, a6=22335577111113131717. a_1 = 17,\ a_2 = 17,\ a_3 = 17^2,\ a_4 = 17^4,\ a_5 = 17^8,\ a_6 = 2^2 \cdot 3^3 \cdot 5^5 \cdot 7^7 \cdot 11^{11} \cdot 13^{13} \cdot 17^{17}.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.