← Sensim Lab Sensim Math

AMC 10 · 2021 · #20

Grade 6 counting
Archetype Branching State Enumeration
permutations-basicsystematic-enumerationpattern-recognitionsymmetry-argument caseworkeasier-related-problemsymmetry-argument ↑ Prerequisites: permutations-basic
📏 Long solution 💡 3 insights

Problem

In how many ways can the sequence 1,2,3,4,51,2,3,4,5 be rearranged so that no three consecutive terms are increasing and no three consecutive terms are decreasing?

Pick an answer.

(A)
~10
(B)
~18
(C)
~24
(D)
~32
(E)
~44
View mode:

Toolkit + CCSS Solution

Understand

Restated: 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.

Givens: Five distinct numbers: $1, 2, 3, 4, 5$; Forbidden: any three consecutive terms going up (e.g. $\dots a < b < c \dots$); Forbidden: any three consecutive terms going down (e.g. $\dots a > b > c \dots$); Choices: (A) $10$, (B) $18$, (C) $24$, (D) $32$, (E) $44$

Unknowns: Number of valid arrangements out of $5! = 120$

Understand

Restated: 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.

Givens: Five distinct numbers: $1, 2, 3, 4, 5$; Forbidden: any three consecutive terms going up (e.g. $\dots a < b < c \dots$); Forbidden: any three consecutive terms going down (e.g. $\dots a > b > c \dots$); Choices: (A) $10$, (B) $18$, (C) $24$, (D) $32$, (E) $44$

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #2 Make a Systematic List, #5 Look for a Pattern, #16 Change Focus / Count the Complement

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_3 = 4, a_4 = 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).

Execute — Answer: D

#9 Solve an Easier Related Problem 6.NS.C.7 Step 1
  • Reformulate: a triple $a < b < c$ or $a > b > c$ is forbidden.
  • So for every interior position, the term there is either greater than both its neighbors (peak) or smaller than both (valley).
  • That means signs of differences alternate — the arrangement zigzags up-down-up-down or down-up-down-up.
Pattern: $a_1 \lessgtr a_2 \gtrless a_3 \lessgtr a_4 \gtrless a_5$

💡 Each interior term must be a peak or a valley — no "flat" run of three increasing or decreasing.

#2 Make a Systematic List 4.OA.B.4 Step 2
  • Easier-Problem warmup: try $n = 3$.
  • List all $3! = 6$ permutations of $\{1, 2, 3\}$: $123, 132, 213, 231, 312, 321$.
  • Forbidden are the monotone ones $123$ and $321$.
  • Valid: $132, 213, 231, 312$ — that is $4$ arrangements.
Count$_3 = 4$

💡 Just drop the two monotone perms and count the rest.

#2 Make a Systematic List 5.OA.B.3 Step 3
  • Easier-Problem step 2: try $n = 4$.
  • Use Tool #16 (symmetry): valid arrangements split into those starting up ($a_1 < a_2$) and starting down ($a_1 > a_2$); reversing the inequalities pairs them, so the two halves are equal in count.
  • Enumerate up-down-up arrangements of $\{1, 2, 3, 4\}$ systematically.
  • The pattern is $a < b > c < d$.
  • By listing: $1324, 1423, 2314, 2413, 3412$ — five up-down-up arrangements.
  • Double by symmetry: $10$ total.
Count$_4 = 2 \cdot 5 = 10$

💡 Symmetry halves the work; then list up-down-up permutations by smallest first.

#2 Make a Systematic List 5.OA.B.3 Step 4
  • Apply the same symmetry to $n = 5$: count arrangements of pattern $a < b > c < d > e$ (up-down-up-down) and double.
  • Group by where the smallest element $1$ sits.
  • Since $1$ is smaller than every neighbor, $1$ must be a valley — positions $1, 3$ or $5$.
  • (Positions $2$ or $4$ would require $1$ to be a peak, impossible.)
$$1 \in \{\text{pos }1, 3, 5\}$$

💡 $1$ is the floor — it can only sit in valley positions.

