A number is formed using the digits $1,2, \ldots, 9$. Any digit can be used more than once, but adjacent digits cannot be the same. Once a pair of adjacent digits has occurred, that pair, in that order, cannot be used again. How many digits are in the largest such number?
(A) 72
(B) 73
(C) 144
(D) 145
(E) 91
A number is formed using the digits $1,2, \ldots, 9$. Any digit can be used more than once, but adjacent digits cannot be the same. Once a pair of adjacent digits has occurred, that pair, in that order, cannot be used again. How many digits are in the largest such number?
(A) 72
(B) 73
(C) 144
(D) 145
(E) 91

## Solution

Since there are $9(8)=72$ ordered pairs of consecutive digits, and since the final digit has no successor, we can construct a 73 digit number by adding a 9. The question is, of course, can we actually construct this number? The answer is 'yes' and the largest such number is,

9897969594939291878685848382817675747372716564636261 545352514342413231219.

If we count the numbers in the string we can see that there are actually 73 numbers contained within it.

ANSWER: (B)