AMC 10 · 2021 · #20

학년 6 counting

유형 Branching State Enumeration └ 세부 유형 Constrained Sequence or Path Count

permutations-basicsystematic-enumerationpattern-recognitionsymmetry-argument caseworkeasier-related-problemsymmetry-argument ↑ 선수 지식: permutations-basic

📏 긴 풀이 💡 3 개 인사이트

문제

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

답을 골라 클릭하세요.

(A)

~10

(B)

~18

(C)

~24

(D)

~32

(E)

~44

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

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 수열 $1, 2, 3, 4, 5$ 를 재배열할 때, 연속한 세 항이 단조증가하지도 단조감소하지도 않도록 하는 배열의 가짓수를 구하세요.

주어진 것: 서로 다른 다섯 수 $1, 2, 3, 4, 5$; 금지: 연속한 세 항이 증가 ($\dots a b > c \dots$); 선택지: (A) $10$, (B) $18$, (C) $24$, (D) $32$, (E) $44$

구하는 것: 전체 $5! = 120$ 가지 중 조건을 만족하는 배열의 수

이해

문제 재정리: 수열 $1, 2, 3, 4, 5$ 를 재배열할 때, 연속한 세 항이 단조증가하지도 단조감소하지도 않도록 하는 배열의 가짓수를 구하세요.

계획

주요 도구: #9 더 쉬운 문제로 줄이기

보조 도구: #2 빠짐없이 나열하기, #5 패턴 찾기, #16 관점 바꾸기

도구 #9 (더 쉬운 문제): $n = 3, n = 4$ 를 먼저 손으로 다 세어 봅니다. 도구 #2 (빠짐없이 나열): 누락 없이 사전순으로 alternating permutation 을 적습니다. 도구 #5 (패턴): 작은 경우 결과 $a_3 = 4, a_4 = 10$ 에서 구조가 보이고, 도구 #16 (관점 바꾸기) 의 "위로 시작" vs "아래로 시작" 대칭이 일거리를 절반으로 줄입니다. 이를 활용해 $n = 5$ 를 최소 원소 $1$ 의 위치로 분할해 셉니다.

실행 — 정답: D

#9 더 쉬운 문제로 줄이기 6.NS.C.7 단계 1

조건을 다시 읽기: $a b > c$ 가 금지.
즉 모든 내부 위치의 항은 양 이웃보다 크거나 (꼭대기) 양 이웃보다 작아야 (골짜기) 합니다.
결국 차의 부호가 번갈아 — 배열은 위-아래-위-아래 혹은 아래-위-아래-위 의 지그재그.

패턴: $a_1 \lessgtr a_2 \gtrless a_3 \lessgtr a_4 \gtrless a_5$

💡 내부 항은 꼭대기 아니면 골짜기 — 연속 세 항이 "한 방향" 으로 가서는 안 됨.

#2 빠짐없이 나열하기 4.OA.B.4 단계 2

더 쉬운 문제 워밍업: $n = 3$.
$\{1, 2, 3\}$ 의 모든 순열 $3! = 6$ 가지를 나열: $123, 132, 213, 231, 312, 321$.
단조 순열 $123, 321$ 이 금지, 유효한 것은 $132, 213, 231, 312$ — $4$ 가지.

Count$_3 = 4$

💡 단조 순열 두 개만 빼고 남은 것 세기.

#2 빠짐없이 나열하기 5.OA.B.3 단계 3

더 쉬운 문제 2단계: $n = 4$.
도구 #16 (대칭): 유효 배열은 "위로 시작" ($a_1 < a_2$) 과 "아래로 시작" ($a_1 > a_2$) 으로 갈리고 부등호를 뒤집으면 짝을 이루므로 두 묶음의 수가 같습니다.
$\{1, 2, 3, 4\}$ 에서 패턴 $a c < d$ 를 체계적으로 나열: $1324, 1423, 2314, 2413, 3412$ — $5$ 가지.
대칭으로 두 배: $10$.

Count$_4 = 2 \cdot 5 = 10$

💡 대칭으로 일거리 절반; 위-아래-위 순열을 첫 항 작은 순으로 나열.

#2 빠짐없이 나열하기 5.OA.B.3 단계 4

