Library / /393 of 1394

, 2023

Combinatorics Difficulty 5.1 AIME, harder Find the answer United States

Problem:

The number $770$ is written on a blackboard. Melody repeatedly performs moves, where a move consists of subtracting either $40$ or $41$ from the number on the board. She performs moves until the number is not positive, and then she stops. Let $N$ be the number of sequences of moves that Melody could perform. Suppose $N = a \cdot 2^{b}$ where $a$ is an odd positive integer and $b$ is a nonnegative integer. Compute $100a + b$ .

Your answer

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

Solution

Solution:

Notice that if we use the $41$ move nine times or less, we will have to make a total of $\left\lceil\frac{770}{40}\right\rceil = 20$ moves, and if we use it ten times or more, we will have to make a total of $\left\lfloor\frac{770}{40}\right\rfloor = 19$ moves. So, doing casework on the number of $40$ s we use gives
$\underbrace{\binom{19}{0} + \binom{19}{1} + \binom{19}{2} + \cdots + \binom{19}{9}}_{19 \text{ moves}} + \underbrace{\frac{\binom{20}{10}}{2} + \binom{20}{11} + \binom{20}{12} + \cdots + \binom{20}{20}}_{20 \text{ moves}}.$
Using the row sums of Pascal's triangle we have this sum equal to $\frac{2^{19}}{2} + \frac{2^{20}}{2} = 3 \cdot 2^{18}$ . The answer is $318$ .

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.