4. The sequence $\left(x_{n}\right)_{n=1}^{\infty} \mathrm{s}$ has the first term $x_{1}=1$ and for every $n>1$ satisfies the condition

$$
x_{n}=x_{n-1}^{ \pm 1}+x_{n-2}^{ \pm 1}+\ldots+x_{1}^{ \pm 1}
$$

with an appropriate choice of the signs "±" in the exponents of the powers.

a) Determine whether any term of such a sequence must be greater than 1000.

b) Find the smallest possible value of the term $x_{1000000}$.

c) Prove that the inequality $x_{n}<4$ cannot hold for nine terms $x_{n}$ of such a sequence.

II. round of category A takes place

## on Tuesday, January 14, 2003

so that it starts in the morning and the contestants have 4 hours of pure time to solve the problems. Each problem can earn the contestant 6 points, and a successful solver is a student who scores 10 points or more. These details will be communicated to the students before the start of the competition.
4. First, we notice that due to the equality $x_{1}=1$, it holds that

$$
\begin{aligned}
& x_{2}=x_{1}^{ \pm 1}=1^{ \pm 1}=1 \\
& x_{3}=x_{2}^{ \pm 1}+x_{1}^{ \pm 1}=1^{ \pm 1}+1^{ \pm 1}=2
\end{aligned}
$$

Since for every $x>0$ both numbers $x^{+1}, x^{-1}$ are positive, it follows easily by mathematical induction that the inequality $x_{n} \geqq 1$ is satisfied for every $n$. If $x \geqq 1$, then however $010^{3}$. Suppose on the contrary that for every $k$ the opposite inequality $x_{k} \leqq 10^{3}$ holds. From the left inequality in (2) then for every $n>4$ we get the estimate

$$
x_{n} \geqq \frac{5}{2}+\underbrace{10^{-3}+10^{-3}+\ldots+10^{-3}}_{(n-4) \text { times }}=\frac{5}{2}+(n-4) \cdot 10^{-3} .
$$

From this, however, it follows that $x_{n}>10^{3}$ for every $n>10^{6}+4$, which is a contradiction.

b) We first prove that from the right inequalities in (2) the estimate $x_{n} \leqq 2^{n-2}$ follows for every $n \geqq 2$. We use induction: for $n=2$ and $n=3$ it holds according to (1) that $x_{n}=2^{n-2}$;
let $n \geqq 4$ and suppose that for all $k \in\{2,3, \ldots, n-1\}$ it holds that $x_{k} \leqq 2^{k-2}$, then from (2) we get

$$
x_{n} \leqq 1+\left(1+2+2^{2}+\ldots+2^{n-3}\right)=1+\left(2^{n-2}-1\right)=2^{n-2}
$$

This completes the induction proof.

Substituting the estimates $x_{n} \leqq 2^{n-2}$ into the left inequality in (2), we get for the value of $x_{10^{6}}$ the lower estimate

$$
x_{10^{6}} \geqq 2+\frac{1}{2}+\frac{1}{2^{2}}+\ldots+\frac{1}{2^{10^{6}-3}}=3-\frac{1}{2^{10^{6}-3}} .
$$

This, together with the example of a suitable sequence

$$
\begin{aligned}
x_{n} & =x_{n-1}+x_{n-2}+\ldots+x_{1} \quad\left(n \in\left\{2,3, \ldots, 10^{6}-1\right\}\right) \\
x_{10^{6}} & =x_{10^{6}-1}^{-1}+x_{10^{6}-2}^{-1}+\ldots+x_{2}^{-1}+x_{1}^{-1}
\end{aligned}
$$

where $x_{n}=2^{n-2}$ for every $n \in\left\{2,3, \ldots, 10^{6}-1\right\}$ and $x_{10^{6}}=3-2^{3-10^{6}}$, shows that the smallest possible value of the term $x_{10^{6}}$ is $3-2^{3-10^{6}}$.

c) Suppose that the inequality $x_{n}<4$ holds for nine indices $n$. Then there exist indices $n_{1}<n_{2}<\ldots<n_{9}$ such that

$$
\begin{gathered}
x_{n_{1}}<4, \quad x_{n_{2}}>f(4)>4.28, \quad x_{n_{3}}>f(4.28)>4.54, \\
x_{n_{4}}>f(4.54)>4.78, \quad x_{n_{5}}>f(4.78)>5.00, \\
x_{n_{6}}>f(5.00)>5.20, \quad x_{n_{7}}>f(5.20)>5.38, \\
x_{n_{8}}>f(5.38)>5.54, \quad x_{n_{9}} \geqq f(5.54)>5.68
\end{gathered}
$$

The last inequality, however, is in contradiction with the condition $x_{n_{k}}<4$ determining the selection of indices $n_{k}$. Therefore, the inequality $x_{n}<4$ cannot hold for nine indices $n$.

For a complete solution, award 6 points, 2 points for each part a), b), and c). For part c), award 0 points if the solver only proves that the inequality $x_{n}<4$ cannot hold for the first nine terms $x_{n}$. Considerations about removing terms or increasing or decreasing their values will likely always be incorrect or incomplete.