Maths Olympiad Prep

Library / /33 of 43

Algebra Difficulty 8.1 Shortlist Find the answer

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, \quad a_{k+1}(n)=P\left(a_{k}(n)\right) \quad(k=1,2, \ldots, 2016) . Determine whether for every set S{1,2,,2017}S \subseteq\{1,2, \ldots, 2017\}, there exists a positive integer nn such that the following condition is satisfied: For every kk with 1k20171 \leq k \leq 2017, the number ak(n)a_{k}(n) is a perfect square if and only if kSk \in S.

A number or a short expression. Spacing and $ signs are ignored.

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 2: n=2w1n=2^{w_{1}} with some nonnegative integer w1w_{1}. Write ak(n)=2wk;a_{k}(n)=2^{w_{k}} ; then 2wk+1=ak+1(n)=P(ak(n))=P(2wk)=1242wk=2wk(wk+1)22^{w_{k+1}}=a_{k+1}(n)=P\left(a_{k}(n)\right)=P\left(2^{w_{k}}\right)=1 \cdot 2 \cdot 4 \cdots 2^{w_{k}}=2^{\frac{w_{k}\left(w_{k}+1\right)}{2}} so wk+1=wk(wk+1)2w_{k+1}=\frac{w_{k}\left(w_{k}+1\right)}{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 kSk \in S. Lemma. Suppose that the sequences (b1,b2,)\left(b_{1}, b_{2}, \ldots\right) and (c1,c2,)\left(c_{1}, c_{2}, \ldots\right) satisfy bk+1=bk(bk+1)2b_{k+1}=\frac{b_{k}\left(b_{k}+1\right)}{2} and ck+1=ck(ck+1)2c_{k+1}=\frac{c_{k}\left(c_{k}+1\right)}{2} for k1k \geq 1, and c1=b1+2mc_{1}=b_{1}+2^{m}. Then for each k=1,mk=1, \ldots m we have ckbk+2mk+1c_{k} \equiv b_{k}+2^{m-k+1} (mod2mk+2)\left(\bmod 2^{m-k+2}\right). As an immediate corollary, we have bkck(mod2)b_{k} \equiv c_{k}(\bmod 2) for 1km1 \leq k \leq m and bm+1cm+1+1b_{m+1} \equiv c_{m+1}+1 (mod2)(\bmod 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+2mk+1)(bk+2mk+1+1)2=bk2+2mk+2bk+22m2k+2+bk+2mk+12==bk(bk+1)2+2mk+2mk+1bk+22m2k+1bk(bk+1)2+2mk(mod2mk+1)\begin{aligned} c_{k+1} & =\frac{c_{k}\left(c_{k}+1\right)}{2} \equiv \frac{\left(b_{k}+2^{m-k+1}\right)\left(b_{k}+2^{m-k+1}+1\right)}{2} \\ & =\frac{b_{k}^{2}+2^{m-k+2} b_{k}+2^{2 m-2 k+2}+b_{k}+2^{m-k+1}}{2}= \\ & =\frac{b_{k}\left(b_{k}+1\right)}{2}+2^{m-k}+2^{m-k+1} b_{k}+2^{2 m-2 k+1} \equiv \frac{b_{k}\left(b_{k}+1\right)}{2}+2^{m-k} \quad\left(\bmod 2^{m-k+1}\right) \end{aligned} therefore ck+1bk+1+2m(k+1)+1(mod2m(k+1)+2)c_{k+1} \equiv b_{k+1}+2^{m-(k+1)+1}\left(\bmod 2^{m-(k+1)+2}\right). Going back to the solution of the problem, for every 1m20171 \leq m \leq 2017 we construct inductively a sequence (v1,v2,)\left(v_{1}, v_{2}, \ldots\right) such that vk+1=vk(vk+1)2v_{k+1}=\frac{v_{k}\left(v_{k}+1\right)}{2}, and for every 1km,vk1 \leq k \leq m, v_{k} is even if and only if kSk \in S. For m=1m=1 we can choose v1=0v_{1}=0 if 1S1 \in S or v1=1v_{1}=1 if 1S1 \notin S. If we already have such a sequence (v1,v2,)\left(v_{1}, v_{2}, \ldots\right) for a positive integer mm, we can choose either the same sequence or choose v1=v1+2mv_{1}^{\prime}=v_{1}+2^{m} and apply the same recurrence vk+1=vk(vk+1)2v_{k+1}^{\prime}=\frac{v_{k}^{\prime}\left(v_{k}^{\prime}+1\right)}{2}. By the Lemma, we have vkvkv_{k} \equiv v_{k}^{\prime} (mod2)(\bmod 2) for kmk \leq m, but vm+1v_{m+1} and vm+1v_{m+1} have opposite parities; hence, either the sequence (vk)\left(v_{k}\right) or the sequence (vk)\left(v_{k}^{\prime}\right) 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)\left(w_{k}\right).

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.