2022 AMC 10 A Problem 24

Complement Counting by First Violation

Instead of counting valid strings directly, count the invalid ones. Group the invalid strings by the *first* condition they fail. This forces exact counts for the digits, making them easy to calculate.

Step 1: Define the conditions mathematically

Let $c_j$ be the number of digits in the string that are strictly less than $j$. The problem requires the string to satisfy four conditions:

Step 2: Set up complement counting

We will count the number of invalid strings and subtract this from the total number of possible 5-digit strings.

Step 3: Classify invalid strings by their first failure

An invalid string fails at least one condition. Let $k$ be the smallest number for which the condition fails. This means the string fails at $k$, but passes for all $j<k$.

Step 4: Deduce the exact digit counts at the first failure

Because $c_k$ counts the digits less than $k$, and $c_{k-1}$ counts the digits less than $k-1$, the former must be at least as large as the latter. Since $k$ is the first failure, the condition for $k-1$ is satisfied. However, the condition for $k$ fails. Combining these inequalities forces both counts to be exactly $k-1$.

Step 5: Interpret the exact counts

The equality means exactly $k-1$ digits are less than $k-1$, and no digits are equal to $k-1$. The remaining digits must be greater than $k-1$.

Step 6: Count invalid strings for $k=1$

For the first case, there are no digits less than 1, meaning there are no ‘0’s. All 5 digits are chosen from the remaining 4 options.

Step 7: Count invalid strings for $k=2$

Here, exactly 1 digit is less than 1 (so it is ‘0’), and 0 digits are equal to 1. The remaining 4 digits are chosen from the 3 options greater than 1. We choose 1 position for the ‘0’ and fill the rest.

Step 8: Count invalid strings for $k=3$

Exactly 2 digits are chosen from the options less than 2, and 0 digits are equal to 2. The remaining 3 digits are chosen from the 2 options greater than 2. The 2 digits less than 2 must not fail the first condition, meaning they cannot both be ‘1’.

Step 9: Count invalid strings for $k=4$

Exactly 3 digits are chosen from the options less than 3, and 0 digits are equal to 3. The remaining 2 digits must be ‘4’. The 3 digits less than 3 must not fail the earlier conditions. We subtract the cases where they fail at the first condition (no ‘0’s) or the second condition (exactly one ‘0’ and no ‘1’s, meaning one ‘0’ and two ‘2’s).

Step 10: Calculate the final answer

Sum the invalid strings from all four cases and subtract from the total possible strings.

Pollak’s Circle Method (Parking Functions)

The problem’s conditions exactly describe a ‘parking function.’ We can count these elegantly by adding a dummy parking spot and arranging the spots in a circle.

Step 1: Translate the problem into a parking model

Add 1 to each digit to shift the available digits to a 1-indexed set. Let the new values represent the preferred parking spots of 5 cars trying to park in 5 spots in a line. The problem’s condition translates to requiring at least $j$ cars to prefer a spot $\le j$.

Step 2: Connect the condition to successful parking

Imagine each car drives to its preferred spot. If it is empty, it parks; if taken, it drives forward to the next available spot. If the condition holds for all $j$, all 5 cars will successfully park. If it fails for some $j$, too few cars want the early spots, leaving an early spot permanently empty and forcing a car to drive past the last spot.

Step 3: Apply Pollak’s Circle Method

To count these successful preference sequences (known as parking functions), we add a 6th dummy parking spot and arrange all 6 spots in a circle. We now allow cars to have preferences from 1 to 6.

Step 4: Identify the successful sequences

Because the spots are in a circle, cars keep driving until they find a spot. With 5 cars and 6 spots, everyone parks, and exactly 1 spot is left empty. By symmetry, each of the 6 spots is equally likely to be the empty one.

Step 5: Relate back to the linear parking lot

If spot 6 is empty, no car could have preferred spot 6, meaning these sequences only use preferences from 1 to 5. Furthermore, leaving spot 6 empty means no car was forced to drive past spot 5. This perfectly matches the condition for all cars to park successfully in the linear lot.