Maths Olympiad Prep

Library / HMMT November /627 of 672

HMMT November, 2018

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

Farmer James invents a new currency, such that for every positive integer n≤6n \leq 6, there exists an nn-coin worth n!n! cents. Furthermore, he has exactly nn copies of each nn-coin. An integer kk is said to be nice if Farmer James can make kk cents using at least one copy of each type of coin. How many positive integers less than 2018 are nice?

Solution

Solution:

We use the factorial base, where we denote
(dn…d1)∗=dn×n!+⋯+d1×1! \left(d_{n} \ldots d_{1}\right)_{*}=d_{n} \times n!+\cdots+d_{1} \times 1!
The representation of 2018102018_{10} is 244002∗244002_{*} and the representation of 72010720_{10} is 100000∗100000_{*}. The largest nice number less than 244002∗244002_{*} is 243321∗243321_{*}. Notice that for the digit did_{i} of a nice number, we can vary its value from 1 to ii, while for a generic number in the factorial base, di−1d_{i-1} can vary from 0 to i−1i-1. Hence we can map nice numbers to all numbers by truncating the last digit and reducing each previous digit 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∗243321_{*} gives 13221∗13221_{*}. We count from 0∗0_{*} to 13221∗13221_{*} (since the first nice number is 1∗1_{*}), to get an answer of
13221∗+1=210 13221_{*}+1=210

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.