8.8, 9.8, 11.8 a) 99 boxes contain apples and oranges. Prove that we can choose 50 boxes in such a way that they contain at least half of all apples and half of all oranges. b) 100 boxes contain apples and oranges. Prove that we can choose 34 boxes in such a way that they contain at least a third of all apples and a third of all oranges. c) 100 boxes contain apples, oranges and bananas. Prove that we can choose 51 boxes in such a way that they contain at least half of all apples, and half of all oranges and half of all bananas. (I. Bogdanov, G. Chelnokov, E. Kulikov)
Problem
Source: All-Russian MO Round 4, 2005
Tags: vector, email, induction, inequalities, combinatorics proposed, combinatorics
Severius
04.04.2005 22:49
Very nice problems. For a): Order the boxes according to the number of apples they contain ($b_{99}$ has the most apples and $b_1$ has the fewest). Then take: $b_{99}$, one of $b_{98}, b_{97}$, ..., one of $b_2, b_1$. It is clear that any such set contains at least half of all apples (in the worst case you have chosen $b_{99}, b_{97}, ..., b_1$ which has at least as many apples as $b_{98}, ..., b_2$). Now from each subset of 2 boxes (98-97, ..., 2-1) take the box with more oranges. Then the set also contains at least half of the oranges. For b): Order the boxes according to the number of apples they contain ($b_{100}$ has the most apples and $b_1$ has the fewest). Then take: $b_{100}$, one of $b_{99}, b_{98}, b_{97}$, ..., one of $b_3, b_2, b_1$. Now in the worst case we have chosen $b_{100}, b_{97}, ..., b_1$ which has at least as many apples as $b_{99}, b_{96}, ..., b_3$ and $b_{98}, b_{95}, ..., b_2$. So any such set contains at least a third of the apples. Now from each set of 3 boxes (99-98-97, ..., 3-2-1) take the box with the most oranges. This set satisfies the conditions.
Pascual2005
05.04.2005 01:23
well i have some ideas for this kind of problems but i cant finish them.... For every box $i$, identify the vector $v_i=(x,y,z)$ where $x$ is the number of apples on it, $y$ the number of oranges and $z$ the number of the other fruit on box $i$. the geometric interpretation is clear now....
Myth
09.04.2005 19:17
Very nice, Severius!
Amir.S
17.04.2005 20:40
and what about c) ?
Fedor Petrov
24.04.2005 08:17
c is very hard. There are many solutions, but none of our students managed to solve it. A hint: prove a lemma: if we have $2k$ boxes, we may partition them to two groups by $k$ boxes in such a way that weight of apples in both groups differ by at most the maximal weight of apples in a single box, and the same for oranges.
georgew_bush
11.09.2005 02:36
OH,MY ROOMMATE AND I CAN ONLY SOLVE THE FIRST TWO PROBLEM,THE SOLUTION IS SIMILAR TO YOURS I think the third problem is really hard for me.And I guess it must have a excelllent solution with a giant use of some lemma.Could anyone post the solution or email me:georgew_bush@163.com?THANKS!
silouan
15.12.2005 21:16
Does anyone has the official solution of this beautiful problem ?I think some people from Russia sure. So please post it Thank you very much
indybar
04.01.2006 10:13
Fedor Petrov wrote: c is very hard. There are many solutions, but none of our students managed to solve it. A hint: prove a lemma: if we have $2k$ boxes, we may partition them to two groups by $k$ boxes in such a way that weight of apples in both groups differ by at most the maximal weight of apples in a single box, and the same for oranges. How? I don't understand
BaBaK Ghalebi
05.01.2006 08:38
amir2 wrote: and what about c) ? prove it with induction
indybar
05.01.2006 10:55
BaBaK Ghalebi wrote: amir2 wrote: and what about c) ? prove it with induction Can you show?
BaBaK Ghalebi
05.01.2006 11:05
indybar wrote: BaBaK Ghalebi wrote: amir2 wrote: and what about c) ? prove it with induction Can you show? sure ASAP
indybar
06.01.2006 14:27
BaBaK Ghalebi wrote: sure ASAP hmm... I don't think induction works here.
BaBaK Ghalebi
06.01.2006 15:04
BaBaK Ghalebi wrote: amir2 wrote: and what about c) ? prove it with induction $2k-1$ box $\& k$ $n=k\to n=k+1$ if there were two boxes such that $a_1>a_2,b_1>b_2$ now by the assumption of the induction we ca n choose $k$ boxes from the $2k-1$ boxes left now we can add the box that contains $a_1,b_1$ now if there werent such boxes then we have: $a_1\geq a_2\geq ...\geq a{}_2{}_k_+_1$ $b_1\leq b_2\leq ...\leq b{}_2{}_k_+_1$ now we choose the boxes $1,3,5,...,2n+1$ $\Rightarrow$ $a_1+a_3+...+a{}_2{}_n_+_1\geq a_2+a_4+...+a{}_2{}_n$ sorry if I didnt explain it clearly did you get it or should I explain it better and more carefully??
ThAzN1
06.01.2006 22:48
I have no idea what you're trying to say. What are the $a_i,b_i$ (I'm assuming they're the weights of apples, oranges resp. in the boxes) Then what about the bananas? Please "explain it better and more carefully"
Erken
06.01.2009 13:51
c) part: Lemma by Fedor Petrov: Any $ 2k$ pairs of positive reals $ (a_i,b_i)$ can be partitioned into $ 2$ groups of $ k$ pairs each, so that if $ x$ is a sum of $ a_i$ in the first group and $ y$ is a sum of $ a_i$ in the second group. Then $ |x - y|\leq\max_{i}a_i$. And the same inequality holds for the $ b_i$, i.e if $ m$ is a sum of $ b_i$ in the first group and $ n$ is a sum of $ b_i$ in the second group, then $ |m - n|\leq \max_i b_i$. Proof of the lemma: The statement clearly holds for the case $ k = 1,2$. So assume that the statement holds for $ k = n$ and let's prove it for $ k = n + 1$. WLOG assume that $ a_{2n + 2}\geq a_{2n + 1}\geq \max_{i = 1}^{2n}a_i$. Due to the induction assumptation used for the case $ 2n$ the following inequality must hold: $ |x - y|\leq a_{2n + 1}$. Consider two cases: 1.$ b_{2n + 2}\geq b_{2n + 1}$ WLOG suppose $ m\geq n$. Then add the pair $ (a_{2n + 1},b_{2n + 1})$ to the first group, and $ (a_{2n + 2},b_{2n + 2})$ to the second, so ${ |x + a_{2n + 1} - y - a_{2n + 2}}|\leq |x - y| + |a_{2n + 1} - a_{2n + 2}|\leq a_{2n + 1} + a_{2n + 2} - a_{2n + 1} = a_{2n + 2}$ Now suppose that $ m + b_{2n + 1}\geq n + b_{2n + 2}$, then $ |m + b_{2n + 1} - n - b_{2n + 2}| = m + b_{2n + 1} - n - b_{2n + 2}\leq\max_{i}^{2n + 2}b_i$, if $ m + b_{2n + 1}\leq n + b_{2n + 2}$ then: $ |m + b_{2n + 1} - n - b_{2n + 2}| = n + b_{2n + 2} - b_{2n + 1} - m\leq b_{2n + 2} - b_{2n + 1}\leq\max_{i}^{2n + 2}b_i$. For the case $ b_{2n + 1} > b_{2n + 2}$ do the reverse addition, the rest is completely the same as in the considered case. So the lemma is proved. $ \blacksquare$ The last step is pretty obvious, take two boxes, one with max number of apples weight and second with max number of oranges weights. So applying the lemma for $ 98$ ,for $ a_i$ take weights of apples and for $ b_i$ weights of oranges, and choose a group with bigger weight of bananas in it. And add both those boxes into this group.
Plops
01.01.2020 00:37
I have a question: for part c, we were able to deal with apples, oranges, and bananas, but is there a way we can generalize this problem so that we can deal with, say, $n$ fruits instead of just $3$? Sorry if the question is vague (and for the massive bump), but I am super curious about this.
OronSH
14.04.2023 01:01
Here is what I believe is a different solution to part (c):
First, select the box with the most apples and the box with the most bananas. (In the case these are the same box, select the box and another arbitrary box.) For the other $98$ boxes, let $a_{n+1}$ be the box with the $n$th most apples, and let $b_{n+1}$ be the box with the $n$th most bananas. We can turn any group of boxes among the $98$ boxes into a $98$-term sequence with the following rule: Write out $a_2,a_3,...,a_{99},$ and replace each $a_k$ with a $1$ if the box is selected, and a $-1$ if the box is not selected. Call this an apple sequence; proceed similarly with $b_k$ for a banana sequence.
Now, for any such sequence, define $S_k$ as the sum of the first $k$ terms. We will prove the following lemma:
If an apple/banana sequence of $n$ terms has $S_k$ nonnegative for all $k$ with $0 \leq k \leq n,$ then it must contain at least half of the apples/bananas.
Proof: We claim that in such a sequence, each $1$ can be paired up with a $-1$ later in the sequence. This implies that the sequence contains at least half of the fruits, since in each pair, the selected box contains more of the chosen fruit than the unselected box, meaning that in each pair, at least half of the fruits are selected, so overall at least half are selected.
To prove this, we show that by pairing each $1$ with the first unpaired $-1,$ we will have a desired sequence. Suppose there is some $1$ that ends up paired to an earlier $-1.$ Let it be the $k$th $1$ and the $n$th term of the sequence. Then it must also be the $k$th $-1.$ However, consider $S_{n-1}.$ This contains $k-1$ $1$s, but contains at least $k$ $-1$s, so it is negative, which is a contradiction. Therefore the lemma is proved.
Now consider all apple sequences that have the property such that for any positive integer $k$ from $1$ to $49,$ exactly one of $a_{2k},a_{2k+1}$ is a $1.$ We easily see that all of these sequences have $S_i=-1,0,1,$ since $S_{2i}=0$ for all positive integers $i$ and $S_{2i+1}$ can only be 1 away from $S_{2i}.$ Call these apple sequences good, and similarly define a good banana sequence in the same way.
We will now prove that there is some good apple sequence that can be paired with some good banana sequence. We use the following process to generate one: First, set the first unset $a_i$ to $1,$ and set the corresponding $b_j$ to $1.$ Next, set $b_{j+1}$ to $-1$ if $j$ is even, and set $b_{j-1}$ to $-1$ if $j$ is odd. Then set the corresponding $a_k$ to $-1,$ and similarly set $a_{k+1}$ or $a_{k-1}$ to $1$ when $k$ is even or odd, respectively. Repeat this until it fills in $a_{i+1},$ at which point we repeat the whole process for the next unset $a_i,$ and repeat until all terms are filled in.
Now we show that this process works. First, notice that the steps of going between corresponding terms in the different sequences and going between terms in pairs $a_{2k},a_{2k+1}$ and $b_{2k},b_{2k+1}$ are reversible. This means that following this process, we must eventually return to $a_i,$ and the preceding step must have been at $a_{i+1}.$ Also, notice that if some term was filled out at some point, then the other term in its pair must have also been filled out, either immediately before or immediately after, and note that each "loop" fills in the same number of terms in each sequence. Therefore, this algorithm generates a corresponding good apple sequence and good banana sequence, so a pair must exist.
Now consider the $99$-term sequence consisting of $a_1$ replaced by $1$ followed by a good apple sequence. Since for the good apple sequence, $S_k$ is always $-1,0,1,$ in our new sequence $S_k$ must always be $0,1,2,$ since the first $n+1$ terms of this sequence are $1$ followed by the first $n$ terms of the good apple sequence. Since $0,1,2$ are positive, this sequence contains at least half of the apples, and this means our $99$ term sequence contains $49+1=50$ boxes chosen that have at least half of the apples, since half of the terms in the $98$ term sequence are $1$s. Adding back the $b_1$ box, which is chosen, we get our $100$ boxes have a $51$ element subset with at least half of the apples. Similar logic shows that the same subset has at least half of the bananas, since the two good sequences are the same subset.
Now, consider the $98$-term apple and banana sequences that have a $1$ in a given place if and only if there are $-1$s in the same places in our already chosen good sequences. It is not hard to see that these are also good sequences, so $S_k$ also must be $-1,0,1.$ Now putting these sequences together with $a_1$ and $b_1$ gives us another $51$ element subset with at least half of the apples and bananas.
Now suppose neither of these two subsets contains at least half of the oranges. Consider the $49$-element subset that contains a box if and only if our first $51$-element subset doesn't contain it, and consider the corresponding $49$-element subset for our second $51$-element subset. Both of these must contain more than half of the oranges, but notice that they are defined such that their intersection is the null set. Therefore their union is just the $98$ boxes excluding $a_1,b_1.$ However, they contain more than the whole of the oranges in the $100$ boxes, which is a contradiction.
Therefore, there is some set of $51$ boxes containing at least half of each fruit.
bever209
08.08.2023 23:52
Place the boxes in 3d space so that no four are coplanar. By the ham sandwich theorem, there is a plane which bisects the apples (treated as a single object) and does the same for the oranges and bananas. Choose the side of the plane with the least number of boxes. The worst case is when 3 boxes intersect the plane and there are 48 on one of the sides and 49 on the other. Thus you select at most 51 boxes. You have at least half of each type of fruit in this collection of boxes.
Oksutok
15.11.2024 14:48
https://turgor.ru/lktg/2005/4/razbeng.ps