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

Question

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.

Answer 1

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.

Answer 2

Our boxes are the $k$-tuples out of the $n$ numbers $a_1,\ldots,a_n$. There are $\binom{n}{k}$ of them (e.g. $(a_1,\ldots,a_k)$). If we fix $a_i$, we have to choose $k-1$ out of $n-1$ numbers $a_1,\ldots,a_{i-1},a_{i+1},\ldots,a_n$, i.e. for each $a_i$ there are $\binom{n-1}{k-1}$ tuples, which contain $a_i$.

Assume the sum of each $k$-tuples is less then $10k$, then the sum of all $k$-tupels is less than $10k\cdot \binom{n}{k}=10n\binom{n-1}{k-1}$. I guess, you can handle it from here.

Maybe, it's easier to have a concrete example. Let $n=3$, $k=2$. We have $a_1+a_2+a_3=30$. Assume $a_1+a_2<20$, $a_1+a_3<20$ and $a_2+a_3<20$, it yields $$2\cdot 30=2(a_1+a_2+a_3)=(a_1+a_2)+(a_1+a_3)+(a_2+a_3)<3\cdot 20.$$ Contradiction!

Answer 3

It’s obviously true for k=0 and k=n. Assume n >= 2 so a non-trivial solution 0 < k < n may exist.

Divide the n numbers into two groups of k and n-k numbers. If they have sums < 10k and < 10(n-k) then the total sum is < 10n. Contradiction. So either the k or n-k numbers have a sum big enough.

Alternative: Assume there is a number >= 10, then we take that number and k=1 is a solution. If there is no number >= 10, then the sum of n numbers can’t be >= 10n.

(If you add: prove that for every k there exist k numbers such that their sum is >= 10k, thats a bit more difficult. Questions need to be precise)

Answer 4

(assume $1<k<n$ to make this non-trivial...) Plan: The largest $k$-element sum is larger than the average $k$-element sum, which average we should be able to estimate in terms of the average of the elements of $S$, by Fubinification.

Say $S$ is the original set of $n$ numbers. Let $F$ be the collection of all subsets of $S$ with exactly $k$ elements.

$\newcommand\C[2]{\begin{pmatrix} #1\\#2\end{pmatrix}}$

Since every element of $S$ lies in exactly $\C{n-1}{k-1}$ elements of $F$ it follows that $$\sum_{E\in F}\sum_{x\in E}x=\C{n-1}{k-1}\sum_{x\in S} x.$$ If $E_0$ is the element of $F$ maximizing $\sum_Ex$ then since $F$ has $\C nk$ elements we have $$10n\C{n-1}{k-1}\le\sum_{E\in F}\sum_Ex\le \C nk\sum_{E_0}x;$$now since $\C nk\le n\C{n-1}{k-1}$ (clear if you write it out in terms of factorials) this shows that $$\sum_{E_0}x\ge 10.$$