International Mathematics Competition
for University Students
2017

IMC2017: Day 1, Problem 3

3. For any positive integer $m$, denote by $P\left(m\right)$ the product of positive divisors of $m$ (e.g. $P(6)=36$). For every positive integer $n$ define the sequence $$ a_1(n)=n, \qquad a_{k+1}(n)=P(a_k(n)) \quad (k=1,2,\ldots,2016). $$

Determine whether for every set $S\subseteq\{1,2,\ldots,2017\}$, there exists a positive integer $n$ such that the following condition is satisfied:

   For every $k$ with $1\le k\le 2017$, the number $a_k(n)$ is a perfect square if and only if $k\in S$.

Proposed by: Matko Ljulj, University of Zagreb

Solution. We prove that the answer is yes; for every $S\subset\{1,2,\ldots,2017\}$ there exists a suitable $n$. Specially, $n$ can be a power of $2$: $n=2^{w_1}$ with some nonnegative integer $w_1$. Write $a_k(n)=2^{w_k}$; then $$ 2^{w_{k+1}} = a_{k+1}(n) = P(a_k(n)) = P(2^{w_k}) = 1\cdot 2\cdot 4\cdots2^{w_k} = 2^{\frac{w_k(w_k+1)}2}, $$ so $$ w_{k+1} = \frac{w_k(w_k+1)}2. $$ The proof will be completed if we prove that for each choice of $S$ there exists an initial value $w_1$ such that $w_k$ is even if and only if $k\in S$.

Lemma. Suppose that the sequences $(b_1,b_2,\ldots)$ and $(c_1,c_2,\ldots)$ satisfy $b_{k+1}=\frac{b_k\left(b_k+1\right)}{2}$ and $c_{k+1}=\frac{c_k\left(c_k+1\right)}{2}$ for $k\geq1$, and $c_1=b_1+2^m$. Then for each $k=1,\ldots m$ we have $c_k \equiv b_k + 2^{m-k+1} \pmod{2^{m-k+2}}$.

As an immediate corollary, we have $b_k\equiv c_k\pmod{2}$ for $1\le k\le m$ and $b_{m+1}\equiv c_{m+1}+1\pmod{2}$.

Proof. We prove the by induction. For $k=1$ we have $c_1=b_1+2^m$ so the statement holds. Suppose the statement is true for some $k<m$, then for $k+1$ we have \begin{align*} 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^{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{align*} therefore $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\le m\le 2017$ we construct inductively a sequence $(v_1,v_2,\ldots)$ such that $v_{k+1} = \frac{v_k(v_k+1)}2$, and for every $1\le k\le m$, $v_k$ is even if and only if $k\in S$.

For $m=1$ we can choose $v_1=0$ if $1\in S$ or $v_1=1$ if $1\notin S$. If we already have such a sequence $(v_1,v_2,\ldots)$ for a positive integer $m$, we can choose either the same sequence or choose $v'_1=v_1+2^m$ and apply the same recurrence $v'_{k+1} = \frac{v'_k(v'_k+1)}2$. By the Lemma, we have $v_k\equiv v'_k\pmod2$ for $k\le m$, but $v_{m+1}$ and $v_{m+1}$ have opposite parities; hence, either the sequence $(v_k)$ or the sequence $(v'_k)$ satisfies the condition for $m+1$.

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

Discussion on ArtOfProblemSolving.com