Library / Annual Harvard-MIT November Tournament /9 of 20

Annual Harvard-MIT November Tournament

Combinatorics Difficulty 4.9 AIME Find the answer United States

Problem:

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.)

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

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$ .

Answer: $36$

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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