IMC 2017 · Day 1 · P3

We prove that the answer is yes; for every $S \subset \{1, 2, \dots, 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 \cdots 2^{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, \dots)$ and $(c_1, c_2, \dots)$ satisfy $b_{k+1} = \frac{b_k (b_k + 1)}{2}$ and $c_{k+1} = \frac{c_k (c_k + 1)}{2}$ for $k \ge 1$, and $c_1 = b_1 + 2^m$. Then for each $k = 1, \dots 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 (c_k + 1)}{2} &\equiv \frac{\bigl( b_k + 2^{m-k+1} \bigr) \bigl( b_k + 2^{m-k+1} + 1 \bigr)}{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, \dots)$ 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, \dots)$ 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 \pmod 2$ 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, \dots, 2017$, we obtain a suitable sequence $(w_k)$.