HMMT 二月 2010 · COMB 赛 · 第 2 题

HMMT February 2010 — COMB Round — Problem 2

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

解析

[ 3 ] How many positive integers less than or equal to 240 can be expressed as a sum of distinct factorials? Consider 0! and 1! to be distinct. Answer: 39 Note that 1 = 0!, 2 = 0! + 1!, 3 = 0! + 2!, and 4 = 0! + 1! + 2!. These are the only numbers less than 6 that can be written as the sum of factorials. The only other factorials less than 240 are 3! = 6, 4! = 24, and 5! = 120. So a positive integer less than or equal to 240 can only contain 3!, 4!, 5!, and/or one of 1, 2, 3, or 4 in its sum. If it contains any factorial larger than 5!, it will be larger than 240. So a sum less than or equal to 240 will will either include 3! or not (2 ways), 4! or not (2 ways), 5! or not (2 ways), and add an additional 0 , 1 , 2 , 3 or 4 (5 ways). This gives 2 · 2 · 2 · 5 = 40 integers less than 240. However, we want only positive integers, so we must not count 0. So there are 39 such positive integers.