Maths Olympiad Prep

Library / /7 of 11

Algebra Difficulty 6.2 National olympiad Prove it Argentina

1000 balls of mass 0.380.38 and 5000 balls of mass 0.0380.038 must be packed in boxes. A box can contain any collection of balls with total mass at most 11. Find the minimum number of boxes needed.

Solution

There can be 00, 11 or 22 balls of mass 0.380.38 in a box since 30.38>13 \cdot 0.38 > 1. In these three cases the box can contain at most 10.038=26\lfloor \frac{1}{0.038} \rfloor = 26, 10.380.038=16\lfloor \frac{1-0.38}{0.038} \rfloor = 16 and 120.380.038=6\lfloor \frac{1-2 \cdot 0.38}{0.038} \rfloor = 6 balls with mass 0.0380.038 respectively. If looking for the minimum number of boxes, we may therefore assume that there are only boxes of three kinds: with 00 heavy and 2626 light balls; with 11 heavy and 1616 light balls; with 22 heavy and 66 light balls. Let there be x0x_0, x1x_1 and x2x_2 boxes of each kind respectively. In order that all balls be packed, it is necessary and sufficient that 26x0+16x1+6x2500026x_0 + 16x_1 + 6x_2 \ge 5000 and x1+2x21000x_1 + 2x_2 \ge 1000. Multiply the second inequality by 1010 and add it to the first one. This gives 26(x0+x1+x2)1500026(x_0 + x_1 + x_2) \ge 15000, hence x0+x1+x21500026=576.9...x_0 + x_1 + x_2 \ge \frac{15000}{26} = 576.9.... Because x0+x1+x2x_0 + x_1 + x_2 is an integer, it follows that x0+x1+x2577x_0 + x_1 + x_2 \ge 577. So 577577 boxes are necessary.

Now let x0=0x_0 = 0, x1=154x_1 = 154, x2=423x_2 = 423. Then x0+x1+x2=577x_0 + x_1 + x_2 = 577, x1+2x2=1000x_1 + 2x_2 = 1000 and 26x0+16x1+6x2=5002>500026x_0 + 16x_1 + 6x_2 = 5002 > 5000. These relations show that 577577 boxes are sufficient. The answer is 577577.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.