Problem 1292

I. solution. We will prove that if $k$ is a natural number and $n$ is a positive integer, then the statement is true.

We apply complete induction on $k$. Suppose that the statement is true for all natural numbers up to $k$, we need to show that it is also true for $k+1$.

If the numbers are $a_{1}, a_{2}, a_{3}, \ldots, a_{n+k+1}$, then by the induction hypothesis, among the numbers $a_{1}, a_{2}, a_{3}, \ldots, a_{n+k}$, we can select $x \geq k+1$ numbers whose sum is divisible by $n$. If $x \geq k+2$, then the statement is true, as we can select at least $(k+1)+1$ numbers from $a_{1}, a_{2}, a_{3}, \ldots, a_{n+k+1}$. If $x=k+1$, then we remove these $k+1$ numbers from the set, and from the remaining $b_{1}, b_{2}, \ldots, b_{n}$ numbers, by the induction hypothesis, we can also select at least $0+1=1$ number such that their sum is divisible by $n$. Adding this number to the previously removed $k+1$ numbers, the sum will also be divisible by $n$, so we can select at least $k+2$ numbers.

To complete the proof, we only need to show that the statement is also true for $k=0$, that is, from $n$ numbers, we can select at least 1 number such that their sum is divisible by $n$.

If there is a number among them that is divisible by $n$, then we take this number.

If there is no number divisible by $n$, then denoting the numbers by $a_{1}, a_{2}, \ldots, a_{n}$, consider the remainders of the following sums when divided by $n$:

$$\begin{aligned} S_{1} & =a_{1} \\ S_{2} & =a_{1}+a_{2} \\ S_{3} & =a_{1}+a_{2}+a_{3} \\ \vdots & \\ S_{n} & =a_{1}+a_{2}+\ldots+a_{n} \end{aligned}$$

Since each of these is an integer, and dividing by $n$ can yield $n$ different remainders, by the pigeonhole principle, either there is a sum with a remainder of 0, or there are at least two sums with the same remainder. If a remainder of 0 occurs, then we have found some numbers whose sum is divisible by $n$. If there are at least two sums with the same remainder, $S_{i}$ and $S_{j}(i>j)$, then $S_{i}-S_{j}=a_{j+1}+a_{j+2}+\ldots+a_{i}$ is divisible by $n$, so we have also found some numbers whose sum is divisible by $n$.

Based on the work of Beke Csongor (Budapest, Békásmegyeri Veres Péter Gimn., 10th grade)

II. solution. We use the known and previously proven fact that from $n$ integers, we can always select some such that their sum is divisible by $n$.

Knowing this, we provide a procedure to find the appropriate at least $(k+1)$ integers.

Select $n$ numbers from the $n+k$ integers. From these $n$ integers, set aside those whose sum is divisible by $n$. Then, from the remaining numbers, again select $n$ numbers. From these, also set aside those whose sum is divisible by $n$. We repeat this procedure until it is no longer possible, that is, at most $n-1$ numbers are not set aside. The number of numbers set aside is therefore at least $(k+1)$ and we set them aside in groups such that the sum of each group is divisible by $n$, so the sum of all of them is also a multiple of $n$. This proves the statement.