Maths Olympiad Prep

Library / /552 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Kelvin the Frog likes numbers whose digits strictly decrease, but numbers that violate this condition in at most one place are good enough. In other words, if did_{i} denotes the ii th digit, then didi+1d_{i} \leq d_{i+1} for at most one value of ii. For example, Kelvin likes the numbers 43210, 132, and 3, but not the numbers 1337 and 123. How many 5-digit numbers does Kelvin like?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Suppose first that no digit violates the constraint; i.e. the digits are in strictly decreasing order. There are (105)\binom{10}{5} ways to choose the digits of the number, and each set of digits can be arranged in exactly one way, so there are (105)\binom{10}{5} such numbers. We now perform casework on which digit violates the constraint. If it is the final digit, the first four digits must be arranged in decreasing order, which there are (104)\binom{10}{4} ways to do. The final digit can then be any digit, but we have overcounted the ones in which the number is in fully decreasing order (this can happen, for example, if the first 4 digits we chose were 5,4,35,4,3, and 2 - a last digit of 1 was already counted in the first case). Therefore, there are (104)(101)252\binom{10}{4}\binom{10}{1}-252 new numbers in this case. If the offending digit is second from the right, the first 3 digits must be decreasing, as must the last 2 digits. There are (103)(102)\binom{10}{3}\binom{10}{2} ways to do this. As before, we overcount the case where the second digit from the right is not actually an offender, so we again overcount the case where all 5 digits decrease. Hence there are (103)(102)252\binom{10}{3}\binom{10}{2}-252 new numbers in this case. The case where the third digit is the offender is identical to the previous case, so there are another (103)(102)252\binom{10}{3}\binom{10}{2}-252 numbers to account for. The final case is when the second digit is the offending digit, in which case there are (104)\binom{10}{4} ways to choose the final 4 digits, but only 9 ways to choose the opening digit (as 0 cannot be a leading digit). Accounting for the usual overcounting, our final answer is 252+[(104)(101)252]+2[(103)(102)252]+[(104)9252]252+\left[\binom{10}{4}\binom{10}{1}-252\right]+2\left[\binom{10}{3}\binom{10}{2}-252\right]+\left[\binom{10}{4} \cdot 9-252\right] which is easily calculated as 14034.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.