# If the the sum of $n$ numbers is $10n$, Prove there exist $k$ numbers that their sum is at least $10k$

pigeonhole-principle

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.

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.