AMC 10 · 2022 · #22

Grade 8 arithmetic

combinations-basiccomplementary-countingpattern-recognition easier-related-problemcomplementary-countingpattern-recognition ↑ Prerequisites: combinations-basic

📏 Medium solution 💡 3 insights 📊 Diagram

Problem

We arrange 13 numbered cards 1, 2, …, 13 in a row. In each pass we scan left to right and pick up the next-numbered uncollected card whenever it lies to the right of the previously picked card in that pass. How many of the 13! orderings get the cards picked up in exactly two passes?

Pick an answer.

(A)

4082

(B)

4095

(C)

4096

(D)

8178

(E)

8191

AMC 10 2022 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve

Strategy Solve an Easier Related Problem

Tool #9 (Easier Problem) and #2 (Systematic List): try the question for n = 2, 3, 4 cards by listing every permutation and counting passes. The data points fit the formula 2ⁿ - n - 1 (Tool #5). Why? Tool #16 (Complement / re-cast): pass 1 collects an initial segment {1, …, k}, and an ordering uses at most two passes iff cards {1, …, k} are in increasing relative order AND cards {k+1, …, 13} are in increasing relative order — that is, the permutation is the shuffle of two increasing subsequences. There are C(13, k) such shuffles for each k, but each non-trivial labeling of cards as 'first set' vs 'second set' is unique except for the fully sorted permutation which counts in every k. Tool #3 confirms the magnitude ≈ 8000 rules out (A)-(C).

1STEP 1

Try the tiny case n = 2: orderings 12 (one pass) and 21 (two passes), so the two-pass count is 1.

n=2: two-pass = 1 = 2² - 2 - 1

2STEP 2

Try n = 3: of all 6 orderings only 123 (one pass) and 321 (three) miss, so the two-pass count is 4.

n=3: two-pass = 4 = 2³ - 3 - 1

3STEP 3

In general, an ordering finishes in at most two passes exactly when the row is a shuffle of two increasing runs {1,…,k} and {k+1,…,13}.

at most 2 passes ⇔ both prefixes increasing in position

4STEP 4

Each subset of the 13 positions chosen for the low cards gives exactly one such ordering, so there are 2¹³ = 8192 of them.

#{ ≤ 2 passes} = 2¹³ = 8192

5STEP 5

Only the sorted row is over-counted (14 times) and it is one-pass, so exactly-two-pass orderings = 8192 - 14 = 8178, choice (D).

(2¹³ - 14) + 1 - 1 = 8192 - 14 = 8178 → (D)

Answer

8178

Pattern check from the small cases: n=2 gave 1 = 4 - 3, n=3 gave 4 = 8 - 4. The formula 2ⁿ - n - 1 matches both, and for n=13 gives 8192 - 14 = 8178, exactly one of the offered choices. The answer is well under 13! (about 6.2 × 10⁹), as expected — the two-pass orderings are a tiny structured subset of all permutations.

💡Key takeaway

This AMC 10 problem only needs Grade 8 powers of 2 you already know — try n=2 and n=3 by hand, spot the pattern 2ⁿ - n - 1, then plug in n = 13 to get 8192 - 14 = 8178.