Let the number $a$ be written on the board initially. If $a=1,2$, we have $1, 2+2$ are perfect squares. Let $a\ge 3$. One can perform the following steps: $$a\to a+1\to 2a+2\to 2a+4\to 3a+6\to 3a+9\to 4a+12\to 4a+16\to \cdots$$Similarly, one can obtain all numbers in the form $k(a-1)+k^2$ and $ka+k^2$ where $k\in\mathbb{Z^+}$. One of the numbers $a-1, a$ is odd. Let this number be $2n+1$. ($a\ge 3\Rightarrow n\ge 1$). For $k=n^2$, we have $k(2n+1)+k^2=n^4+2n^3+n^2=(n^2+n)^2$, as desired.

Strong induction on $n$, with small $n$ being easy to check. Assume up to $n-1$ and consider $n$. If it is divisible by a square of a prime, say $p^2$, then $\frac{n}{p^2} < n$ and so if the sequence $a_1,\ldots,a_k$ yields a perfect square from $\frac{n}{p^2}$ (and there is such a sequence by the induction hypothesis), then $p^2a_1,\ldots,p^2a_k$ works for $n$. Now suppose $n$ is squarefree. If $n$ is even, then adding $2$ yields a multiple of $4$ and since $\frac{n+2}{4} < n$ we are done by the induction hypothesis for $\frac{n+2}{4}$ (note that every element in the sequence for $n+2$ will be a multiple of $4$ and in particular we cannot run into the issue of the first term being equal to $2$). If $n$ is odd, then adding $1$ either gives a non-squarefree number (and we are done from $\frac{n+1}{p^2}$), else adding $2$ yields $n+3$ as a multiple of $4$ (and we are done from $\frac{n+3}{4} < n$).

Let our initial number be $n$. We see that $1$ is a divisor of this number. Then from $n$ we can get $n+1$, the number itself is a divisor of the number, then we can double it and obtain $2(n+1)$. We see that $2$ is a divisor of this number which means from $2(n+1)$ we get $2(n+2)$, double again. We keep doing this adding $2^r$ every time $2^r$ is a divisor and then double after. We then get the following forms of numbers: $$2^{k-1}(n+k) \rightarrow 2^k(n+k) \rightarrow 2^k(n+k+1)$$Now we prove that the $2$ operation's divisors aren't equal. Which is the same thing as proving that $$2^{k-1}(n+k) \neq 2^k \Rightarrow n+k \neq 2$$If $k=0$ then we look at the operation $$n \rightarrow n+1 \rightarrow 2(n+1)$$If the operations were equal then we'll get $1=n+1$, a contradiction. Then we just check that it's true for $k \ge 1$. Since $k$ and $n$ are both $\ge 1$. We'll get that if $n+k=2$, the only solution would be $n=k=1$, but $n=1$ is already a perfect square, so we can just take $n>1$, and it won't be equal. So we can always do these kinds of operations. Now we prove that we can always get a perfect square, but if we keep doing these operations at some point we'll get an $r$ such that one of $$2^{2r}(n+2r) \hspace{0.5cm} 2^{2r}(n+2r+1)$$is a perfect square. $\textit{Q.E.D}$

There is actually an even easier inductive way. If $n$ is a multiple of $4$, use the sequence from $\frac{n}{4}$ (but with all terms multiplied by $4$) and if $n\equiv 3 \pmod 4$, then add $1$ and then use the sequence from $\frac{n+1}{4}$. If $n\equiv 2 \pmod 4$, then add $n$ and then in $2n = 4 \cdot \frac{n}{2}$ use the sequence from $\frac{n}{2}$ - the only trouble here is if the first term from this sequence, when multiplied by $4$, equals $n$ (since then we will have two consecutive equal numbers to be added), but this would imply that $\frac{n}{4}$ is an integer, contradiction. Finally, if $n\equiv 1 \pmod 4$, then add $n$ and then $2$ and in the result $2n+2 = 4 \cdot \frac{n+1}{2}$ use the sequence from $\frac{n+1}{2}$, multiplied by $4$.

