HMMT 十一月 2018 · THM 赛 · 第 6 题
HMMT November 2018 — THM Round — Problem 6
题目详情
英文原题
- Farmer James invents a new currency, such that for every positive integer n ≤ 6, there exists an n -coinworth n ! cents. Furthermore, he has exactly n copies of each n -coin. An integer k is said to be niceif Farmer James can make k cents using at least one copy of each type of coin. How many positiveintegers less than 2018 are nice?
解析
英文解析
- Farmer James invents a new currency, such that for every positive integer n ≤ 6, there exists an n -coinworth n ! cents. Furthermore, he has exactly n copies of each n -coin. An integer k is said to be niceif Farmer James can make k cents using at least one copy of each type of coin. How many positiveintegers less than 2018 are nice?
Proposed by: Nikhil Reddy
Answer: 210
We use the factorial base, where we denote
( d . . . d ) = d × n ! + · · · + d × 1!
n 1 ∗ n 1
The representation of 2018 is 244002 and the representation of 720 is 100000 . The largest nice
10 ∗ 10 ∗
number less than 244002 is 243321 . Notice that for the digit d of a nice number, we can vary its
∗ ∗ ivalue from 1 to i , while for a generic number in the factorial base, d can vary from 0 to i − 1.
i − 1
Hence we can map nice numbers to all numbers by truncating the last digit and reducing each previousdigit by 1, and likewise reverse the procedure by increasing all digits by 1 and adding 1 at the end.
Furthermore, this procedure preserves the ordering of numbers. Applying this procedure to 243321
∗
gives 13221 . We count from 0 to 13221 (since the first nice number is 1 ), to get an answer of
∗ ∗ ∗ ∗
13221 + 1 = 210 .
∗