AMC 10 · 2024 · #20

학년 7 counting

permutations-basiccombinations-basicsystematic-enumerationpattern-recognition systematic-enumerationcaseworkidentify-subproblems ↑ 선수 지식: permutations-basiccombinations-basicfactorial

📏 중간 풀이 💡 3 개 인사이트

문제

Three different pairs of shoes are placed in a row so that no left shoe is next to a
right shoe from a different pair. In how many ways can these six shoes be lined up?

$\textbf{(A) } 60 \qquad\textbf{(B) } 72 \qquad\textbf{(C) } 90 \qquad\textbf{(D) } 108 \qquad\textbf{(E) } 120$

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

108

(E)

120

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 서로 다른 신발 세 켤레 — $P_1, P_2, P_3$, 각 켤레는 왼쪽 $L_i$ 와 오른쪽 $R_i$ — 를 한 줄 여섯 자리에 배열합니다. 규칙: 서로 다른 켤레의 왼쪽 신발과 오른쪽 신발은 이웃할 수 없다 (즉 $L_i$ 와 $R_j$ 가 인접하려면 반드시 $i = j$). 서로 다른 여섯 신발의 배열 중 규칙을 지키는 것은 몇 가지?

주어진 것: 서로 다른 신발 $6$ 짝: $L_1, R_1, L_2, R_2, L_3, R_3$; 금지: $i \ne j$ 일 때 인접한 $L_i \;\&\; R_j$; 허용: 두 $L$ 인접, 두 $R$ 인접, 또는 짝이 맞는 $L_i R_i$ 인접; 선택지: (A) $60$, (B) $72$, (C) $90$, (D) $108$, (E) $120$

구하는 것: 규칙을 지키는 한 줄 배열의 수

이해

계획

주요 도구: #2 빠짐없이 나열하기

보조 도구: #7 작은 문제로 쪼개기, #9 더 쉬운 문제로 줄이기

신발이 복잡해 보이지만, 규칙이 신경 쓰는 건 $L$ 과 $R$ 사이의 경계뿐 입니다. 도구 #2(빠짐없이 나열하기) 가 두 층 계획을 깔끔히 줍니다: 1층 — $L$ 셋·$R$ 셋의 종류 문자열 중 금지 경계가 없는 것들을 빠짐없이 나열, 2층 — 살아남은 각 문자열에 대해 $L$ 들을 $L_1, L_2, L_3$, $R$ 들을 $R_1, R_2, R_3$ 로 이름 붙이되 모든 $L$-$R$ 경계가 짝이 맞는 쌍이 되도록 세기. 도구 #7(작은 문제로 쪼개기) 가 종류 문자열을 블록 모양 네 부류로 나눠 줍니다. 도구 #9(더 쉬운 문제로 줄이기) 가 이름 붙이기 층을 부류별 작은 순열 수로 줄여 줍니다.

실행 — 정답: A

#7 작은 문제로 쪼개기 5.OA.A.2 단계 1

규칙을 $L/R$ 종류 문자열 위로 옮깁니다.
종류 문자열에서 $L$ 바로 뒤에 $R$ 이 (또는 그 반대로) 오는 곳을 "경계" 라 하면, 그 두 신발은 반드시 어떤 공통 $i$ 에 대해 짝이 맞는 $L_i, R_i$.
즉시 따라오는 결과: 종류 부분 문자열 $LRL$ (또는 $RLR$) 은 불가능 — 가운데 신발이 서로 다른 경계 짝의 동반자 $R_i$ 와 $R_j$ 가 동시에 될 수 없기 때문 (한 신발이 두 자리에 있을 수는 없음).

$$\text{경계 } L_i R_j \;\Rightarrow\; i = j; \quad LRL, RLR \;\text{는 종류 부분 문자열로 금지}$$

💡 신발에서 이름을 떼고 $L/R$ 골격만 보면, 금지 인접 규칙이 짧은 문자열 위의 깔끔한 규칙이 됩니다.

#2 빠짐없이 나열하기 7.SP.C.8 단계 2

