Browse · MathNet
PrintArgentine National Olympiad
Argentina counting and probability
Problem
Given 100 infinitely large boxes with markers in them, the following procedure is carried out. At step 1 one adds one marker in every box. At step 2 one marker is added in every box containing an even number of markers. At step 3 one marker is added in every box in which the number of markers is divisible by 3, and so on.
Before the process starts Bruno wants to distribute several markers in the boxes so that there is at least one marker in each box and the following holds: After any number of steps there exist two boxes containing different number of markers. Decide if this is possible to achieve.
Before the process starts Bruno wants to distribute several markers in the boxes so that there is at least one marker in each box and the following holds: After any number of steps there exist two boxes containing different number of markers. Decide if this is possible to achieve.
Solution
The answer is no. Regardless of the initial distribution all boxes will contain the same number of markers after finitely many steps. Moreover this is true for any number of boxes.
Denote by the number of markers in a certain box before step , . Suppose that for some . Then by the rule of adding markers we have , etc.; in other words the number of markers in that box equals the number of the oncoming step for each . So, in order to prove that eventually all boxes contain the same number of markers, it is enough to show that for each box there exist a step such that .
We use the following observation. Let a box satisfy for some , that is, the difference is positive. Then there is an such that receives no marker at step . Otherwise
increases by 1 at every step , which means that is divisible by for all .
However this is impossible as for sufficiently large; it is enough to take .
Let be the first step that adds no marker to . Then the observation implies that the difference . If then by the same reason there is a step with . Repeated applications of the same argument show that after finitely many steps there will be a step such that , that is, .
Initially, before step 1, one has for each box . This is ensured by the condition that every box contains a marker. If then holds for already with . Otherwise , so by the above will result after finitely many steps. As explained in the beginning, when this happens for all boxes, the numbers of markers in them will be the same.
Denote by the number of markers in a certain box before step , . Suppose that for some . Then by the rule of adding markers we have , etc.; in other words the number of markers in that box equals the number of the oncoming step for each . So, in order to prove that eventually all boxes contain the same number of markers, it is enough to show that for each box there exist a step such that .
We use the following observation. Let a box satisfy for some , that is, the difference is positive. Then there is an such that receives no marker at step . Otherwise
increases by 1 at every step , which means that is divisible by for all .
However this is impossible as for sufficiently large; it is enough to take .
Let be the first step that adds no marker to . Then the observation implies that the difference . If then by the same reason there is a step with . Repeated applications of the same argument show that after finitely many steps there will be a step such that , that is, .
Initially, before step 1, one has for each box . This is ensured by the condition that every box contains a marker. If then holds for already with . Otherwise , so by the above will result after finitely many steps. As explained in the beginning, when this happens for all boxes, the numbers of markers in them will be the same.
Final answer
no
Techniques
Invariants / monovariantsDivisibility / Factorization