같은 대칭을 $n = 5$ 에 적용: 패턴 $a c < d > e$ (위-아래-위-아래) 의 개수를 센 뒤 두 배.
최소 원소 $1$ 의 위치로 분할: $1$ 은 모든 이웃보다 작으므로 골짜기 — 위치 $1, 3, 5$ 만 가능 (위치 $2$ 나 $4$ 는 꼭대기여야 하므로 불가).

$1 \in \{$ 위치 $1, 3, 5\}$

💡 $1$ 은 최솟값 — 골짜기 위치에만 들어갑니다.

#2 빠짐없이 나열하기 5.OA.B.3 단계 5

경우 (b): $1$ 이 위치 3, 패턴 $a 1 < d > e$, $\{a, b, d, e\} = \{2, 3, 4, 5\}$.
제약: $a < b$, $d > e$, $b > 1$ (자동), $d > 1$ (자동).
자유 제약: $\{2,3,4,5\}$ 에서 두 개를 골라 왼쪽 짝 $(a, b)$ 로 ($a < b$, $\binom{4}{2} = 6$ 가지), 나머지가 오른쪽 짝 $(d, e)$ 로 ($d > e$, $1$ 가지).
따라서 $6$ 가지.

경우 (b): $6$ 가지 ($1$ 이 위치 $3$)

💡 $\{2,3,4,5\}$ 를 왼쪽 쌍 (오름) 과 오른쪽 쌍 (내림) 으로 나눔 — $\binom{4}{2}$.

#2 빠짐없이 나열하기 5.OA.B.3 단계 6

경우 (a): $1$ 이 위치 1, 패턴 $1 c < d > e$, $\{b, c, d, e\} = \{2, 3, 4, 5\}$, 내부 골짜기 $c$ ($c < b, c < d$) 는 $c \in \{2, 3\}$.
$c = 2$: $1 2 < d > e$, $\{b, d, e\} = \{3, 4, 5\}$, 꼭대기 $d$ 가능값별로 — $d = 5$: $\{b, e\} = \{3, 4\}$, $b, e$ 자유, $2$ 가지.
$d = 4$: $\{b, e\} = \{3, 5\}$, $e < 4$ 이므로 $e = 3, b = 5$, $1$ 가지.
$d = 3$: $\{b, e\} = \{4, 5\}$, $e < 3$ 불가, $0$.
소계 $c=2$: $3$.
$c = 3$: $1 3 < d > e$, $\{b, d, e\} = \{2, 4, 5\}$, $b > 3, d > 3$ 이므로 $\{b, d\} = \{4, 5\}, e = 2$, $b, d$ 순서 $2$ 가지.
소계 $c=3$: $2$.
경우 (a) 합계: $3 + 2 = 5$.

경우 (a): $5$ 가지 ($1$ 이 위치 $1$)

💡 $1$ 을 고정, 내부 골짜기 $c \in \{2, 3\}$ 로 분기.

#5 패턴 찾기 5.OA.B.3 단계 7

경우 (c): $1$ 이 위치 5, 패턴 $a c < d > 1$.
경우 (a) 와 좌우 대칭 (위치 거꾸로 읽기) 이므로 같은 수: $5$ 가지.
직접 검산: 내부 골짜기 $c \in \{2, 3\}$, 동일한 분기로 $c = 2$ 일 때 $3$, $c = 3$ 일 때 $2$ — 합 $5$.

경우 (c): $5$ 가지 ($1$ 이 위치 $5$)

💡 경우 (a) 의 거울 — 좌우 대칭으로 같은 수.

#16 관점 바꾸기 4.NBT.B.4 단계 8

위-아래-위-아래 (양수 시작) 합계: $5 + 6 + 5 = 16$.
도구 #16 대칭 ($a_i \to 6 - a_i$ 로 모든 위·아래 뒤집기) 으로 아래-위-아래-위 도 $16$.
총 유효 배열: $16 + 16 = 32$.
선택지 (D).

총합 $= 2 \cdot 16 = 32 \Rightarrow \textbf{(D)}$

💡 $a_i$ 를 $6 - a_i$ 로 바꾸면 모든 위가 아래로 — 개수가 두 배.