$L$ 셋·$R$ 셋 종류 문자열 중 $LRL$, $RLR$ 부분 문자열이 없는 것을 모두 나열.
허용되는 문자열은 연속 블록 모양이 $\{3, 3\}$ 인 경우, $L,R,L$ 또는 $R,L,R$ 순으로 블록 세 개인 경우, $L,R,L,R$ 또는 $R,L,R,L$ 순으로 블록 네 개($\{1,2,2,1\}$)인 경우.
블록 모양별 나열: $LLLRRR, RRRLLL$ (경계 $1$개 짜리 $2$개); $LLRRRL, LRRRLL, RLLLRR, RRLLLR$ (경계 $2$개 짜리 $4$개); $LRRLLR, RLLRRL$ (경계 $3$개 짜리 $2$개).
총 $8$개의 유효 종류 문자열.

$$\text{유효 종류 문자열} = \{LLLRRR, RRRLLL, LLRRRL, LRRRLL, RLLLRR, RRLLLR, LRRLLR, RLLRRL\}$$

💡 블록 모양 기준 체계적 나열은 누락과 중복을 모두 막아 줍니다 — $LRL/RLR$ 금지와 양립하는 네 모양뿐.

#9 더 쉬운 문제로 줄이기 4.OA.A.3 단계 3

쪼개기 A — 경계 $1$개 ($LLLRRR, RRRLLL$).
$LLLRRR$ 의 경우 자리 $(3, 4)$ 가 유일 경계로 짝이 맞는 쌍 $L_a R_a$, $a$ 선택 $3$ 가지.
나머지 두 $L$ 은 자리 $1, 2$ 에 $2! = 2$ 순으로, 나머지 두 $R$ 은 자리 $5, 6$ 에 $2! = 2$ 순으로.
한 문자열당 $3 \cdot 2 \cdot 2 = 12$, 대칭으로 $RRRLLL$ 도 $12$.
부분합 $24$.

$$3 \cdot 2! \cdot 2! = 12 \;\text{각각}, \quad \text{부분합} = 12 + 12 = 24$$

💡 경계의 짝을 정하고 나면 양쪽이 독립적인 작은 줄 세우기 — 도구 #9 의 "작은 조각으로 줄이기".

#9 더 쉬운 문제로 줄이기 7.SP.C.8 단계 4

쪼개기 B — 경계 $2$개 ($LLRRRL, LRRRLL, RLLLRR, RRLLLR$).
$LLRRRL$ 의 경우 자리 $(2,3)$ 과 $(5,6)$ 두 경계 각각이 짝이 맞는 쌍이고, 두 쌍은 서로 달라야 함 (한 신발은 두 자리에 못 옴).
서로 다른 두 쌍의 순서 있는 선택 $3 \cdot 2 = 6$.
한 번 — 예: $(L_1, R_1)$ 가 $(2,3)$, $(R_2, L_2)$ 가 $(5,6)$ — 정하면 자리 $1$ 은 남은 $L_3$, 자리 $4$ 는 남은 $R_3$ 로 완전히 강제됨.
한 문자열당 $6$, 부분합 $4 \cdot 6 = 24$.

$$P(3, 2) = 6 \;\text{각각}, \quad \text{부분합} = 4 \cdot 6 = 24$$

💡 경계가 두 개면 각 경계가 짝 하나를 "고정", 세 번째 쌍이 들어갈 자리는 자동 결정.

#9 더 쉬운 문제로 줄이기 4.OA.A.3 단계 5

쪼개기 C — 경계 $3$개 ($LRRLLR, RLLRRL$).
$LRRLLR$ 의 경우 자리 $(1,2), (3,4), (5,6)$ 세 경계 각각이 짝이 맞는 쌍이고, 세 쌍은 $\{P_1, P_2, P_3\}$ 의 순열.
$3! = 6$ 가지, 내부 같은 종류 인접 (예: $R_1 R_2$, $L_2 L_3$) 은 모두 허용.
한 문자열당 $6$, 부분합 $2 \cdot 6 = 12$.

$$3! = 6 \;\text{각각}, \quad \text{부분합} = 2 \cdot 6 = 12$$

💡 경계 세 개 — 각 경계가 한 쌍을 쓰고 세 쌍이 순서대로 들어가므로 $3! = 6$.

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

세 부분합을 더합니다.

$$\text{전체} = 24 + 24 + 12 = 60 \;\Rightarrow\; \textbf{(A)}$$

