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 개 인사이트

문제

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

답을 골라 클릭하세요.

(A)

~10

(B)

~18

(C)

~24

(D)

~32

(E)

~44

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

풀이 과정

전략 더 쉬운 문제로 줄이기

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

1STEP 1

조건을 바꿔 읽으면 내부 항은 꼭대기 아니면 골짜기 — 배열은 지그재그여야 합니다.

패턴: a₁ ≶ a₂ ＞ rless a₃ ≶ a₄ ＞ rless a₅

2STEP 2

n = 3 로 워밍업: 3! = 6 순열 중 단조인 123, 321 만 금지 — 남는 건 4 가지.

Count₃ = 4

3STEP 3

n = 4 는 대칭으로 위·아래 시작을 짝지어, 위-아래-위 나열 5 가지를 두 배 해 10.

Count₄ = 2 · 5 = 10

4STEP 4

n = 5, 패턴 a ＜ b ＞ c ＜ d ＞ e: 1 은 이웃보다 작아 골짜기뿐 — 위치 1, 3, 5.

1 ∈ { 위치 1, 3, 5}

5STEP 5

경우 (b) 1 이 위치 3, 패턴 a ＜ b ＞ 1 ＜ d ＞ e: {2, 3, 4, 5} 를 오름·내림 쌍으로 갈라 6 가지.

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

6STEP 6

경우 (a) 1 이 위치 1, 패턴 1 ＜ b ＞ c ＜ d ＞ e: 내부 골짜기 c ∈ {2, 3} 로 분기해 합 5 가지.

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

7STEP 7

경우 (c) 1 이 위치 5, 패턴 a ＜ b ＞ c ＜ d ＞ 1: 내부 골짜기 c ∈ {2, 3} 로 갈라 합 5 가지.

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

8STEP 8

위-아래-위-아래 합계 5 + 6 + 5 = 16, 대칭으로 아래-위-아래-위 도 16 — 총 32 → (D).

총합 = 2 · 16 = 32 → (D)

정답

~32

더 쉬운 문제로 검산: a₃ = 4, a₄ = 10, a₅ = 32. 비율 a₅ / a₄ = 3.2, a₄ / a₃ = 2.5 — 제약이 강해지면서 성장이 둔화되는 정상 경향. 또 다른 검산: 잘 알려진 "지그재그" (오일러) 수 E_n 은 E₃ = 2, E₄ = 5, E₅ = 16 이고 {1, …, n} 의 alternating permutation 수는 2 E_n. 대입: 2 · 2 = 4, 2 · 5 = 10, 2 · 16 = 32 — 모두 손계산과 일치. 답 32 = (D) 확정.

💡핵심 정리

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

비슷한 유형 더 풀어보기