[1] #9 6.NS.C.7 조건을 다시 읽기: $a b > c$ 가 금지. 즉 모든 내부 위치의 항은 양 이웃보다 크거나 (꼭대기) 양 이웃보

[2] #2 4.OA.B.4 더 쉬운 문제 워밍업: $n = 3$. $\{1, 2, 3\}$ 의 모든 순열 $3! = 6$ 가지를 나열: $123, 132, 213, 231

[3] #2 5.OA.B.3 더 쉬운 문제 2단계: $n = 4$. 도구 #16 (대칭): 유효 배열은 "위로 시작" ($a_1 < a_2$) 과 "아래로 시작" ($a_1

[4] #2 5.OA.B.3 같은 대칭을 $n = 5$ 에 적용: 패턴 $a c < d > e$ (위-아래-위-아래) 의 개수를 센 뒤 두 배. 최소 원소 $1$

[5] #2 5.OA.B.3 경우 (b): $1$ 이 위치 3, 패턴 $a 1 < d > e$, $\{a, b, d, e\} = \{2, 3, 4, 5\}$. 제

[6] #2 5.OA.B.3 경우 (a): $1$ 이 위치 1, 패턴 $1 c < d > e$, $\{b, c, d, e\} = \{2, 3, 4, 5\}$, 내

[7] #5 5.OA.B.3 경우 (c): $1$ 이 위치 5, 패턴 $a c < d > 1$. 경우 (a) 와 좌우 대칭 (위치 거꾸로 읽기) 이므로 같은 수:

[8] #16 4.NBT.B.4 위-아래-위-아래 (양수 시작) 합계: $5 + 6 + 5 = 16$. 도구 #16 대칭 ($a_i \to 6 - a_i$ 로 모든 위·아래 뒤

검토

합리성 확인: 더 쉬운 문제로 검산: $a_3 = 4, a_4 = 10, a_5 = 32$. 비율 $a_5 / a_4 = 3.2$, $a_4 / a_3 = 2.5$ — 제약이 강해지면서 성장이 둔화되는 정상 경향. 또 다른 검산: 잘 알려진 "지그재그" (오일러) 수 $E_n$ 은 $E_3 = 2, E_4 = 5, E_5 = 16$ 이고 $\{1, \dots, n\}$ 의 alternating permutation 수는 $2 E_n$. 대입: $2 \cdot 2 = 4$, $2 \cdot 5 = 10$, $2 \cdot 16 = 32$ — 모두 손계산과 일치. 답 $32 =$ (D) 확정.

대안 접근: 도구 #2 (빠짐없이 나열) 무차별 풀이: $\{1, 2, 3, 4, 5\}$ 의 $120$ 순열을 사전순으로 모두 적고 연속 세 항이 단조인 것을 지워 나갑니다. 시간은 들지만 확실하고, 결과 $32$ 가 위 분할 풀이를 직접 검증합니다.

사용된 CCSS 표준 (최저 학년 6)

6.NS.C.7 유리수의 순서와 절댓값 이해 ("세 항 증가" / "세 항 감소" 를 인접 항 순서 제약으로 읽기.)
4.OA.B.4 모든 인수쌍 찾기, 배수 인식, 소수·합성수 판정 ($\{1, 2, 3\}$ 의 $6$ 순열을 모두 적고 단조 두 개를 빼내는 기초 나열 사고.)
5.OA.B.3 두 규칙으로 두 수 패턴 만들고 관계 식별 (alternating permutation 의 체계적 나열: 최소 원소 위치로 분할, 내부 골짜기 값으로 다시 분할.)
4.NBT.B.4 여러 자릿수 수 능숙하게 더하기 빼기 (부분합 $5 + 6 + 5 = 16$, 두 배 해서 $32$.)

⭐ "연속 세 개가 모두 오르거나 내리면 안 됨" 은 결국 "지그재그여야 함" 이라는 뜻. 최소 원소 $1$ 의 위치 (골짜기 자리: $1, 3, 5$) 로 나눠 세면 $5 + 6 + 5 = 16$, 위·아래 뒤집기 대칭으로 두 배 $\textbf{(D) }32$.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: D

검토

사용된 CCSS 표준 (최저 학년 6)

비슷한 유형 더 풀어보기