AMC 10 · 2023 · #24

Grade 10 counting

Archetype Branching State Enumeration └ Sub-archetype Ordered Placement Count

fundamental-counting-principleexponentsmodular-arithmetic-mod-10symmetry-argument easier-related-problempattern-recognitionidentify-subproblems ↑ Prerequisites: fundamental-counting-principleexponents

📏 Long solution 💡 3 insights

Problem

Build chains of subsets of the numbers one through ten. First pick a length up to ten, then pick that many subsets so that each contains the one before it. Repeats are allowed. Find the remainder when the total number of such chains, over every allowed length, is divided by ten.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Change Focus / Count the Complement

Counting the chains set by set is a dead end. Choosing A₁ leaves a different number of options for A₂ depending on how big A₁ turned out to be, so the choices are tangled and the casework explodes. The escape is to stop looking at the sets and look at the elements instead. The containment condition says nothing about sets as a whole once it is read one element at a time: it just says an element that has entered can never leave. That makes each element's entire life story a single number, the moment it walks in, and it makes the ten elements completely independent of one another. Ten independent choices multiply, which kills the chain count for a fixed length in one line. After that the problem splits into two clean halves: add the ten length-counts together, then throw away everything except the last digit.

1STEP 1

Read it one element at a time

Once in, an element stays in.

j ∈ A_i-1 → j ∈ A_i → j ∈ A_i+1 → … → j ∈ A_n

2STEP 2

Record the entry time

Record each element's entry time.

t(j) ∈ {1, 2, …, n} ∪ {never}, A_i = { j : t(j) ≤ i }

3STEP 3

Independent choices multiply

The ten choices are independent.

(chains of length n) = (n+1) × (n+1) × … × (n+1)₁₀ elements = (n+1)¹⁰

4STEP 4

Test on tiny cases

Test the formula on tiny cases.

ground set {1}: 2¹ = 2, 3¹ = 3 ground set {1,2}: 2² = 4, 3² = 9, 4² = 16

5STEP 5

Add over every length

Add over every allowed length.

K = Σ_n=1¹⁰ (n+1)¹⁰ = 2¹⁰ + 3¹⁰ + 4¹⁰ + … + 11¹⁰ = Σ_m=2¹¹ m¹⁰

6STEP 6

Keep only the last digit

Keep only the units digit.

K ≡ Σ_m=2¹¹ m¹⁰ ≡ Σ_r=0⁹ r¹⁰ (mod 10)

7STEP 7

Pair the digits and finish

Pairing and adding gives 5.

Σ_r=0⁹ r¹⁰ ≡ 0 + 5 + 2(1 + 4 + 9 + 6) = 5 + 40 = 45 ≡ 5 (mod 10)

Answer

The final digit can be confirmed by a route that shares nothing with the one above: split the modulus into 2 and 5. For the parity, an even base raised to any power is even and an odd base raised to any power is odd, and among the bases 2, 3, …, 11 exactly five are odd, namely 3, 5, 7, 9, 11. A sum of five odd numbers and five even numbers is odd, so K is odd. This is consistent with every listed choice, since all five are odd, which is itself a hint that the parity was never going to be the deciding fact. For the factor of 5, Fermat's little theorem gives m⁴ ≡ 1 (mod 5) whenever m is not a multiple of 5, so m¹⁰ = m⁸ · m² ≡ m² (mod 5). The bases 5 and 10 contribute 0, and the remaining eight bases 2, 3, 4, 6, 7, 8, 9, 11 give squares congruent to 4, 4, 1, 1, 4, 4, 1, 1, which total 20 ≡ 0 (mod 5). So K is odd and divisible by 5, and the only such remainder modulo 10 is 5. Both routes agree. As a final check on size, the exact value is K = 2¹⁰ + 3¹⁰ + … + 11¹⁰ = 40851766525, which does end in 5, and it is dominated by its last term 11¹⁰ = 25937424601, exactly as expected when the terms grow this fast.

💡Key takeaway

A chain of nested sets is really ten stopwatches, one per element, each recording the moment that element walked in and stayed, so counting chains is nothing more than counting stopwatch settings.

Read the rule one element at a time
Record each element's entry time
Ten independent choices multiply
Test the formula on tiny cases
Add over every allowed length
Keep only the last digit
Pair the digits and finish