Skip to main content
OlympiadHQ

Browse · MathNet

Print

31st Junior Turkish Mathematical Olympiad

Turkey counting and probability

Problem

There are empty red boxes numbered and empty white boxes numbered on the table. At each step we choose one red and one white box and put one ball into each chosen box. After finite number of steps it turns out that for any two identically numbered red and white boxes either the red box contains more balls than the white box or the white box contains more balls than the red box. Find all possible values of .
Solution
Answer: , where is a positive integer.

Suppose that in identically numbered pairs of red and white boxes each red box contains more balls than the white box. Then the difference between the total number of balls in red boxes and the total number of balls in white boxes is . On the other hand, since the total number of balls in red boxes and the total number of balls in white boxes increases by at each step, the difference should be equal to . Therefore, . Thus, should be a multiple of .

Firstly, we give an example for . Let each pair of red box numbered and white box numbered , and be chosen exactly two times. Then after these steps the problem conditions will be satisfied.

If , we partition boxes into groups numbered where group number contains red and white boxes numbered , change box numbers to their values in and apply steps defined above to each of these groups.
Final answer
n = 11k for positive integer k

Techniques

Invariants / monovariantsGreatest common divisors (gcd)