HMMT-Nov 2009 thm, Problem 2

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 \times(n-1) \times(n-2) \times \cdots \times 2 \times 1$, so $1 !=1,2 !=2,3 !=6,4 !=24$, etc. $)$

Solution: To get to 100, you have to use one number which is at least $5 !=120$, because $24 \times 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 \cdot 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 \cdot 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 . $\fbox{36}$.

Answer: 36