Skip to main content
OlympiadHQ

Browse · MathNet

Print

50th Mathematical Olympiad in Ukraine, Fourth Round (March 24, 2010)

Ukraine 2010 counting and probability

Problem

Find the least possible natural number , such that each number from the set can be expressed as a digit or as a sum of consecutive digits of .
Solution
It is obvious, that we can not find number with given property and three digits. Suppose, that it has 4 digits: , then we can construct 10 different sums of consecutive digits, more precisely: , , , , , , , , , . To satisfy the conditions of the problem these 10 sums have to be distinct. Hence, all digits have to be distinct either, and their sum equals 10. We have only one option: 1, 2, 3, 4. But, in order to get 9 as a sum, 1 should be the last or the first digit of our number. In the same way, to represent 8 as a sum of consecutive digits, 2 should be the first or the last digit. Therefore, we have 4 options: 1342, 1432, 2341, 2431. However, for first and fourth numbers we can not get 5 as a sum of consecutive digits, for second and third - 6.

Hence, the least possible number of digits is at least 5. Our number can not start with 1111, because, in order to get 10 as a sum, we have the following options: 11116, 11117, 11118, 11119, but we can not express 5 then. Following the same lines, if our number starts with 1112, then we have the following options - 11125, 11126, 11127, 11128, 11129. But we can not express 5 (except second number) and 6 for second number. Therefore, our minimal number starts with 1113 at least. Numbers 11131, 11132, 11133 do not give us 10 as a sum, and 11134 meets all the requirements.
Final answer
11134

Techniques

Pigeonhole principleColoring schemes, extremal arguments