For each positive integer , find the number of -digit positive integers that satisfy both of the following conditions:
[list]
[*] no two consecutive digits are equal, and
[*] the last digit is a prime.
[/list]
Solution
To solve this problem, we need to determine the number of -digit positive integers that meet two criteria:
1. No two consecutive digits are equal.
2. The last digit is a prime number.
### Step 1: Count All -Digit Numbers
The total number of -digit numbers is . The first digit can be any non-zero digit (1 to 9), giving us 9 choices. Each subsequent digit can be any digit from 0 to 9. Thus, the total number of -digit numbers is given by:
### Step 2: Account for the Last Digit Being Prime
The last digit must be a prime number. The single-digit prime numbers are 2, 3, 5, and 7. There are 4 choices for the last digit to be prime.
### Step 3: Ensure No Two Consecutive Digits Are Equal
To ensure no two consecutive digits are equal, the first digit is chosen from 9 options (1 to 9, as it cannot be 0). Each subsequent digit is selected from 9 possibilities as well, since it cannot equal the previous digit. Therefore, for an arbitrary -digit number, this gives us:
### Step 4: Calculate the Efficient Case
Considering all -digit numbers with no two consecutive digits equal, and ensuring the last digit is a prime, we use our last two observations to find the solution.
Since the condition of ending in a prime digit affects only the last digit, we independently multiply the choices for valid numbers by the fraction of these digits:
The term (or ) represents the probability that the last digit chosen is prime, within the context of all digits.
Thus, the count becomes:
### Step 5: Consider Alternating Sign Factor
Account for alternating sign factors based on parity of :
Upon careful analysis of different conditions on (whether is even or odd), we find that the adjustment effectively corrects the overcounting.
The final answer is: