Maths Olympiad Prep

Library / /13 of 24

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!n! to your current number to get a new number. In how many ways can you get from 00 to 100100 in 44 seconds? (n!n! is defined as n×(n1)×(n2)××2×1n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1, so 1!=11! = 1, 2!=22! = 2, 3!=63! = 6, 4!=244! = 24, etc.)

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

Solution

Solution:

To get to 100100, you have to use one number which is at least 5!=1205! = 120, because 24×4=9624 \times 4 = 96, which is less than 100100. If you use 6!=7206! = 720 or anything larger, you need to get back from 720720 to 100100 (or further) in three seconds. Since 35!<6203 \cdot 5! < 620, there is no way to do this in 33 seconds. This means you have to use 5!5! at least once. The remaining numbers must get you from 120120 to 100100.

If you use three numbers all at most 3!3!, you can move by at most 33!=18<1201003 \cdot 3! = 18 < 120 - 100. This means you have to use 4!4!. From 12024=96120 - 24 = 96, there are two ways to get to 100100: adding 66 then subtracting 22, or adding 22 twice. So, to get to 100100 from 00 in four seconds, you must either add 120120, subtract 2424, add 66, and subtract 22, or add 120120, subtract 2424, and add 22 twice. You can do these steps in any order, so the first sequence yields 2424 paths and the second sequence yields 1212.

Answer: 3636

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.