Discrete Math Counting Question

Question

How many 10-digit telephone numbers (that is, length-10 sequences with entries from ) are there for which no two adjacent numbers are both even or both odd?

I calculated 14400 from 5! * 5! but this was wrong. Then I thought maybe it was 28800 but this was also wrong. Any help or hints would be greatly appreciated!

Answer 1

Let us assume the digits we are allowed to use are taken from the set {0, 1, 2, ..., 8, 9}. To ensure no two neighboring digits are both even or both odd, this implies our phone number must alternate being even and odd digits. So if the first digit is even, the next digit must be odd, and then the following digit must be even, and so on. There is a similar pattern if the first digit is odd.

Since there are exactly 5 even and 5 odd numbers in {0, 1, .., 8, 9}, and since our phone number is 10 digits, this implies the total number of phone numbers is 2 * 5^5 * 5^5 = 2 * 5^10. We can see this by first recognizing that given the first digit is even, there are 5^10 satisfying phone numbers. Similarly, given the first digit is odd, there are also 5^10 satisfying phone numbers. So in total, there are 5^10 + 5^10 = 2 * 5^10 phone numbers that satisfy the property we care about.