Olympiad Maths Prep

Library / /5 of 11

, 2010

Combinatorics Difficulty 5.9 AIME, harder Prove it Ukraine

Find the least possible natural number nn, such that each number from the set 1,2,,101, 2, \dots, 10 can be expressed as a digit or as a sum of consecutive digits of nn.

Solution

It is obvious, that we can not find number with given property and three digits. Suppose, that it has 4 digits: abcda b c d, then we can construct 10 different sums of consecutive digits, more precisely: aa, bb, cc, dd, a+ba+b, b+cb+c, c+dc+d, a+b+ca+b+c, b+c+db+c+d, a+b+c+da+b+c+d. 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.

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.