$2n-1$ distinct positive real numbers with sum $S $ are given. Prove that there are at least $\binom {2n-2}{n-1}$ different ways to choose $n $ numbers among them such that their sum is at least $\frac {S}{2}$. Proposed by Amirhossein Gorzi
Problem
Source: Iranian TST 2018, third exam day 2, problem 5
Tags: combinatorics, Iran, Iranian TST
21.04.2018 15:14
Call a subset of size $n-1$ bad if it's elements add to more than $\frac{S}{2}$ and good otherwise. There cannot exist two disjoint bad subsets, as otherwise the sum of their combined $2n-2$ elements add to more than $S$. Hence all bad subsets pairwise intersect. By the Erdős–Ko–Rado theorem, there are at most $\binom{2n-2}{n-2}$ bad subsets. Hence the number of good subsets is at least $\binom{2n-1}{n-1}-\binom{2n-2}{n-2}=\binom{2n-2}{n-1}$. The complement of any good subset is a set of $n$ elements adding to at least $\frac{S}{2}$, so we are done.
27.04.2019 03:28
An approach for those who aren't acquainted with Erdős–Ko–Rado ... Lemma: For any $2n-1$ numbers $x_1,...,x_{2n-1}$ arranged on a circle in clockwise order (indices $\pmod {2n-1}$) there exist at least $n$ values $i$ such that $x_i + ... + x_{i+n-1}$ has sum $\ge S/2$ where $S:=\sum_{i=1}^{2n-1}x_i$. Proof: Consider the complement of each sum block it is equivalent to show that there are at least $n$ values $i$ such that $s_i:= x_i+...+x_{i+n-2} \le S/2$. Let the set of $i$ with $s_i > S/2$ be $I$. If $\exists \ i,j \in I $ such that $i \equiv n + j \pmod {2n-1}$ then we get a contradiction when we sum these two together. Therefore $I$ has no two elements differing by $n-1$. Now arrange $n,2n,3n,...,(2n-1)n$ around the circle and color the elements in $I$. No two elements are colored so $|I| < n-1$ as desired. With the lemma, randomly choose $n$ numbers, the probability (that their sum is at least $S/2$) is at least $\frac{n}{2n-1}$ as desired.
24.08.2019 22:28
Here is pretty simple solution.Let $a_1<a_2...<a_{2n-1}$ be $2n-1$ given numbers.First take out $a_1$. Then we have $\frac{\binom{2n-2}{n-1}}{2}$ pairs of unordered $n-1$-tuples (without $a_1$). Next one of them has sum greater than or equal to $\frac{S-a_1}{2}$ so add $a_1$ to this $n-1$-tuple. This way we get $\frac{\binom{2n-2}{n-1}}{2}$ ; $n$-tuples with sum $\ge$ than $\frac{S}{2}$. Next consider process: from $a_2...a_{2n-1}$ take two distinct $n-1$-tuples and as already noted one has sum $\ge$ $\frac{S-a_1}{2}$. Call this $n-1$-tuple $A$. To $A$ we add one element from other $n-1$-tuple. Obviously now $A$ has sum greater than $\frac{S}{2}$. To $A$ we could have added $n-1$ elements and we get $A$ in $\frac{\binom{2n-2}{n-1}}{2}$ ways. So by process we get $(n-1)\frac{\binom{2n-2}{n-1}}{2}$ ; $n$-tuples with sum $\ge$ $\frac{S}{2}$. Now we show that if $n$-tuple $b_1,b_2,..,b_n$ is chosen in this process in can occur at most $n-1$ times. When chosing $A$ we have to chose some subset of $b_1,b_2,..,b_n$ in order for it to occur. Next from other set there is unique element that when added to $A$ makes $b_1,b_2,..,b_n$. Thus every subset occurs at most $n-1$ and from this we get another $\frac{\binom{2n-2}{n-1}}{2}$ so we are done.
29.07.2020 13:59
Arrange a random permutation of the numbers in a circle . Label the numbers as $a_1,a_2, \dots ,a_{2n-1}$ . We define the following sums $:=$ $$ S_i \stackrel{\text {def}}{:=} a_i +a_{i+1} + a_{i+2} + \dots a_{i+n-1}$$(Indices taken $\pmod {2n-1}$ ) Claim : Atleast $n$ of these partial sums are not less than $\frac S2$ . Proof := FTSOC assume not . Hence there are atleast $n$ indices $i_1,i_2, \dots ,i_n$ such that $S_{i_j} < \frac S2$ for all $1 \leq j \leq n$. Note that by Pigeonhole, there must exist indices $i_x$ and $i_y$ such that $i_x-i_y \equiv n \pmod {2n-1}.$ This is because there are $n-1$ sets of the form $\{i, i+n\}$ and we are picking $n$ indices. Next note that we have $:=$ $$2 \times \frac S2 > S_{i_x}+S_{i_y} = \sum_{i=0}^{n-1} i_{x+i} + \sum_{j=0}^{n-1} i_{y+j} = \left( \sum_{i=1}^{2n-1}a_i \right)+ a_x > S $$ So we have the desired contradiction and the claim holds. Now note that for a given good sum $S_i$ it can exist in $n! \times (\{(2n-1)-n+1\}-1)!= (n-1)! \times n!$ permutations . Hence total number ways are atleast $:=$ $$\frac {(2n-1-1)! \times n}{n! \times (n-1)!}= \binom {2n-2}{n-1}$$ We are done $\blacksquare$
25.10.2020 10:15
Let $a$ be the smallest element among the $2n-1$ numbers.Denote $f(n)=\binom{2n-2}{n-1}$. Claim: There are atleast $\frac{f(n)}{2}$ sets with sum atleast $\frac{S}{2}$ which contains $a$. $\emph {proof.}$ For any set $A$ which does not contains $a$,we have, $sum(A)+sum(A^c-\{a\})=S-a$.So one of the summands is at least $\frac{S-a}{2}$.Moreover,we can pair two $n-1$-sets one with sum of elements atleast $\frac{S-a}{2}$ and the other with sum of elements atmost $\frac{S-a}{2}$.There are $\frac{\binom{2n-2}{n-1}}{2}$ such pairs.Now inserting $a$ in the set whose sum of element is atleast $\frac{s-a}{2}$ we get a valid set.$\blacksquare$ Let $\mathcal T$ be the collection of all these sets containing $a$ and element-sum atleast $\frac{S}{2}$. Claim:There exists atleast atleast $\frac{f(n)}{2}$ sets which does not contain $a$ and sum of elements is atleast $\frac{a}{2}$. $\emph{proof.}$ The idea is to take a set $A$ from $\mathcal T$ and replace $a$ by some other number currently not in $A$ and then count the number of new sets appear. Observe that if we take $A\in \mathcal T$ replace $a\in A$ with some number the produced set has sum atleast $\frac{S}{2}$ because of the minimality of $a$. Now obserbe that $A\in \mathcal T$ does not contains $n-1$ numbers from the $2n-1$ numbers.So for this $n-1$ numbers we will get $n-1$ distinct sets.So totally we will get $(n-1)\frac{f(n)}{2}$ sets counted with multiplicity. Now we will find how many times a set is counted. By the opperation, $\{a\}\cup X$ is transferred into $\{c\}\cup X$ for some $c$.Take any element $d$ from $X$ in $(n-1)$ ways.For this fixed $d$ there can be atmost 1 set $Y$ such that, $\{c\}\cup X=\{d\}\cup Y$ holds.Indeed $Y=\{c\}\cup X-\{d\}$. Also observe that $\{c\}\cup X\ne \{c\}\cup Y$ for $Y\ne X$. Hence ,any set is counted $(n-1)$ times. Hence,we get $(n-1)\frac{f(n)}{2}\frac{1}{n-1}=\frac{f(n)}{2}$ sets.$\blacksquare$ From the above 2 claims we get $f(n)$ sets with sum of elements $\frac{S}{2}$.$\blacksquare$
28.03.2022 09:39
Lazy solution outline: Let $x_1,\cdots,x_{2n-1}$ be our variables. Indices are taken mod $2n-1$. Claim: Let $S_j=\sum\limits_{i=j}^{j+n-1} x_j$ then at least $n$ $S_j$'s are at least $\frac S2$ Proof: Note one of $S_j, S_{n+j}$ must be at least $\frac S2$ since $S_j+S_{n-j}=S+x_{n+j}$. Now if I travel $S_j, S_{n+j}, S_{2n+j}, \cdots, \cdots, S_{(2n-1)n+j}, S_j$ then it's easy to see at least $n$ of them is at least $\frac S2$ If I select a random ordering of $1,\cdots,2n-1$, I get at least $n$ out of $2n-1$ sums are at least $\frac S2$. Summing over all random orderings, I can see the probability that a sum has at least $\frac S2$ is at least $\frac{n}{2n-1}$, which gives the desired result.
23.05.2022 22:07
The method of solving the problem without Erdős–Ko–Rado theorem (by considering a random cyclic permutation) just seems equivalent to the proof of Erdős–Ko–Rado theorem (Wikipedia). Can someone please tell the motivation behind it ? The only little motivation I can see is the equality case.