PUMaC 2022 · 组合（B 组） · 第 2 题
PUMaC 2022 — Combinatorics (Division B) — Problem 2
题目详情
- The base factorial number system is a unique representation for positive integers where the n th digit from the right ranges from 0 to n inclusive and has place value n ! for all n ≥ 1. For instance, 71 can be written in base factorial as 2321 = 2 · 4! + 3 · 3! + 2 · 2! + 1 · 1!. Let S ( n ) ! ! 700 P be the base 10 sum of the digits of n when n is written in base factorial. Compute S ( n ) ! n =1 (expressed in base 10).
解析
- The base factorial number system is a unique representation for positive integers where the n th digit from the right ranges from 0 to n inclusive and has place value n ! for all n ≥ 1. For instance, 71 can be written in base factorial as 2321 = 2 · 4! + 3 · 3! + 2 · 2! + 1 · 1!. Let S ( n ) ! ! 700 P be the base 10 sum of the digits of n when n is written in base factorial. Compute S ( n ) ! n =1 (expressed in base 10). Proposed by Julian Shah Answer: 5163 First, we compute the sum as n ranges from 0 to 719 . Observe that n ranges from 0 to 10 ! 54321 . The sum includes all possible numbers with at most five digits in the base factorial ! system. There are exactly k + 1 possible choices for the value of the k th digit from the right. 720 Given some value m of this digit, then, exactly of these numbers have m in the digit place. k +1 k P k ( k +1) 720 720 Thus, the sum of the k th digits over all 720 numbers is is i = · = 360 k . k +1 k +1 2 i =0 P 5 Thus, our total sum is 360 k = 360 · 15 = 5400. k =1 Now, we need to subtract off the contributions from 701 to 719 (and from 0 which has digit sum 0). Note that 701 = 54021 , so digits 5 and 4 remain the same for all 19 numbers for 10 ! a sum of 19 · 9 = 171. For the third digit from the right, there are six occurrences each of 3, 2, and 1, and one occurrence of 0, for a sum of 6 · (3 + 2 + 1) = 36. For the second digit from the right, there are six occurrences each of 2, 1, and 0 for 702 through 719, and then one more occurrence of 2 for 701 for a sum of 7 · 2 + 6 · 1 = 20. Finally, the first digit is one exactly 19+1 = 10 times for a sum of 10. Thus, our final answer is 5400 − 171 − 36 − 20 − 10 = 5163. 2