I am baffling this question for a couple of days now and haven't seen a proof to this yet.

So as the title says: We have $n$ numbers such that their sum is $10n$ and we need to prove using dirichlet principle (pigeonhole principle) that there exist $k$ out of these $n$ numbers such that their sum is at least $10k$

I tried at least using the contrary:

Assume on the contrary that there exist $k$ numbers from these $n$ numbers such that their sum is at most $10k-1$ then we have $n-k$ numbers such that their sum is at least $10n-(10k-1)=10n-10k+1$

Here I get stuck not knowing how to proceed nor understanding what are the pigeons/pigeonholes here.

## Best Answer

Let $L=\operatorname{lcm}(n,k)$ so both $n,k\mid L$. Let your numbers be $a_1,a_2,\ldots a_n$.

Now replicate this sequence $\frac{L}{n}$ times to get the following sequence:

$$\underbrace{\underbrace{a_1, a_2, \ldots, a_n}, \underbrace{a_1, a_2, \ldots, a_n}, \ldots, \underbrace{a_1, a_2, \ldots, a_n}}_{\frac{L}{n}}$$

The sum of all those numbers is at least $10n\frac{L}{n}=10L$.

On the other hand, let's suppose that the sum of any $k$ numbers is less than $10k$. Break this sequence into groups of $k$ numbers:

$$\underbrace{\underbrace{a_1, a_2, \ldots, a_k}, \underbrace{a_{k+1},\ldots},\ldots,\underbrace{a_{n-k+1}, a_{n-k+2}, \ldots, a_n}}_{\frac{L}{k}}$$

the sum of all those numbers will be less than $10k\frac{L}{k}=10L$ - a contradiction.