Maths Olympiad Prep

Track / Stage 4 / 288 of 340 #1028 of 2444

Problem 1028

AMC 12 late, AIME early
Combinatorics Difficulty 4.9 Find the answer HMMT November

How many 8-digit numbers begin with 1 , end with 3 , and have the property that each successive digit is either one more or two more than the previous digit, considering 0 to be one more than 9 ?

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

Next problem →

Official solution

Given an 8-digit number aa that satisfies the conditions in the problem, let aia_{i} denote the difference between its (i+1)(i+1) th and ii th digit. Since i{1,2}i \in\{1,2\} for all 1i71 \leq i \leq 7, we have 7a1+a2++a7147 \leq a_{1}+a_{2}+\cdots+a_{7} \leq 14. The difference between the last digit and the first digit of mm is 3123-1 \equiv 2 (mod10)(\bmod 10), which means a1++a7=12a_{1}+\cdots+a_{7}=12. Thus, exactly five of the ai sa_{i} \mathrm{~s} equal to 2 and the remaining two equal to 1 . The number of permutations of five 2 s and two 1 s is (72)=21\binom{7}{2}=21.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.