Olympiad Maths Prep

Library / /33 of 55

Combinatorics Difficulty 6.0 National olympiad Prove it Ukraine

Number 10001000 was split into 99 (not necessarily different) positive integer additive terms. After that, we list all different numbers that can be obtained from adding some of these terms (from one to eight). What is the minimum number of numbers listed?

Solution

Let us split 10001000 into 88 numbers 100100 and one number 200200. In this case, the sum of some terms can have 99 different values: 1001100 \cdot 1, 1002100 \cdot 2, \ldots, 1008100 \cdot 8, and 200+1007=900200 + 100 \cdot 7 = 900.

Let us prove that it is impossible to obtain less than 99 different numbers. Since 99 does not divide 10001000, a split of 10001000 results in at least 22 different terms. Let us sort the terms in ascending order. For the list, we first pick only the 11st term, then 11st and 22nd, then 11st, 22nd and 33rd, and so on, until we pick the first 88 numbers – in this way, we get 88 different numbers. Now we take the last 88 terms: this new sum is larger than any previous sum, therefore, there cannot be fewer than 99 different numbers listed.

Looking for a route rather than 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.