Maths Olympiad Prep

Library / /3 of 5

Algebra Difficulty 5.1 AIME, harder Prove it Brazil

Find all 10 digit numbers a0a1a9a_0a_1\ldots a_9 such that, for each kk, aka_k is the number of times that the digit kk appears in the number.

Solution

Note that a0+a1++a9a_0 + a_1 + \cdots + a_9 is equal to the sum of number of 0s, 1s, ..., 9s, which is, in turn, equal to total number of digits, 10. In other words, the sum of the digits is 10. In particular, if i>5i > 5, then ai=0a_i = 0 or 1 (because if ai=2a_i = 2, then we have at least 2 digits bigger than 5 with sum bigger than 10).

Suppose all ai5a_i \le 5. Then in particular a05a_0 \le 5, so there are at least 5 non-zero digits, and hence at least 4 of a1,a2,,a9a_1, a_2, \dots, a_9 are non-zero. But that means that a1+2a2+3a3++9a91+2+3+4a_1 + 2a_2 + 3a_3 + \cdots + 9a_9 \ge 1 + 2 + 3 + 4 with equality iff a1=a2=a3=a4=1a_1 = a_2 = a_3 = a_4 = 1 and a5=a6=a7=a8=a9=0a_5 = a_6 = a_7 = a_8 = a_9 = 0. But we must have equality because a1+2a2+3a3++9a9a_1 + 2a_2 + 3a_3 + \cdots + 9a_9 is the sum of the digits which is 10. However it is not possible to have a1=a2=a3=a4=1a_1 = a_2 = a_3 = a_4 = 1 and a5=a6=a7=a8=a9=0a_5 = a_6 = a_7 = a_8 = a_9 = 0 because then there are four 1s, but a4=1a_4 = 1.

So suppose some ai6a_i \ge 6. Then a61a_6 \ge 1. But a61a_6 \le 1, so a6=1a_6 = 1. Hence a1>0a_1 > 0. We cannot have a1=1a_1 = 1, because then there are at least two 1s, so a12a_1 \le 2. We cannot have a1=6a_1 = 6, because then there are six 1s and one 6, total 12, whereas all the digits only total 10. So a1a_1 must be some other digit k>1k > 1. But we now have at least six 0s, at least two 1s, a kk and a 6, which is at least
10. So it must be exactly 10. Hence a0=6a_0 = 6 and a1=2a_1 = 2. So the number must be 6210001000.

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.