Maths Olympiad Prep

Library / /692 of 740

, 2018

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

Farmer James invents a new currency, such that for every positive integer n6n \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
(dnd1)=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 244002244002_{*} and the representation of 72010720_{10} is 100000100000_{*}. The largest nice number less than 244002244002_{*} is 243321243321_{*}. 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, di1d_{i-1} can vary from 0 to i1i-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 243321243321_{*} gives 1322113221_{*}. We count from 00_{*} to 1322113221_{*} (since the first nice number is 11_{*}), 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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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