A palindrome is a word, phrase, or positive integer that reads the same forwards and backwards. For example, "kayak" is a palindrome. The integers \(292\), \(11\), and \(6\,357\,536\) are also palindromes.
Determine the number of nine-digit palindromic integers that satisfy the following:
The first five digits in the integer are distinct.
The integer is divisible by 4 and/or the integer ends with an 8.
Any nine-digit palindromic integer with the first five digits distinct will be of the form \(abcdedcba\), where \(a\), \(b\), \(c\), \(d\), and \(e\) are distinct digits.
First we will count the number of such palindromes that end with \(8\). These will be integers of the form \(8bcdedcb8\) where \(b,c,d,e \ne 8\). In this case, there will be \(9\) choices for the digit \(b\), \(8\) choices for the digit \(c\), \(7\) choices for the digit \(d\), and \(6\) choices for the digit \(e\). Therefore, the number of palindromes with the first five digits distinct that end with \(8\) is \(9 \times 8 \times 7 \times 6 = 3024\).
Next we will count the number of palindromes with the first five digits distinct that are divisible by \(4\) but do not end with \(8\). (We must exclude the palindromes that end with \(8\) because we already counted them above.) In general, if an integer is divisible by \(4\) then the integer formed by its last two digits must be divisible by \(4\). Therefore, if an integer of the form \(abcdedcba\) is divisible by \(4\), then the two-digit integer \(ba\) must be divisible by \(4\). However we cannot have \(a=0\) since the leading digit in our palindrome cannot be \(0\). Thus, we need to determine the number of two-digit integers \(ba\) with \(b \ne a\) and \(a \ne 0,8\) that are divisible by \(4\). These are:
\(04\), \(12\), \(16\), \(24\), \(32\), \(36\), \(52\), \(56\), \(64\), \(72\), \(76\), \(84\), \(92\), \(96\)
In total there are \(14\) possibilities for \(ba\). For each of these possibilities, there are \(8\) choices for the digit \(c\), \(7\) choices for the digit \(d\), and \(6\) choices for the digit \(e\). Therefore, the number of palindromes with the first five digits distinct that are divisible by \(4\) but do not end with \(8\) is \(14 \times 8 \times 7 \times 6 = 4704\).
Thus, the number of nine-digit palindromic integers with the first five digits distinct that are divisible by \(4\) and/or end with \(8\) is \(3024 + 4704 = 7728\).