9,10,11 |
| :---: | :---: | :---: | :---: |
|  | Iterations | ] |  |
|  | Integer and integer-valued polynomials |  |  |
|  | Rational and irrational numbers |  |  |
|  | Sequences (other). |  |  |
|  | Processes and operations |  |  |

Authors: Shapovalov A.V., Doienko V.V.

From the available sequences $\left\{b_{n}\right\}$ and $\left\{c_{n}\right\}$ (possibly $\left\{b_{n}\right\}$ coincides with $\left\{c_{n}\right\}$), it is allowed to obtain sequences $\left\{b_{n}+c_{n}\right\}$, $\left\{b_{n}-c_{n}\right\}$, $\left\{b_{n} c_{n}\right\}$, and $\left\{{ }^{b_{n} /} c_{n}\right\}$ (if all terms of the sequence $\left\{c_{n}\right\}$ are different from 0). Additionally, from any available sequence, a new one can be obtained by removing several initial terms. Initially, there is only the sequence $\left\{a_{n}\right\}$. Can the sequence $\{n\}$, that is, $1,2,3,4, \ldots$, be obtained from it using the described operations if

a) $a_{n}=n^{2} ;$

b) $a_{n}=n+\sqrt{2}$

c) $a_{n}=\frac{n^{2000}+1}{n} ?$
Let's explain how to act in points a) and b).

The allowed operations can transform the sequence $\left\{a_{n}\right\}$ into the sequence $\left\{a_{n+1}-a_{n}\right\}$. Let's denote such a transformation by $T$, and the $m$-fold application of transformation $T$ by $T^{m}$. Note that if $P$ is a polynomial of degree $m-1$, then applying $T$ to the sequence $\{P(n)\}$ yields the sequence $\{Q(n)\}$, where $Q$ is a polynomial of degree $m-2$. From this, it follows that applying $T^{m}$ to $\{P(n)\}$ yields the zero sequence. Additionally, we will use the sequence $I$, all of whose terms are ones (which can be obtained by dividing a given sequence without zeros by itself). Adding this sequence to itself $n-1$ times, we get the sequence $n I$ (where $n$ is a natural number).

a) Applying the transformation $T$ to $\left\{n^{2}\right\}$, we get the sequence $\{2 n+1\}$. Subtracting $I$, we get $\{2 n\}$; finally, dividing by $2 I$, we get $\{n\}$.
b) Applying the transformation $T^{2000}$ to the sequence $a_{n}=n^{1999}+1 / n$, we get the sequence

$\left\{\frac{2000!}{n(n+1) \ldots(n+2000)}\right\}$

Dividing $2000!$ by this sequence, we get $\{n(n+1) \ldots(n+2000)\}$. Finally, applying the transformation $T^{2000}$ to this sequence, we get a sequence of the form $\{a n+b\}$, where $a$ and $b$ are integers, and $a \neq 0$. Further actions are clear.

c) Let's prove that the sequence $\{n\}$ cannot be obtained. For this, note that all sequences that can be obtained from $\{n+\sqrt{2}\}$ have the form $\left\{\frac{P(n+\sqrt{2})}{Q(n+\sqrt{2})}\right\}$, where $P$ and $Q$ are polynomials with integer coefficients. (Indeed, the original sequence has such a form. When adding, subtracting, multiplying, or dividing sequences of such form, we obviously get a sequence of such form again, and removing several terms is equivalent to replacing ${ }^{P(x)} / Q(x)$ with ${ }^{P(x+r)} / Q(x+r)$ for some natural number $r$, which can be represented in the required form by expanding all brackets in the numerator and denominator.) If the sequence $\{n\}$ can be represented in such a form, then the sequence whose all terms are $\sqrt{2}$ can also be represented in such a form. But from the equality $\frac{P(n+\sqrt{2})}{Q(n+\sqrt{2})}=\sqrt{2}$, it follows that the ratio of the leading coefficients of the polynomials $P$ and $Q$ is $\sqrt{2}$, which is impossible. Contradiction.

## Answer

a), b) Can c) Cannot.