Maths Olympiad Prep

Library / /173 of 377

Combinatorics Difficulty 5.0 AIME, harder Prove it United States

Problem:

How many positive integers less than or equal to 240240 can be expressed as a sum of distinct factorials? Consider 0!0! and 1!1! to be distinct.

Solution

Solution:

Answer: 3939

Note that 1=0!1 = 0!, 2=0!+1!2 = 0! + 1!, 3=0!+2!3 = 0! + 2!, and 4=0!+1!+2!4 = 0! + 1! + 2!. These are the only numbers less than 66 that can be written as the sum of factorials. The only other factorials less than 240240 are 3!=63! = 6, 4!=244! = 24, and 5!=1205! = 120. So a positive integer less than or equal to 240240 can only contain 3!3!, 4!4!, 5!5!, and/or one of 1,2,31, 2, 3, or 44 in its sum. If it contains any factorial larger than 5!5!, it will be larger than 240240. So a sum less than or equal to 240240 will either include 3!3! or not (22 ways), 4!4! or not (22 ways), 5!5! or not (22 ways), and add an additional 0,1,2,30, 1, 2, 3 or 44 (55 ways). This gives 2225=402 \cdot 2 \cdot 2 \cdot 5 = 40 integers less than 240240. However, we want only positive integers, so we must not count 00. So there are 3939 such positive integers.

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.