Maths Olympiad Prep

Library / /22 of 24

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Netherlands

A set consisting of at least two distinct positive integers is called *centenary* if its greatest element is 100100. We will consider the average of all numbers in a centenary set, which we will call the average of the set. For example, the average of the centenary set {1,2,20,100}\{1, 2, 20, 100\} is 1234\frac{123}{4} and the average of the centenary set {74,90,100}\{74, 90, 100\} is 8888.
Determine all integers that can occur as the average of a centenary set.

Solution

If you decrease one of the numbers (unequal to 100100) in a centenary set, the average becomes smaller. Also if you add a number that is smaller than the current average, the average becomes smaller. To find the centenary set with the smallest possible average, we can start with 1,1001, 100 and keep adjoining numbers that are as small as possible, until the next number that we would add is greater than the current average. In this way, we find the set with the numbers 11 to 1313 and 100100 with average 114(1+2++13+100)=19114=13914\frac{1}{14} \cdot (1+2+\dots+13+100) = \frac{191}{14} = 13\frac{9}{14}. Adding 1414 would increase the average, and removing 1313 (or more numbers) would increase the average as well. We conclude that the average of a centenary set must be at least 1414 when it is required to be an integer.
Therefore, the smallest integer which could be the average of a centenary set is 1414, which could for example be realised using the following centenary set:
{1,2,3,4,5,6,7,8,9,10,11,12,18,100}. \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 18, 100\}.
Now we still have to show that all integers greater than 1414 (and smaller than 100100) can indeed be the average of a centenary set. We start with the centenary set above with average 1414. Each time you add 1414 to one of the numbers in this centenary set, the average increases by 11. Apply this addition from right to left, first adding 1414 to 1818 (the average becoming 1515), then adding 1414 to 1212 (the average becoming 1616), then adding 1414 to 1111, etcetera. Then you end up with the centenary set:
{15,16,17,18,19,20,21,22,23,24,25,26,32,100} \{15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 32, 100\}
with average 2727, and you realised all values from 1414 to 2727 as an average. Because we started adding 1414 to the second largest number in the set, this sequence of numbers remains increasing during the whole process, and therefore consists of 1414 distinct numbers the whole time, and hence the numbers indeed form a centenary set.
We can continue this process by first adding 1414 to 3232, then 1414 to 2626 etcetera, and then we get a centenary set whose average is 4040. Repeating this one more time, we finally end up with the set:
{43,44,45,46,47,48,49,50,51,52,53,54,60,100} \{43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 60, 100\}
with average 5353. Moreover, we can obtain 5454 as the average of the centenary set {8,100}\{8, 100\}, 5555 as the average of {10,100}\{10, 100\}, and so on until 9999, which we obtain as the average of {98,100}\{98, 100\}. This shows that all values from 1414 to 9999 can be obtained. \square

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.