💡 서로 배반인 세 부분합 더하기 — 4학년 여러 자리 덧셈. (한 배열은 유일한 $L/R$ 종류 문자열을 갖기 때문에 배반.)

[1] #7 5.OA.A.2 규칙을 $L/R$ 종류 문자열 위로 옮깁니다. 종류 문자열에서 $L$ 바로 뒤에 $R$ 이 (또는 그 반대로) 오는 곳을 "경계" 라 하면, 그

[2] #2 7.SP.C.8 $L$ 셋·$R$ 셋 종류 문자열 중 $LRL$, $RLR$ 부분 문자열이 없는 것을 모두 나열. 허용되는 문자열은 연속 블록 모양이 ${3,

[3] #9 4.OA.A.3 쪼개기 A — 경계 $1$개 ($LLLRRR, RRRLLL$). $LLLRRR$ 의 경우 자리 $(3, 4)$ 가 유일 경계로 짝이 맞는 쌍 $

[4] #9 7.SP.C.8 쪼개기 B — 경계 $2$개 ($LLRRRL, LRRRLL, RLLLRR, RRLLLR$). $LLRRRL$ 의 경우 자리 $(2,3)$ 과 $

[5] #9 4.OA.A.3 쪼개기 C — 경계 $3$개 ($LRRLLR, RLLRRL$). $LRRLLR$ 의 경우 자리 $(1,2), (3,4), (5,6)$ 세 경계

[6] #2 4.NBT.B.4 세 부분합을 더합니다.

검토

합리성 확인: 다른 길로 교차 확인. $8$ 개의 유효 종류 문자열을 경계 수 $1, 2, 3$ 의 세 부류로 나눴고, 문자열당 값 $12, 6, 6$ 은 경계 수에만 의존합니다 — $12 = 3 \cdot (2!)^2$ (경계 1), $6 = 3 \cdot 2$ (경계 2, 서로 다른 두 쌍의 순서 있는 선택), $6 = 3!$ (경계 3). 합산: $2 \cdot 12 + 4 \cdot 6 + 2 \cdot 6 = 24 + 24 + 12 = 60$. 무제약 전체 $6! = 720$ 보다 훨씬 작아 인접 제약이 실제로 강하게 작용함과 부합. 답 (A) $= 60$.

대안 접근: 도구 #16(관점 바꾸기 / 여사건). 한 줄을 $L$-블록과 $R$-블록 사이의 이동 시퀀스로 보고, 무제약 $6! = 720$ 에서 금지 경계 (각 $5$ 자리에서 $L_i$ 와 $i \ne j$ 인 $R_j$ 가 이웃하는 경우) 를 포함-배제로 빼도 $60$ 이 나옵니다. 위의 경우 나눔이 더 빠르지만 여사건 시각은 든든한 교차 검증입니다.

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

5.OA.A.2 수의 계산을 기록하는 식 쓰기 (규칙을 $L/R$ 종류 문자열 위로 옮겨 "모든 $L$-$R$ 경계는 짝이 맞는 쌍 $L_i R_i$" 로 정리.)
7.SP.C.8 정리된 목록·표·시뮬레이션을 이용한 복합 사건의 경우의 수 ($L$ 셋·$R$ 셋 종류 문자열 중 $LRL$, $RLR$ 이 없는 유효 문자열 $8$ 개를 빠짐없이 나열하고, 경계 2개 부류에서 $P(3, 2) = 6$ 으로 경계 쌍을 선택.)
4.OA.A.3 사칙연산을 이용한 자연수 다단계 문장제 풀기 (경계 1개 문자열당 $3 \cdot 2! \cdot 2! = 12$, 경계 3개 문자열당 $3! = 6$ 의 곱셈.)
4.NBT.B.4 여러 자리 자연수의 덧셈·뺄셈 (세 부류 부분합 $24 + 24 + 12 = 60$ 을 더하는 데 사용.)

⭐ 이 AMC 10 문제는 7학년의 정리된 세기 — 모든 유효 $L/R$ 골격을 나열하고, 경계마다 이름 붙이는 가짓수를 세서 더하기 — 만 알면 풀려요. 답은 $60$!

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: A

검토

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

비슷한 유형 더 풀어보기