A local supermarket is responsible for the distribution of supply boxes. Each box is ought to contain kilograms of rice and eggs. It is known that a total of kilograms of rice and eggs are in these boxes, but in some of them the amount of either item is more or less than the amount required. In each step, supermarket workers can choose two arbitrary boxes and transfer any amount of rice or any number of eggs between them. At least how many steps are required so that, starting from any arbitrary initial condition, after these steps the amount of rice and the number of eggs in all these boxes is equal?
Solution
The answer is . First consider the initial condition that all of eggs are in just one of boxes. In each step, we can transfer eggs to at most one new box and so we need at least steps. We claim that steps is always enough. For this end, we call a box containing exactly eggs and kilograms of rice a good box, and a box which is not good a bad box! In each step, consider one of bad boxes containing the most number of eggs and one of bad boxes containing the most amount of rice. If these two boxes were the same, consider another arbitrary bad box (note that if all other boxes were good, this box also must be good and there is nothing to prove). Evidently, we have at least number of eggs and kilograms of rice in these two boxes. So by transferring eggs and rice between them, we can make one of them a good box. Therefore, after steps we have at least good boxes and so the last box is also good and we are done.
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.