$\textbf{Lemma:}$ For any natural $M$, there exists $x,y>2$ such that $M<\frac{x^2}{2^y}<M+1$. $\textbf{Proof:}$ Induct on $M$. $M=1$ is trivial. Assume that $M<\frac{x^2}{2^y}<M+1$. We will prove that there exist natural $u,v$ such that $M+1<\frac{u^2}{2^v}<M+2$. It is enough to find natural $u,v$ such that $\frac{u^2}{2^v} -\frac{x^2}{2^y}=1$. Choose $v=y+2t$ and $u=u'2^t$ such that $u'^2-x^2=2^y$.$\square$ Let $X$ be the number written on the board. If $X$ is odd power of two add $X$. Otherwise choose $x,y$ such that $X<\frac{x^2}{2^y}<X+2$ which is possible as a result of the lemma. We add the number itself on the board $y$ times, $X+X+2X+4X+...+2^{y-1}X=2^yX$. Now $2^{y+1}>x^2-2^yX>0$ . We add the power of $2$'s appear in the binary representation of $x^2-2^yX$ from bigger to smaller to $2^yX$. Observe that they are not equal and each one is a divisor of the number written on the board all the time. Also they cannot coincide with $2^iX$ because $X$ is odd. We reach $x^2$ at the end.

Assassino9931 wrote: Strong induction on $n$, with small $n$ being easy to check. Assume up to $n-1$ and consider $n$. If it is divisible by a square of a prime, say $p^2$, then $\frac{n}{p^2} < n$ and so if the sequence $a_1,\ldots,a_k$ yields a perfect square from $\frac{n}{p^2}$ (and there is such a sequence by the induction hypothesis), then $p^2a_1,\ldots,p^2a_k$ works for $n$. Now suppose $n$ is squarefree. If $n$ is even, then adding $2$ yields a multiple of $4$ and since $\frac{n+2}{4} < n$ we are done by the induction hypothesis for $\frac{n+2}{4}$ (note that every element in the sequence for $n+2$ will be a multiple of $4$ and in particular we cannot run into the issue of the first term being equal to $2$). If $n$ is odd, then adding $1$ either gives a non-squarefree number (and we are done from $\frac{n+1}{p^2}$), else adding $2$ yields $n+3$ as a multiple of $4$ (and we are done from $\frac{n+3}{4} < n$). The idea of decreasing square part is also used in RMM 2019/1

rafaello wrote: A positive integer is written on the board. Every minute Maxim adds to the number on the board one of its positive divisors, writes the result on the board and erases the previous number. However, it is forbidden for him to add the same number twice in a row. Prove that he can proceed in such a way that eventually a perfect square will appear on the board. Hmm does this work? Way less complicated than everything above: Note that if $n=6k$ then we can repeatedly do +2,+1,+3. We can also do +3,+1,+2. This will eventually hit a perfect square as infinitely many perfect squares are 3 mod 6 (just square any 3 mod 6 number). If the original number is 0 mod 6 we are done. If it is 5 mod 6, we can +1 and do +2 +1 +3 repeatedly. If it is 4 mod 6, we can +2 and do +3 +1 +2 repeatedly. If it is 3 mod 6, we can +3 and do +2 +1 +3 repeatedly. If it is 2 mod 6, we can double the number and do +2, followed by +3 +1 +2 repeatedly. (except if the original number is 2, in which case just make it 4.) If it is 1 mod 6, we can double the number twice and do +2, followed by +3 +1 +2 repeatedly. (except if the original number is 1, in which case we are already done.)

Proposed by Novikov Vladislav

We go by induction. The base cases $1, 2, 3, 4$ are easy ($1 \to 2 \to 4$ and $3 \to 4$). Suppose the result was true for everything less than $n$ for some $n >4$. If $n \equiv 1\pmod 4$, add $n$ by $1$ then $2$. If $n \equiv 2\pmod 4$, add by $2$. If $n \equiv 3\pmod 4$, add by $1$. Now we are at some multiple of $4$ that is at most $n + 3$ by performing moves with length at most $2$. Call it $4k$. Let the sequence from $k$ to a perfect square $k \to k_1 \to k_2 \to \cdots \to k_t$, where $k_t$ is a perfect square. Notice that $4k \to 4k_1 \to \cdots \to 4k_t$ is also a valid sequence of moves with lengths at least $4$. Hence we can make the moves from $n$ to $4k$ with length at most $2$ and then from $4k$ to $4k_t$, where $4k_t$ is a perfect square. The lengths of the moves won't intersect since the last move from $n$ to $4k$ is guaranteed to have a lower length than the first from $4k$ to $4k_t$.