uniolympiads Ελληνικά

IMC 2017, Day 1, Problem 3

For any positive integer mm, denote by P(m)P(m) the product of positive divisors of mm (e.g. P(6)=36P(6) = 36). For every positive integer nn define the sequence

a1(n)=n,ak+1(n)=P(ak(n))(k=1,2,…,2016).a_1(n) = n, \qquad a_{k+1}(n) = P(a_k(n)) \quad (k = 1, 2, \dots, 2016).

Determine whether for every set S⊆{1,2,…,2017}S \subseteq \{1, 2, \dots, 2017\}, there exists a positive integer nn such that the following condition is satisfied:

For every kk with 1≤k≤20171 \le k \le 2017, the number ak(n)a_k(n) is a perfect square if and only if k∈Sk \in S.

Original from the official PDFFor any positive integer m , denote by P (m) the product of positive divisors of m (e.g. P (6) = 36 ). For every positive integer n dene the sequence a 1 (n) = n, a k+1 (n) = P (a k (n)) (k = 1, 2, . . . , 2016). Determine whether for every set S ⊆ {1, 2, . . . , 2017} , there exists a positive integer n such that the following condition is satised: For every k with 1 ≤ k ≤ 2017 , the number a k (n) is a perfect square if and only if k ∈ S .

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(Proposed by Matko Ljulj , University of Zagreb)

Solution. We prove that the answer is yes; for every S⊂{1,2,…,2017}S\subset\{1,2,\ldots,2017\} there exists a suitable nn. Specially, nn can be a power of 22: n=2w1n = 2^{w_1} with some nonnegative integer w1w_1. Write ak(n)=2wka_k(n) = 2^{w_k}; then

2wk+1=ak+1(n)=P(ak(n))=P(2wk)=1⋅2⋅4⋯2wk=2wk(wk+1)2,2^{w_{k+1}} = a_{k+1}(n) = P(a_k(n)) = P(2^{w_k}) = 1\cdot 2\cdot 4\cdots 2^{w_k} = 2^{\frac{w_k(w_k+1)}{2}},
so
wk+1=wk(wk+1)2.w_{k+1} = \frac{w_k(w_k+1)}{2}.
The proof will be completed if we prove that for each choice of SS there exists an initial value w1w_1 such that wkw_k is even if and only if k∈Sk\in S.

Lemma. Suppose that the sequences (b1,b2,…)(b_1,b_2,\ldots) and (c1,c2,…)(c_1,c_2,\ldots) satisfy bk+1=bk(bk+1)2b_{k+1} = \frac{b_k(b_k+1)}{2} and ck+1=ck(ck+1)2c_{k+1} = \frac{c_k(c_k+1)}{2} for k≥1k\ge 1, and c1=b1+2mc_1 = b_1 + 2^m. Then for each k=1,…mk = 1,\ldots m we have ck≡bk+2m−k+1(mod2m−k+2)c_k \equiv b_k + 2^{m-k+1} \pmod{2^{m-k+2}}.

As an immediate corollary, we have bk≡ck(mod2)b_k\equiv c_k \pmod 2 for 1≤k≤m1\le k\le m and bm+1≡cm+1+1(mod2)b_{m+1}\equiv c_{m+1}+1 \pmod 2.

Proof. We prove the by induction. For k=1k = 1 we have c1=b1+2mc_1 = b_1 + 2^m so the statement holds. Suppose the statement is true for some k<mk < m, then for k+1k+1 we have

ck+1=ck (ck+1)2≡(bk+2m−k+1)(bk+2m−k+1+1)2=bk2+2m−k+2bk+22m−2k+2+bk+2m−k+12==bk(bk+1)2+2m−k+2m−k+1bk+22m−2k+1≡bk(bk+1)2+2m−k(mod2m−k+1),\begin{aligned} c_{k+1} &= \frac{c_k\,(c_k+1)}{2} \equiv \frac{\big(b_k + 2^{m-k+1}\big)\big(b_k + 2^{m-k+1} + 1\big)}{2} \\ &= \frac{b_k^2 + 2^{m-k+2}b_k + 2^{2m-2k+2} + b_k + 2^{m-k+1}}{2} = \\ &= \frac{b_k(b_k+1)}{2} + 2^{m-k} + 2^{m-k+1}b_k + 2^{2m-2k+1} \equiv \frac{b_k(b_k+1)}{2} + 2^{m-k} \pmod{2^{m-k+1}}, \end{aligned}
therefore ck+1≡bk+1+2m−(k+1)+1(mod2m−(k+1)+2)c_{k+1} \equiv b_{k+1} + 2^{m-(k+1)+1} \pmod{2^{m-(k+1)+2}}.

Going back to the solution of the problem, for every 1≤m≤20171\le m\le 2017 we construct inductively a sequence (v1,v2,…)(v_1,v_2,\ldots) such that vk+1=vk(vk+1)2v_{k+1} = \frac{v_k(v_k+1)}{2}, and for every 1≤k≤m1\le k\le m, vkv_k is even if and only if k∈Sk\in S.

For m=1m = 1 we can choose v1=0v_1 = 0 if 1∈S1\in S or v1=1v_1 = 1 if 1∉S1\notin S. If we already have such a sequence (v1,v2,…)(v_1,v_2,\ldots) for a positive integer mm, we can choose either the same sequence or choose v1′=v1+2mv'_1 = v_1 + 2^m and apply the same recurrence vk+1′=vk′(vk′+1)2v'_{k+1} = \frac{v'_k(v'_k+1)}{2}. By the Lemma, we have vk≡vk′(mod2)v_k\equiv v'_k \pmod 2 for k≤mk\le m, but vm+1v_{m+1} and vm+1v_{m+1} have opposite parities; hence, either the sequence (vk)(v_k) or the sequence (vk′)(v'_k) satisfies the condition for m+1m+1.

Repeating this process for m=1,2,…,2017m = 1,2,\ldots,2017, we obtain a suitable sequence (wk)(w_k).

Transcribed from the official solutions, pages 2–3. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?