Browse · MathNet
PrintChina Girls' Mathematical Olympiad
China counting and probability
Problem
Suppose small balls have been placed into numbered boxes . Each time we can select a box and do the following operations: (1) If and there is at least one ball in , move one ball from into . (2) If and there is at least one ball in , move one ball from into . (3) If and there are at least two balls in , move one ball from into and one ball into , respectively.
Prove the following: no matter how the balls are distributed among the boxes originally, it is always realizable to let each box contain exactly one ball by finite operations.
Prove the following: no matter how the balls are distributed among the boxes originally, it is always realizable to let each box contain exactly one ball by finite operations.
Solution
For any two vectors and , if there exists such that we then denote it as . Let represent the distribution of the balls among the boxes. Then is a non-negative integer vector. The operation defined in the question, if executable, can be expressed as , where , (), . Then for , we always have . So for any initial distribution of the balls, after a finite number of operations on every () that contains at least two balls, we can arrive at a ball distribution satisfying for all . If at this time , the problem is solved; otherwise, we have .
Assuming is the smallest number such that , we can then do a series of operations on : to get . Repeating the operations above, we can finally arrive at the ball distribution vector that meets the requirement.
Assuming is the smallest number such that , we can then do a series of operations on : to get . Repeating the operations above, we can finally arrive at the ball distribution vector that meets the requirement.
Techniques
Invariants / monovariantsGames / greedy algorithms