## Problem 2.

Determine the largest natural number $n$ for which the following statement is true:

There exist $n$ distinct non-zero natural numbers $x_{1}, x_{2}, \ldots, x_{n}$ with the property that for any numbers $a_{1}, a_{2}, \ldots, a_{n} \in\{-1,0,1\}$, not all zero, the number $n^{3}$ does not divide the number $a_{1} x_{1}+a_{2} x_{2}+\ldots+a_{n} x_{n}$.
Solution. For $n=9$ we choose $x_{1}=2^{0}, x_{2}=2^{1}, \ldots, x_{9}=2^{8}$. For any numbers $a_{1}, a_{2}, \ldots, a_{n} \in\{-1,0,1\}$, we have:

$$
\left|a_{1} x_{1}+a_{2} x_{2}+\ldots+a_{n} x_{n}\right| \leq 1+2+\ldots+2^{8}=2^{9}-1 < n^{3}$.

Let $A=\left\{x_{1}, x_{2}, \ldots, x_{n}\right\}$ be a set of $n$ distinct non-zero natural numbers and $\mathcal{P}(A)$ the set of its subsets. Since $|\mathcal{P}(A)|=2^{n}>n^{3}$, using the Pigeonhole Principle, we obtain two different subsets $B$ and $C$ of $A$ such that

$$
\sum_{x \in B} x \equiv \sum_{x \in C} x \quad\left(\bmod n^{3}\right)
$$

Choosing $a_{i}=1$ for the elements of $B \backslash C$, $a_{j}=-1$ for the elements of $C \backslash B$, and $a_{k}=0$ for the other elements of $A$, we find a combination $a_{1} x_{1}+a_{2} x_{2}+\ldots+a_{n} x_{n}$ that is divisible by $n^{3}$. Therefore, numbers $n \geqslant 10$ do not have the property stated in the problem, so the sought number is $n=9$.

Observations.

(O1) For the simple writing, without any justification, of a correct example in the case $n=9$, no points were awarded.

(O2) For not demonstrating the inequality $2^{n}>n^{3}$ for $n \geq 10$, one point was deducted from the 4 points allocated.

![](https://cdn.mathpix.com/cropped/2024_06_07_358793f0e2c2b567ccf8g-5.jpg?height=286&width=976&top_left_y=122&top_left_x=150)

## Second Selection Barrier for OBMJ  Bucharest, May 14, 2022

Solutions and grading scales