Maths Olympiad Prep

Library / /201 of 348

Combinatorics Difficulty 4.9 AIME Find the answer

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. Spacing and $ signs are ignored.

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.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.