2008 iTest Problems/Problem 87

Problem

Find the number of $12$ -digit "words" that can be formed from the alphabet $\{0,1,2,3,4,5,6\}$ if neighboring digits must differ by exactly $2$ .

Solution

Since the "digits" are numbers, all of the digits of the "word" must have the same parity. We can use casework to split up the cases.

Case 1: All digits are odd

The "outer numbers" are 1 and 5, and the middle number is 3. Since neighboring digits differ by exactly 2, the outer numbers and the middle number must alternate. Denoting $O$ as the outer number, we must have the following:

$\text{O 3 O 3 O 3 O 3 O 3 O 3}$ $\text{3 O 3 O 3 O 3 O 3 O 3 O}$

It does not matter what the outer numbers are, and since both cases have the same number of outer numbers, there are $2^6 \cdot 2 = 128$ words that have odd digits.

Case 2: All digits are even

The "outer numbers" are 0 and 6, and the "middle numbers" are 2 and 4. In the sequence, we can not put two outer numbers in a row, and selecting one starting number determines the rest of the numbers (as there is only one adjacent edge number or middle number). As a result, we can split this case into further sub-cases depending on the number of outer numbers.

If there are zero outer numbers, the only option is having 12 middle numbers in a row, so there is $1$ option in this case.
If there is one outer number, there are $12$ options in this case.
If there are two outer numbers, one of the middle number must be sandwiched between to prevent two outer numbers being next to each other. The 9 other middle numbers can go anywhere, so there are $\tbinom{11}{2} = 55$ options in this case.
If there are three outer numbers, two of the middle numbers must be sandwiched between to prevent two outer numbers being next to each other. The 7 other middle numbers can go anywhere, so there are $\tbinom{10}{3} = 120$ options in this case.
Similarly, with four outer numbers, there are $\tbinom{9}{4} = 126$ options. With five outer numbers, there are $\tbinom{8}{5} = 56$ options. With six outer numbers, there are $\tbinom{7}{6} = 7$ options.
If there are seven (or more) outer numbers, six (or more) middle numbers must be sandwiched between to prevent two outer numbers being next to each other. However, that means the word has 13 digits, so this option does not work.

Since there are 2 ways to pick the starting number, there are $2 \cdot (7 + 56 + 126 + 120 + 55 + 13) = 754$ options if all of the digits are even.

Altogether there are $128 + 754 = \boxed{882}$ words that satisfy the conditions.

2008 iTest (Problems)
Preceded by: Problem 86	Followed by: Problem 88
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30 • 31 • 32 • 33 • 34 • 35 • 36 • 37 • 38 • 39 • 40 • 41 • 42 • 43 • 44 • 45 • 46 • 47 • 48 • 49 • 50 • 51 • 52 • 53 • 54 • 55 • 56 • 57 • 58 • 59 • 60 • 61 • 62 • 63 • 64 • 65 • 66 • 67 • 68 • 69 • 70 • 71 • 72 • 73 • 74 • 75 • 76 • 77 • 78 • 79 • 80 • 81 • 82 • 83 • 84 • 85 • 86 • 87 • 88 • 89 • 90 • 91 • 92 • 93 • 94 • 95 • 96 • 97 • 98 • 99 • 100

Page

Toolbox

Search

2008 iTest Problems/Problem 87

Problem

Solution

See Also