경시 · AMC 대비 · 4단계 중 4

AMC 10 · 2021A · #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)

(B)

(C)

(D)

(E)

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으로 워밍업하기

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

Count₃ = 4

3STEP 3

n = 4 세어 보기

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

Count₄ = 2 · 5 = 10

4STEP 4

1의 위치로 n = 5 나누기

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

1 ∈ { 위치 1, 3, 5}

5STEP 5

경우 a 세기

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

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

6STEP 6

경우 b 세기

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

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

7STEP 7

경우 c 세기

경우 (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)

정답

더 쉬운 문제로 검산: 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.

금지된 모양 다시 쓰기
n = 3으로 워밍업하기
n = 4 세어 보기
1의 위치로 n = 5 나누기
경우 b 세기
경우 a 세기
경우 c 세기
더하고 대칭으로 두 배 하기

가족의 부모 대시보드는 sensimlab.com에 있습니다.