HMMT 二月 2017 · COMB 赛 · 第 5 题
HMMT February 2017 — COMB Round — Problem 5
题目详情
- 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 d denotes the i th digit, then d ≤ d for i i i +1 at most one value of i . 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?
解析
- 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 d denotes the i th digit, then d ≤ d for i i i +1 at most one value of i . 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? Proposed by: Alexander Katz Answer: 14034 Suppose first that no digit violates the constraint; i.e. the digits are in strictly decreasing order. There ( ) 10 are ways to choose the digits of the number, and each set of digits can be arranged in exactly one 5 ( ) 10 way, so there are such numbers. 5 We now perform casework on which digit violates the constraint. If it is the final digit, the first four ( ) 10 digits must be arranged in decreasing order, which there are ways to do. The final digit can then 4 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, 3, and 2 – a last digit of 1 was already ( )( ) 10 10 counted in the first case). Therefore, there are − 252 new numbers in this case. 4 1 If the offending digit is second from the right, the first 3 digits must be decreasing, as must the last ( )( ) 10 10 2 digits. There are ways to do this. As before, we overcount the case where the second digit 3 2 from the right is not actually an offender, so we again overcount the case where all 5 digits decrease. ( )( ) 10 10 Hence there are − 252 new numbers in this case. 3 2 The case where the third digit is the offender is identical to the previous case, so there are another ( )( ) 10 10 − 252 numbers to account for. The final case is when the second digit is the offending digit, 3 2 ( ) 10 in which case there are ways to choose the final 4 digits, but only 9 ways to choose the opening 4 digit (as 0 cannot be a leading digit). Accounting for the usual overcounting, our final answer is [( )( ) ] [( )( ) ] [( ) ] 10 10 10 10 10 252 + − 252 + 2 − 252 + · 9 − 252 4 1 3 2 4 which is easily calculated as 14034 .