HMMT 十一月 2009 · GEN2 赛 · 第 2 题

HMMT November 2009 — GEN2 Round — Problem 2

[ 4 ] You start with a number. Every second, you can add or subtract any number of the form n ! to your current number to get a new number. In how many ways can you get from 0 to 100 in 4 seconds? ( n ! is defined as n × ( n − 1) × ( n − 2) × · · · × 2 × 1, so 1! = 1, 2! = 2, 3! = 6, 4! = 24, etc.)

解析

[ 4 ] You start with a number. Every second, you can add or subtract any number of the form n ! to your current number to get a new number. In how many ways can you get from 0 to 100 in 4 seconds? ( n ! is defined as n × ( n − 1) × ( n − 2) × · · · × 2 × 1, so 1! = 1, 2! = 2, 3! = 6, 4! = 24, etc.) Answer: 36 To get to 100, you have to use one number which is at least 5! = 120, because 24 × 4 = 96, which is less than 100. If you use 6! = 720 or anything larger, you need to get back from 720 to 100 (or further) in three seconds. Since 3 · 5! < 620, there is no way to do this in 3 seconds. This means you have to use 5! at least once. The remaining numbers must get you from 120 to 100. If you use three numbers all at most 3!, you can move by at most 3 · 3! = 18 < 120 − 100. This means you have to use 4!. From 120 − 24 = 96, there are two ways to get to 100: adding 6 then subtracting 2, or adding 2 twice. So, to get to 100 from 0 in four seconds, you must either add 120, subtract 24, add 6, and subtract 2, or add 120, subtract 24, and add 2 twice. You can do these steps in any order, so the first sequence yields 24 paths and the second sequence yields 12.