#2 Make a Systematic List 5.OA.B.3 Step 5
  • Sub-case (a): $1$ at position 1, pattern $1 < b > c < d > e$.
  • The four remaining $\{2, 3, 4, 5\}$ fill $b, c, d, e$ with $b > c < d > e$.
  • Tool #2 (Systematic List) by smallest of $\{c, e\}$: $c = 2$ gives $b > 2 < d > e$, so $\{b, d, e\} = \{3, 4, 5\}$ with $b > 2, d > 2, d > e$, i.e.
  • any peak $d \in \{4, 5\}$ and the others split.
  • $d = 5$: $\{b, e\} = \{3, 4\}$, $b, e$ free (no constraint between them), so $2$ orderings.
  • $d = 4$: $\{b, e\} = \{3, 5\}$, $e < 4$ means $e = 3, b = 5$ — $1$ ordering.
  • Subtotal $c = 2$: $3$.
  • Symmetric: $e = 2$ gives $1 < b > c < d > 2$, by mirror-symmetry $3$ more arrangements.
  • Together $6$ for sub-case (a).
Sub-case (a): $6$ arrangements with $1$ at position $1$

💡 Pin $1$, then split by which interior valley equals $2$.

#2 Make a Systematic List 5.OA.B.3 Step 6
  • Sub-case (b): $1$ at position 3, pattern $a < b > 1 < d > e$ with $\{a, b, d, e\} = \{2, 3, 4, 5\}$.
  • Constraints: $a < b, d > e, b > 1$ (auto), $d > 1$ (auto).
  • Free constraints: choose any $\{a, b\}$ as a $2$-subset of $\{2,3,4,5\}$ (with $a < b$ giving $\binom{4}{2} = 6$ ways) and the remaining two go to $\{d, e\}$ with $d > e$ ($1$ way).
  • So $6$ arrangements.
Sub-case (b): $6$ arrangements with $1$ at position $3$

💡 Split $\{2,3,4,5\}$ into left pair (ascending) and right pair (descending) — that's $\binom{4}{2}$ choices.

#2 Make a Systematic List 5.OA.B.3 Step 7
  • Sub-case (c): $1$ at position 5, pattern $a < b > c < d > 1$.
  • Mirror of sub-case (a) (read right-to-left): also $4$ arrangements?
  • Let's recount directly.
  • Remaining $\{a, b, c, d\} = \{2, 3, 4, 5\}$, constraints $a < b, b > c, c < d, d > 1$ (auto).
  • Split by $c$: $c = 2$ gives $a < b > 2 < d$, $\{a, b, d\} = \{3, 4, 5\}$.
  • Need $b > a$ and $b > 2$ (auto) and $d > 2$ (auto).
  • $b \in \{3, 4, 5\}$, $a < b$, $\{a, d\} = \{3, 4, 5\} \setminus \{b\}$.
  • $b = 5$: $\{a, d\} = \{3, 4\}$, $a$ can be $3$ or $4$ — but $a < 5$ auto, both work — $2$.
  • $b = 4$: $\{a, d\} = \{3, 5\}$, need $a < 4$ so $a = 3, d = 5$ — $1$.
  • $b = 3$: $a < 3$, $a \in \{4, 5\}$ impossible — $0$.
  • Subtotal $c = 2$: $3$.
  • By symmetric counting on the other end, $c = 3$ with $a, b > 3$ and one of $\{4, 5\}$...
  • wait, let me re-split.
  • Actually split by which of $\{c, e\}$...
  • here $e$ is fixed as position with $1$.
  • Just split by $c$: $c$ is a valley between $b$ and $d$, $c \in \{2, 3\}$ since $c < b, c < d$.
  • $c = 3$: $a < b > 3 < d > 1$, $\{a, b, d\} = \{2, 4, 5\}$.
  • Need $a < b$, $b > 3$, $d > 3$.
  • $b, d \in \{4, 5\}$, so $\{b, d\} = \{4, 5\}$, $a = 2$.
  • $b, d$ orderings: $2$.
  • Subtotal $c = 3$: $2$.
  • Total sub-case (c): $3 + 2 = 5$.
  • Hmm, that's $5$ not $6$.
Sub-case (c): $5$ arrangements with $1$ at position $5$

💡 Split by the interior valley value $c \in \{2, 3\}$.

