A basket is called "Stuff Basket" if it includes $10$ kilograms of rice and $30$ number of eggs. A market is to distribute $100$ Stuff Baskets. We know that there is totally $1000$ kilograms of rice and $3000$ number of eggs in the baskets, but some of market's baskets include either more or less amount of rice or eggs. In each step, market workers can select two baskets and move an arbitrary amount of rice or eggs between selected baskets. Starting from an arbitrary situation, what's the minimum number of steps that workers provide $100$ Stuff Baskets?
Problem
Source: Iran National Olympiad - 2014 Second Round - D1P1
Tags: combinatorics unsolved, combinatorics
08.05.2014 19:31
It is very easy! suppose $ a_i : $ the value of rice in basket $ i $ $ b_i : $ the number of eggs in basket $ j $ now we prove that there are two baskets $ i,j $ such that $ a_i+a_j > 10 , b_i+b_j>30 $ $ ( $ $ * $ $ ) $ suppose that $ \forall 1 \le i \le 100 : b_m \ge b_i $ if $ b_m < 30 $ then $ b_1+b_2+...+b_100 < 100b_m \Rightarrow 30000<100b_m<30000 $ and it is impossible. so $ b_m \ge 30 $ thus $ \forall 1 \le i \le 100 , i \neq m : b_i+b_m \ge 30+b_i>30 $ if $ a_m \ge 10 $ then $ ( $ $ * $ $ ) $ is true. otherwise suppose $ a_m<10 $ now we prove there is a basket $ j $ such that $ a_m+a_j>10 $ suppose this is false. so $ \forall i \neq m : a_i+a_m \le 10 $ $ a_1+a_m \le 10 $ $ a_2+a_m \le 10 $ $ ... $ $ a_{m-1}+a_m \le 10 $ $ a_{m+1}+a_m \le 10 $ $ ... $ $ a_100+a_m \le 10 $ so $ (a_1+a_2+...+a_{m-1})+(a_{m+1}+a_{m+2}+...+a_100 ) + 99 a_m \le 9900 $ but $ a_m < 10 $ so $ (a_1+a_2+...+a_100)+99a_m < 9900+10 =10000 $ thus $ 10000+99a_m<10000 $ and it is impposible. so there is a basket $ j $ such that $ a_m+a_j > 10 $ but we know $ b_m+b_j >30 $ with this we can simply prove in one step we can make a basket with $ 30 $ eggs and $ 10kg $ rice. continue this way with other baskets. the answer is $ 99 .$ but don't forget you must in an example prove that you need at least $ 99 $ steps! it is easy to find this example ( how?! ) so it's done