Maths Olympiad Prep

Library / /12 of 15

Combinatorics Difficulty 6.7 National Olympiad Prove it Argentina

The following operation is allowed on several given nonnegative integers. A positive number aa is chosen among them, and each number bab \ge a is replaced by bab-a, including the choice aa itself. Starting with 1,2,,20131, 2, \ldots, 2013, after several operations numbers with sum 1010 are obtained. What can these numbers be? Find all possibilities

Solution

Call the set Sk={1,2,,k}S_k = \{1, 2, \dots, k\} a block, for k=1,2,k=1, 2, \dots; for consistency assume that S0S_0 is the empty block. Suppose that several numbers can be partitioned into blocks. The key observation is that the same holds true after any operation is applied. Indeed let SkS_k be one of the blocks, and let f(a)f(a) denote the operation applied to number aa. If a>ka > k then SkS_k remains unchanged. If aka \le k then SkS_k is replaced by the blocks Sa1S_{a-1} and SkaS_{k-a}. The claim is justified.

Since the initial numbers 1,2,,20131, 2, \ldots, 2013 form a block, it follows that one has a disjoint union of blocks after any number of operations. The sum of the block SkS_k is 12k(k+1)\frac{1}{2}k(k+1), so if the total sum is 1010 then the blocks participating can be only S1={1}S_1 = \{1\}, S2={1,2}S_2 = \{1, 2\}, S3={1,2,3}S_3 = \{1, 2, 3\}, S4={1,2,3,4}S_4 = \{1, 2, 3, 4\}, with sums 1,3,6,101, 3, 6, 10 respectively. So the question reduces to representing 1010 as a sum of several numbers among 1,3,6,101, 3, 6, 10. The possibilities are

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 reproduced verbatim; metadata (topic, difficulty) added by this project.