2022 AMC 12A Problem 19

Problem 19 of 25HarderCounting & Probability

Suppose that

13

cards numbered

1,

2,

3,

\ldots,

13

are arranged in a row. The task is to pick them up in numerically increasing order, working repeatedly from left to right. In the example below, cards

1,

2,

3

are picked up on the first pass,

4

and

5

on the second pass,

6

on the third pass,

7,

8,

9,

10

on the fourth pass, and

11,

12,

13

on the fifth pass. For how many of the

13!

possible orderings of the cards will the

13

cards be picked up in exactly two passes?

Show solution

Solution

Let

\text{pos}(k)

be the position of card

k.

A fresh pass is needed exactly when

\text{pos}(k+1)\lt\text{pos}(k),

so the number of passes is one more than the number of descents in the sequence

\text{pos}(1),\text{pos}(2),\ldots,\text{pos}(13).

To build a permutation with at most one descent, choose the entries before the possible descent and write both chosen blocks in increasing order. There are

2^{13}

subsets. The

14

initial segments

\varnothing,\{1\},\ldots,\{1,\ldots,13\}

produce no descent; every other subset produces a unique permutation with one descent. Hence the count is

2^{13}-14=8178.

Thus, the correct answer is D.

Answer choices

Solution

More practice