Maths Olympiad Prep

Library / /13 of 13

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Italy

Problem:

We call monotone numbers the positive integers such that
- they are written using at least two digits;
- no digit is zero;
- the digits appear in strictly increasing or strictly decreasing order.
(For example 127127 and 97429742 are monotone numbers, while 172172, 12241224 and 73207320 are not.)

a. Compute the sum of all five-digit monotone numbers.

b. Determine with how many zeros the least common multiple of all monotone numbers ends (with no constraint on the number of digits).

Solution

Solution:

a. We call increasing the monotone numbers whose digits appear in increasing order, and similarly we call decreasing the monotone numbers whose digits appear in decreasing order. We further call twin of a monotone number NN the integer obtained by replacing every digit of NN with its complement to 1010. Thus, for example, the twin of 1257812578 is 9853298532.

Note that every decreasing number is the twin of an increasing number, and vice versa. Moreover, it is easy to see that the sum of a five-digit monotone number and its twin is always equal to 111110111110.

Suppose now that we have written the sum SS of all five-digit monotone numbers. In this sum we can group the addends in pairs, so that to each increasing number corresponds its decreasing twin. By the previous observation, performing the sums in pairs, we get that SS becomes the sum of addends all equal to 111110111110. Moreover, the addends are as many as the increasing numbers, which in turn are as many as the ways to choose five different digits from a set of nine, that is
(95)=9!5!4!=126 \binom{9}{5} = \frac{9!}{5!\,4!} = 126
Without using the combinatorial meaning of binomial coefficients one can reason as follows. First we choose the 55 different digits that make up the number: the first can be chosen in 99 different ways, the second in 88, ..., the fifth in 55. In doing so we do not always obtain an increasing number: indeed, in order to obtain one, the first digit must be the smallest of the 55 chosen, which happens only once out of 55, the second must be the smallest of the remaining 44, which happens only once out of 44, and so on. Consequently the increasing numbers are
987655432=126 \frac{9 \cdot 8 \cdot 7 \cdot 6 \cdot 5}{5 \cdot 4 \cdot 3 \cdot 2} = 126
Therefore the sum of all five-digit monotone numbers is 126111110=13999860126 \cdot 111110 = 13999860.

b. Let us denote by MM the least common multiple of all monotone numbers. We first observe that the set of monotone numbers is finite (because no monotone number can have more than nine digits), hence MM is well defined.

To know with how many zeros MM ends, we need to know the largest power of 1010 that divides MM. To this end we consider separately the powers of 22 and of 55. Let us begin by analyzing the case of 55. The largest power of 55 that divides MM equals the largest power of 55 by which a monotone number is divisible. This power is at least 33, since 53=1255^{3} = 125 is a monotone number. Moreover all integers divisible by 125125 necessarily end with 000000, 125125, 250250, 375375, 500500, 625625, 750750, 875875, and consequently the monotone multiples of 125125 can only end with 125125 or 875875. The only monotone numbers having such an ending are 125125, 875875, 98759875, none of which is divisible by 545^{4}. Therefore the largest power of 55 that divides MM is 535^{3}.

Since MM obviously contains more than three factors of 22 (for example 24=162^{4} = 16 is a monotone number), it follows that MM ends with exactly 33 zeros.

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 translated into English from it; metadata (topic, difficulty) added by this project.