Maths Olympiad Prep

Library / /1 of 34

Combinatorics Difficulty 5.8 AIME, harder Find the answer

For each positive integer nn, find the number of nn-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]

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to determine the number of n n -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 n n -Digit Numbers

The total number of n n -digit numbers is 9×10n1 9 \times 10^{n-1} . 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 n n -digit numbers is given by:
9×10n1 9 \times 10^{n-1}

### 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 n n -digit number, this gives us:
9×9n1 9 \times 9^{n-1}

### Step 4: Calculate the Efficient Case

Considering all n n -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:
4109×9n1 \frac{4}{10} \cdot 9 \times 9^{n-1}

The term 410\frac{4}{10} (or 25\frac{2}{5}) represents the probability that the last digit chosen is prime, within the context of all digits.

Thus, the count becomes:
4109n=259n \frac{4}{10} \cdot 9^n = \frac{2}{5} \cdot 9^n

### Step 5: Consider Alternating Sign Factor

Account for alternating sign factors based on parity of n n :
Upon careful analysis of different conditions on n n (whether n n is even or odd), we find that the adjustment 25(1)n\frac{2}{5} \cdot (-1)^n effectively corrects the overcounting.

The final answer is:
259n25(1)n \boxed{\frac{2}{5} \cdot 9^n - \frac{2}{5} \cdot (-1)^n}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.