AMC 10 · 2021 · #20

Grade 6 counting

Archetype Branching State Enumeration └ Sub-archetype Constrained Sequence or Path Count

permutations-basicsystematic-enumerationpattern-recognitionsymmetry-argument caseworkeasier-related-problemsymmetry-argument ↑ Prerequisites: permutations-basic

📏 Long solution 💡 3 insights

Problem

Count the arrangements (permutations) of the sequence 1, 2, 3, 4, 5 such that nowhere in the arrangement do three consecutive terms appear in strictly increasing order, and nowhere do three consecutive terms appear in strictly decreasing order.

Pick an answer.

(A)

~10

(B)

~18

(C)

~24

(D)

~32

(E)

~44

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

How to solve

Strategy Solve an Easier Related Problem

Tool #9 (Easier Problem) — solve for n = 3 and n = 4 first, where we can list everything by hand. Tool #2 (Systematic List) — enumerate alternating permutations in lexicographic order so nothing is missed. Tool #5 (Pattern) — the small-case counts a₃ = 4, a₄ = 10 already reveal the structure, and Tool #16 (symmetry between "up-down" and "down-up" via reversing inequalities) cuts the work in half. With those in hand, count n = 5 by symmetry plus a clean case-split on the position of 1 (the unique smallest element).

1STEP 1

Reframe the ban: every interior term is a peak or a valley, so difference signs alternate — the arrangement must zigzag.

Pattern: a₁ ≶ a₂ ＞ rless a₃ ≶ a₄ ＞ rless a₅

2STEP 2

Warm up with n = 3: of the 3! = 6 permutations only the two monotone ones (123, 321) are banned, leaving 4 arrangements.

Count₃ = 4

3STEP 3

For n = 4, symmetry pairs up-down with down-up; listing the up-down-up permutations gives 5, so doubling yields 10.

Count₄ = 2 · 5 = 10

4STEP 4

Now n = 5, pattern a ＜ b ＞ c ＜ d ＞ e: since 1 is below both neighbors it must be a valley — positions 1, 3, or 5.

1 ∈ {pos 1, 3, 5}

5STEP 5

1 at position 1 (1 ＜ b ＞ c ＜ d ＞ e): a first count over the interior valley c gives 6 arrangements, revisited in step 8.

Sub-case (a): 6 arrangements with 1 at position 1

6STEP 6

1 at position 3 (a ＜ b ＞ 1 ＜ d ＞ e): split {2, 3, 4, 5} into an ascending pair and a descending pair — C(4, 2) = 6 arrangements.

Sub-case (b): 6 arrangements with 1 at position 3

7STEP 7

1 at position 5 (a ＜ b ＞ c ＜ d ＞ 1): split by the interior valley c ∈ {2, 3} — c = 2 gives 3 and c = 3 gives 2, for 5 arrangements.

Sub-case (c): 5 arrangements with 1 at position 5

8STEP 8

Recount 1 at position 1 by the interior valley c ∈ {2, 3}: c = 2 gives 3 and c = 3 gives 2, so the true count is 5, not 6.

Sub-case (a) corrected: 5 arrangements

Answer

~32

Sanity via the easier-problem pattern: a₃ = 4, a₄ = 10, a₅ = 32. The ratio a₅ / a₄ = 3.2 and a₄ / a₃ = 2.5 — growth is reasonable (well under n+1 per step since constraints get stronger as n grows). Another check: the well-known "zigzag" (Euler) numbers E_n satisfy E₃ = 2, E₄ = 5, E₅ = 16, and the number of alternating permutations of {1, …, n} is 2 E_n. Plugging in: 2 · 2 = 4, 2 · 5 = 10, 2 · 16 = 32 — matches our hand counts at every n. Answer 32 = (D) confirmed.

💡Key takeaway

"No three in a row going up or down" means the arrangement has to zigzag. Pin the smallest number 1 (it can only be a valley, so positions 1, 3, or 5), count carefully — you get 5 + 6 + 5 = 16 up-down-up-down arrangements. Double for the down-up-down-up mirror pattern: 32. Answer (D) 32.

More like this