A loader has two carts. One of them can carry up to 8 kg, and another can carry up to 9 kg. A finite number of sacks with sand lie in a storehouse. It is known that their total weight is more than 17 kg, while each sack weighs not more than 1 kg. What maximum weight of sand can the loader carry on his two carts, regardless of particular weights of sacks? Author: M.Ivanov, D.Rostovsky, V.Frank
Problem
Source: Tuymaada 2008, Senior League, Second Day, Problem 7.
Tags: algebra unsolved, algebra
mszew
22.07.2008 15:32
Is it $ \frac{9}{10} \cdot 17$ ? with equal weights of $ \frac{9}{10}+\epsilon$
goc
23.07.2008 22:46
i think i have an ugly working solution and it is $ 17\cdot 0.9=15.3$ first the example mszew gave shows that we can give the loader such weights that he can't guarantee more. now notice that if we give him a weight $ x$ such that $ x\leq 0.85$ then he can obtain $ 15.3$ just fill the carts without using $ x$. if we have no more weights (except $ x$) then we have more that $ 17-0.85=16.15$ which is enough. if we simply can't put any more weights(except $ x$) then the sum is atleast $ 15$. if we can put $ x$ we are done, and if we can't then the carts must weigh atleast $ 7.15$ and $ 8.15$ atleast respectively so in total over $ 15.3$ so there is no weight $ \leq 0.85$. now we count the weights in the sections $ <0.85,0.9], <0.9,0.95>, [0.95,1]$ if there are at least $ 10$ weights in the first segment then we take them and put them on the bigger cart their weight is between $ 8.5$ and $ 9$ so they fit in the cart and since we can certainly fill the other carts weight over $ 7$ we are done. so there are at most $ 9$ weights in the first segment. the minimum nuber of weights is $ 18$ so there are at least $ 9$ segments in the interval $ <0.9,1]$. if there are two greater than $ 0.95$ then take those two and six from $ <0.9,0.95>$ and put it on the smaller cart it fits and weighs atleast $ 6.3$ which is again enough. so atmost 1 over $ 0.95$ and atleast $ 8$ in $ <0.9,0.95>$ if now there exists atleast one weight smaller than $ 0.9$ put it aside take the $ 8$ weights from $ <0.9,0.95>$ and put it on the small cart. minimum weight $ 7.2$ now fill the big carts weight arbitrarily over $ 8$.if it's greater than $ 8.1$ we're done otherwise add the weight we put aside (the weight smaller than $ 0.9$) and then we ARE done so now we know there are no weights smaller than or equal to $ 0.9$. since the loader can surely put at least $ 8$ weights on the small and $ 9$ on the big cart whose total weight is atleast $ (8+9)\cdot 0.9=15.3$ we are done... blaaaah to long