Maths Olympiad Prep

Library / /19 of 24

, 2016

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Argentina

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.

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 xnx_n the number of markers in a certain box before step nn, n=1,2,n = 1, 2, \dots. Suppose that xn=nx_n = n for some nn. Then by the rule of adding markers we have xn+1=n+1x_{n+1} = n+1, xn+2=n+2x_{n+2} = n+2 etc.; in other words the number of markers in that box equals the number of the oncoming step ll for each lnl \ge n. 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 nn such that xn=nx_n = n.

We use the following observation. Let a box C satisfy xi>lx_i > l for some ll, that is, the difference di=xild_i = x_i - l is positive. Then there is an mlm \ge l such that C receives no marker at step mm. Otherwise

xix_i increases by 1 at every step mlm \ge l, which means that xi+sx_i + s is divisible by l+sl+s for all s0s \ge 0.

However this is impossible as 1<xi+sl+s<21 < \frac{x_i + s}{l+s} < 2 for ss sufficiently large; it is enough to take s>xi2ls > x_i - 2l.

Let mlm \ge l be the first step that adds no marker to C. Then the observation implies that the difference dm+1=xm+1(m+1)=xm(m+1)d_{m+1} = x_{m+1} - (m+1) = x_m - (m+1) satisfies dm+1=dl1d_{m+1} = d_l - 1. If dm+1>0d_{m+1} > 0 then by the same reason there is a step k>mk > m with dk=dm1d_k = d_m - 1. Repeated applications of the same argument show that after finitely many steps there will be a step ss such that ds=0d_s = 0, that is, xs=sx_s = s.

Initially, before step 1, one has x11x_1 \ge 1 for each box C. This is ensured by the condition that every box contains a marker. If x1=1x_1 = 1 then xn=nx_n = n holds for C already with n=1n=1. Otherwise xi>1x_i > 1, so by the above xn=nx_n = n 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.

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.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.