#5 Look for a Pattern 5.OA.B.3 Step 8
  • Recount sub-case (a) the same way for consistency.
  • Pattern $1 < b > c < d > e$, $\{b, c, d, e\} = \{2, 3, 4, 5\}$, $c$ is the interior valley ($c < b, c < d$), so $c \in \{2, 3\}$.
  • $c = 2$: $1 < b > 2 < d > e$, $\{b, d, e\} = \{3, 4, 5\}$.
  • Need $b > 2$ (auto), $d > 2$ (auto), $d > e$.
  • $d \in \{3, 4, 5\}$ as the peak: $d = 5$: $\{b, e\} = \{3, 4\}$, $e < 5$ auto, $b$ free — $2$ orderings.
  • $d = 4$: $\{b, e\} = \{3, 5\}$, $e < 4$ so $e = 3, b = 5$ — $1$.
  • $d = 3$: $\{b, e\} = \{4, 5\}$, $e < 3$ impossible — $0$.
  • Subtotal $c = 2$: $3$.
  • $c = 3$: $1 < b > 3 < d > e$, $\{b, d, e\} = \{2, 4, 5\}$.
  • Need $b > 3, d > 3$, so $\{b, d\} = \{4, 5\}$, $e = 2$.
  • $b, d$ orderings: $2$.
  • Subtotal $c = 3$: $2$.
  • Sub-case (a) total: $3 + 2 = 5$.
Sub-case (a) corrected: $5$ arrangements

💡 Mirror of (c) — same count by left-right symmetry.

#16 Change Focus / Count the Complement 4.NBT.B.4 Step 9
  • Add up-down-up-down (positive start) counts: $5 + 6 + 5 = 16$.
  • By Tool #16 symmetry (negate all positions: $a_i \to 6 - a_i$ flips up-down-up-down to down-up-down-up), down-up-down-up also has $16$.
  • Total valid: $16 + 16 = 32$.
  • Choice (D).
Total $= 2 \cdot 16 = 32 \Rightarrow \textbf{(D)}$

💡 Replace $a_i$ with $6 - a_i$ — every up becomes a down and vice versa, doubling the count.

[1] #9 6.NS.C.7 Reformulate: a triple $a < b < c$ or $a > b > c$ is forbidden. So for every inte
[2] #2 4.OA.B.4 Easier-Problem warmup: try $n = 3$. List all $3! = 6$ permutations of ${1, 2, 3
[3] #2 5.OA.B.3 Easier-Problem step 2: try $n = 4$. Use Tool #16 (symmetry): valid arrangements
[4] #2 5.OA.B.3 Apply the same symmetry to $n = 5$: count arrangements of pattern $a < b > c < d
[5] #2 5.OA.B.3 Sub-case (a): $1$ at position 1, pattern $1 < b > c < d > e$. The four remaining
[6] #2 5.OA.B.3 Sub-case (b): $1$ at position 3, pattern $a < b > 1 < d > e$ with ${a, b, d, e\
[7] #2 5.OA.B.3 Sub-case (c): $1$ at position 5, pattern $a < b > c < d > 1$. Mirror of sub-case
[8] #5 5.OA.B.3 Recount sub-case (a) the same way for consistency. Pattern $1 < b > c < d > e$,
[9] #16 4.NBT.B.4 Add up-down-up-down (positive start) counts: $5 + 6 + 5 = 16$. By Tool #16 symme

Review

Reasonableness: Sanity via the easier-problem pattern: $a_3 = 4, a_4 = 10, a_5 = 32$. The ratio $a_5 / a_4 = 3.2$ and $a_4 / a_3 = 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_3 = 2, E_4 = 5, E_5 = 16$, and the number of alternating permutations of $\{1, \dots, n\}$ is $2 E_n$. Plugging in: $2 \cdot 2 = 4$, $2 \cdot 5 = 10$, $2 \cdot 16 = 32$ — matches our hand counts at every $n$. Answer $32 = $ (D) confirmed.

Alternative: Tool #2 (Systematic List) brute force — write out all $120$ permutations of $\{1, 2, 3, 4, 5\}$ in lexicographic order and strike through any with three monotone consecutive terms. Tedious but bulletproof, and the resulting count of $32$ is a direct check on the case-split argument above. AoPS-style published enumeration gets the same answer.

CCSS standards used (min grade 6)

  • 6.NS.C.7 Understand ordering and absolute value of rational numbers (Reading "three increasing" / "three decreasing" as constraints on the order of adjacent terms.)
  • 4.OA.B.4 Find all factor pairs and recognize multiples; determine prime or composite (Listing all $6$ permutations of $\{1, 2, 3\}$ and identifying the two monotone ones — basic enumeration thinking.)
  • 5.OA.B.3 Generate two numerical patterns using two given rules and identify relationships (Systematic enumeration of alternating permutations: split by the position of the smallest element, then by interior-valley value.)
  • 4.NBT.B.4 Fluently add and subtract multi-digit whole numbers (Adding subcounts $5 + 6 + 5 = 16$, then doubling to $32$.)

⭐ "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 $\textbf{(D) }32$.

⭐ "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 $\textbf{(D) }32$.

More like this

Same archetype — closest grade level first.