Maths Olympiad Prep

Library / /2 of 3

Combinatorics Difficulty 5.2 AIME, harder Prove it Czech Republic

Suppose we have a 9-digit number NN in which all the digits are distinct and non-zero. Then we consider all the sums of adjacent triples of digits of NN and order them in a non-decreasing sequence. For the following sequences, determine whether there exists an NN for which we get them as a result:
a) 11,15,16,18,19,21,22,11, 15, 16, 18, 19, 21, 22,
b) 11,15,16,18,19,21,23.11, 15, 16, 18, 19, 21, 23.

Solution

a) Yes, the number N=137658942N = 137658942 works, since the sums of consecutive triples are (left to right) 11, 16, 18, 19, 22, 21, 15.

b) We shall prove that no such number exists by showing that for any NN, the sum of the 7 numbers is at most 122, while the numbers given to us have sum 123. Denote the ii-th digit of NN by aia_i and let SS be the sum of the resulting 7 sums. Then we have:
S=(a1+a2+a3)+(a2+a3+a4)+(a3+a4+a5)+(a4+a5+a6)+(a5+a6+a7)+(a6+a7+a8)+(a7+a8+a9)=3(a2+a3+a4+a5+a6+a7+a8)+a1+a9 \begin{aligned} S &= (a_1 + a_2 + a_3) + (a_2 + a_3 + a_4) + (a_3 + a_4 + a_5) + (a_4 + a_5 + a_6) + (a_5 + a_6 + a_7) + (a_6 + a_7 + a_8) + (a_7 + a_8 + a_9) \\ &= 3(a_2 + a_3 + a_4 + a_5 + a_6 + a_7 + a_8) + a_1 + a_9 \end{aligned}
Since all digits are distinct and non-zero, a1,,a9a_1, \ldots, a_9 is a permutation of 1,2,,91,2,\ldots,9, so their sum is 4545. Thus,
S=3(a2+a3+a4+a5+a6+a7+a8)+a1+a9=3(45a1a9)+a1+a9=1352a12a9 S = 3(a_2 + a_3 + a_4 + a_5 + a_6 + a_7 + a_8) + a_1 + a_9 = 3(45 - a_1 - a_9) + a_1 + a_9 = 135 - 2a_1 - 2a_9
The minimum possible value of a1+a9a_1 + a_9 is 1+2=31 + 2 = 3, so the maximum possible SS is 1352×3=129135 - 2 \times 3 = 129. The maximum a1+a9a_1 + a_9 is 8+9=178 + 9 = 17, so the minimum SS is 1352×17=101135 - 2 \times 17 = 101.

But more precisely, since the sequence 11,15,16,18,19,21,2311, 15, 16, 18, 19, 21, 23 sums to 123123, which is not possible as SS can be at most 122122 (as shown in the original solution), there is no such NN.

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.