Let $a_1,a_2,...,a_9$ be nine real numbers, not necessarily distinct, with average $m$. Let $A$ denote the number of triples $1 \le i < j < k \le 9$ for which $a_i + a_j + a_k \ge 3m$. What is the minimum possible value of $A$? Proposed by Ray Li
Problem
Source: ELMO 2013/1, by Ray Li; also Shortlist C3
Tags: pigeonhole principle, probability, expected value, combinatorics, Elmo, 2013
19.06.2013 18:55
The only problem I solved, hooray! Basically, you just show that at least one out of three triples belong to A, because otherwise we arrive at a contradiction. Then you just construct a set for which this is true, for example: $1,1,1,1,1,1,1,1,2$ EDIT: 300th post!
19.06.2013 18:59
19.06.2013 19:05
infiniteturtle's "one out of three" made it trivial :/ Note that the sum of all $a_i$ is $9m$. By the real number version of Pigeonhole Principle, if three numbers $x,y,z$ add up to $9m$, one of them must be at least $3m$. In particular, if we partition the $a_i$ into three triples and let $x,y,z$ be the sum of the elements in the first, second, triple respectively, at least one of these three triples sum to at least $3m$. So at least 1/3 of all triples have their sum at least $3m$. The number of triples is obviously $\binom{9}{3} = 84$, so at least $28$ triples have their sum at least $3m$ and hence $A \ge 28$. It remains to show that this is achievable; see infiniteturtle's construction. If a triple contains all 1s, its sum is $3 < \dfrac{10}{3} = 3 \cdot \dfrac{10}{9} = 3m$. There are $\binom{8}{3} = 56$ triples containing solely 1s, so $A \le 84-56 = 28$. EDIT: Sniped
19.06.2013 19:32
This is more-or-less borntobeweild's solution. Its what I would have turned in had I competed. I claim the answer is $28$. A construction is arrived at by considering $a_1 = a_2 = ... = a_8 = -1$ and $a_9 = 8$. Consider a random permutation $\sigma \in S_9$. Now consider the triplet $\{a_{\sigma(1)}, a_{\sigma(2)}, a_{\sigma(3)}\}$. It is clear that as least one of $\{a_{\sigma(1)}, a_{\sigma(2)}, a_{\sigma(3)}\}, \{a_{\sigma(4)}, a_{\sigma(4)}, a_{\sigma(6)}\}, \{a_{\sigma(7)}, a_{\sigma(8)}, a_{\sigma(9)}\}$ has a sum of elements at least $3m$ since the sums of all three sums equals $9m$. It follows that $\text{Pr}[a_{\sigma(1)} + a_{\sigma(2)} + a_{\sigma(3)} \ge 3m] \ge \frac{1}{3}$. It follows that the number of triplets whose sum is at least $3m$ numbers at least \[ \frac{1}{3} \dbinom{9}{3} = 28\] as desired.
19.06.2013 19:49
I get it, but how are we sure that it is possible to partition the 84 triples into 28 sets such that in each set, the numbers a_1, a_2, ..., a_9
19.06.2013 19:57
The solutions of borntobeweild and dinoboy do not require such a partition. chaotic_iak's solution does not explicitly require such a partition, but it is rather muddy in the relevant spot and probably would be docked points on a competition for this reason.
19.06.2013 20:02
There is actually a fairly nice way to explicitly construct a partition based on looking at shapes in a $3 \times 3$ grid, but it doesn't generalize easily, unlike the probabilistic / double-counting solutions.
19.06.2013 23:32
19.06.2013 23:53
Here's how I thought about it before I dropped out. I knew that two of the three numbers, at best, had to be greater than the average. That's really all I got. I had no idea how to proceed.
20.06.2013 04:27
darn I had it, but I thought the solution was too simple so I must have gotten it wrong and didn't bother to turn it in. Anyway, here's what I did (it's probably unnecessarily complicated).
20.06.2013 06:24
"obviously" is not that obvious (and in fact one of the main points of the proof). It also suffers from the same mistake in my proof (prove that each triple indeed appears $\binom{6}{3}$ times). SZRoberson is even more wrong. The answer is 1/3 of the number of triples, not 2/3.
20.06.2013 22:04
My formal solution which I submitted was almost exactly like exmath89's (he worded it better than I did) except that I divided by $3!$ and $10$ at the same time.
07.07.2014 11:43
21.11.2014 20:41
The answer is $28$.To prove that the answer is,just observe there are $84$ triples and if we choose $3$ triplets $ai,aj,ak$ $ah,ag,as$ $ar,at,am$ such that $i,j,k,h,g,s,t,m$ such that all are pairwaise distinct,at least one will we have sum at least $3m$,so from this we easy get the answer is $28$(at least one third of all triples will have the sum at least $3m$ ).An example is easy,just take the biggest number be much larger than the others(for examle,$4$ and $9$ zeroes).
22.11.2014 12:47
I misread the question but realized that what I had misunderstood was probably a question itself Can we maximize the value of $A$ ?
22.11.2014 13:15
Well that is obvious,took all numbers be equal,than you have all triplets,or $84$.
05.04.2017 12:22
It's just Baranyai's theorem: If $k$ divides $n$, the set of all $\binom{n}{k}$ $k-$subsets of an $n-$set may be partitioned into disjoint parallel classes $A_{i}$ for $i=1, 2,\dots , \binom{n-1}{k-1}$.
30.01.2019 06:50
31.01.2019 05:59
bump....
30.08.2020 02:51
Note that because the average value of the values $a_n$ is $m$, you could say that the expected value of $a_n$ is $m$. If you were to take three disjoint triples, note that as the expected value of the sum of each triple is $3m$, you would expect that at least one of the triples has a sum that is greater than or equal to $3m$. From this, we can infer that at least $\frac{1}{3}$ of the possible triples satisfy $a_i+a_j+a_k \geq 3m$, which implies $A \geq 28$ as there are $\binom{9}{3} = 84 = 28 \cdot 3$ triples. A possible construction is if the nine real numbers are $8$ instances of the number $1$ and $1$ instance of the number $2$. Note that in order for a triple to satisfy the condition, it must have the $2$ in it, and there are $\binom{8}{2} = 28$ ways to choose the remaining numbers. So, the minimum possible value for $A$ is $28$.
05.05.2021 20:47
The answer is $28$. A construction is $a_1=a_2=\cdots=a_8=0$ and $a_9=187$, in which case a triple $1 \leq i<j<k\leq 9$ satisfies $a_i+a_j+a_k \geq 3m$ if and only if $k=9$. We can easily check that there are $\binom{8}{2}=28$ such triples. Now I will show that $A$ cannot be smaller. Instead of viewing $i,j,k$ as triples, view them as subsets of $\{1,2,\ldots,9\}$. We can partition all of the possible sets into groups of 3 sets $A,B,C$ such that $A \cap B=\emptyset,B\cap C=\emptyset, C \cap A=\emptyset$: an example is $A=\{1,5,6\},B=\{2,8,9\},C=\{3,4,7\}$. Since $A \cup B \cup C$ is then always $\{1,2,\ldots,9\}$, we require at least one of the sets to result in a sum of at least $3m$, otherwise their combined sum is less than $9m=1+2+\cdots+9$: impossible. Thus we have at least $\frac{1}{3}\binom{9}{3}=28$ triples, as desired. $\blacksquare$
16.07.2021 13:49
Ok so at least one out of every three disjoint triples must have a sum at least $3m$ This gives $A \geq \frac{1}{3}\binom{9}{3}=24$. now we just find a construction.
23.01.2023 20:52
We claim that the answer is 28. We say that a triple is acceptable if its average is greater than or equal to the overall average. For a construction of 28, take $$(10^{100},1,1,1,1,1,1,1,1).$$Clearly, a triple is acceptable if and only if it contains $10^{100}$, so there are 28 acceptable triples. Consider partitioning the 9 numbers into 3 sets of 3. Note that there is at least 1 acceptable set out of these 3 due to Pidgeonhole. Therefore, the expected number of acceptable sets when doing a random partition is at least 1. By Linearity of Expectation, the expected number of acceptable sets when doing a random partition is $$n/28,$$where $n$ is the number of total acceptable triples, since each acceptable triple has a 1/28 chance of appearing in the set. Therefore, $n\geq28$, so we are done.
06.03.2023 06:08
Call a triple fat if it satisfies the desired condition. The answer is $28$ triples. For a construction, just make one of the $a_n$ really big. Note that among any three distinct triples, at least one is fat. Thus, among all $\frac{9!}{(3!)^4}$ partitions of $[9]$ into triples, each triple appears in exactly $\frac 12{6 \choose 3} = 10$ partitions. Thus, to contribute $280$ fat triples among partitions with multiplicity, there must exist at least $28$ triples, as needed.
28.05.2023 21:08
The answer is $28$, achievable by taking $a_1=a_2=\dots=a_8=0$ and $a_9=9$. We will show that we must have $A \ge 28$. Note that there are $\tbinom{9}{3}=84$ possible triples $(i, j, k)$ possible. Choose a permutation $\sigma$ of $(a_1, \dots, a_9)$ randomly. Let $S_i=\{a_{\sigma(3i+1)}, a_{\sigma(3i+2)}, a_{\sigma(3i+3)}\}$ for $i=0, 1, 2$. Let $X$ be the number of $S_0, S_1, S_2$ that have the sum of its elements at least $3m$. Clearly $X \ge 1$, so $\mathbb{E}[X] \ge 1$, and if the probability of a randomly selected triple having sum at least $3m$ is $p$, then $\mathbb{E}[X] = 3p$. Thus $3p \ge 1$, so $p \ge \tfrac{1}{3}$, which means that $A = 84p \ge 84 \cdot \frac{1}{3} = 28$, as needed.
27.11.2023 08:05
Did anyone manage to create 28 triples of disjoint (i, j, k)?
10.03.2024 05:12
06.12.2024 05:28
The answer is $\boxed{28}$, achieved by $a_1=a_2=\dots=a_8=0$ and $a_9=1434$. Among any three disjoint triples, at least one satisfies the condition (else $\sum a_i < 9m$, contradiction). There are $280$ triples of disjoint triples so thus there are at least $280$ triples satisfying the condiiton. But every triple is counted in $\frac12 \binom63 = 10$ sets, so we have at least $28$ triples, as desired.
09.01.2025 13:33
The answer is 28, achieved by taking $(a_1,a_2,\dots ,a_8,a_9)=(0,0,\dots ,0,1)$. To see the bound, notice that amongst any 3 disjoint triples, atleast one of them satisfies the desired property. Its not so hard to see that there are $280$ disjoint triples so there are atleast 280 triples satisfying the given condition counted with multiplicity, and since each triple is counted $10$ times, we get that there are atleast $28$ triples as desired.