HMMT 十一月 2020 · 冲刺赛 · 第 24 题

HMMT November 2020 — Guts Round — Problem 24

[12] Compute the number of positive integers less than 10! which can be expressed as the sum of at most 4 (not necessarily distinct) factorials. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMO 2020, November 14–21, 2020 — GUTS ROUND Organization Team Team ID# ∑ 100

解析

[12] Compute the number of positive integers less than 10! which can be expressed as the sum of at most 4 (not necessarily distinct) factorials. Proposed by: Sheldon Kieren Tan Answer: 648 Solution: Since 0! = 1! = 1, we ignore any possible 0!’s in our sums. Call a sum of factorials reduced if for all positive integers k , the term k ! appears at most k times. It is straightforward to show that every positive integer can be written uniquely as a reduced sum of factorials. Moreover, by repeatedly replacing k + 1 occurrences of k ! with ( k + 1)!, every non-reduced sum of factorials is equal to a reduced sum with strictly fewer terms, implying that the aforementioned reduced sum associated to a positive integer n in fact uses the minimum number of factorials necessary. It suffices to compute the number of nonempty reduced sums involving { 1! , 2! , . . . , 9! } with at most 4 ( ) 13 terms. By stars and bars, the total number of such sums, ignoring the reduced condition, is = 714. 9 The sums that are not reduced must either contain two copies of 1!, three copies of 2!, or four copies of 3!. Note that at most one of these conditions is true, so we can count them separately. If k ( ) 13 − k terms are fixed, there are ways to choose the rest of the terms, meaning that we must subtract 9 ( ) ( ) ( ) 11 10 9