Skip to main content
OlympiadHQ

Browse · MathNet

Print

China 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.
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.

Techniques

Invariants / monovariantsGames / greedy algorithms