AMC 10 · 2013 · #24

학년 8 counting

유형 Branching State Enumeration └ 세부 유형 Ordered Placement Count

permutations-basiccaseworkcombinatorial-identity caseworksystematic-enumeration ↑ 선수 지식: permutations-basic

📏 긴 풀이 💡 4 개 인사이트

문제

센트럴 고등학교가 노던 고등학교와 백개먼 경기를 겨룬다. 각 학교에는 세 명의 선수가 있으며, 경기 규칙에 따라 각 선수는 상대 학교의 각 선수와 두 경기씩 치러야 한다. 경기는 여섯 라운드로 진행되며, 각 라운드에서는 세 경기가 동시에 진행된다. 이 경기를 편성하는 서로 다른 방법은 몇 가지인가?

답을 골라 클릭하세요.

(A)

540

(B)

600

(C)

720

(D)

810

(E)

900

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 두 학교가 각각 세 명의 선수를 낸다. 센트럴 팀을 $A,B,C$, 노던 팀을 $X,Y,Z$라 하자. 모든 선수는 상대 팀의 각 선수와 두 번씩 경기해야 한다. 전체 경기는 여섯 라운드로 진행되고, 한 라운드마다 세 경기가 동시에 열린다. 여섯 라운드를 짜는 서로 다른 일정의 수를 구하라.

주어진 것: 센트럴 선수 $A,B,C$, 노던 선수 $X,Y,Z$; 상대 팀과의 각 짝(예: $A$ 대 $X$)은 정확히 두 번 경기한다; 경기는 순서가 있는 여섯 라운드(1라운드, 2라운드, ...)로 진행된다; 한 라운드에는 정확히 세 경기가 동시에 열린다; 선택지: (A) $540$, (B) $600$, (C) $720$, (D) $810$, (E) $900$

구하는 것: 여섯 라운드를 짜는 서로 다른 일정의 수

이해

계획

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

보조 도구: #4 변수 도입하기, #15 다르게 정리하기, #7 작은 문제로 쪼개기

"몇 가지 방법"을 묻는 세는 문제이므로 도구 #2(빠짐없이 나열하기)로 목표를 잡는다: 여섯 라운드를 만드는 모든 합법적인 방법을 나열한다. 핵심은 한 라운드를 $\{A,B,C\}$에 대한 $\{X,Y,Z\}$의 순열 하나로 보는 것이다(선수는 라운드마다 한 번씩만 경기한다). 그런 뒤 도구 #4(변수 도입하기)로 순열 $\pi$를 쓰는 라운드 수를 $n_\pi$로 둔다. 도구 #15(다르게 정리하기)는 "각 짝이 두 번"이라는 조건을 $3\times 3$ 표의 개수 조건으로 바꾸고, 이는 작은 일차 연립방정식이 된다. 이를 풀면(도구 #7, 작은 문제로 쪼개기: 먼저 합법적인 라운드 묶음을 찾고 그다음 각각의 배열 수를 센다) 오직 세 가지 유형만 남고, 답은 그들이 만드는 순서 있는 일정의 총수이다.

실행 — 정답: E

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

한 라운드는 일대일 짝짓기

경기 수를 센다: 각 센트럴 선수는 세 명의 노던 선수와 두 번씩 하므로 $3 \times 3 \times 2 = 18$경기다.
세 경기씩 여섯 라운드도 $18$이므로 어느 라운드에도 쉬는 선수가 없다.
세 경기가 동시에 열리고 팀당 세 명이므로, 각 선수는 한 라운드에 정확히 한 경기만 한다.
따라서 한 라운드는 $\{A,B,C\}$와 $\{X,Y,Z\}$의 완전한 짝짓기 — 순열이다.
가능한 라운드는 $3! = 6$가지다.

$$3 \times 3 \times 2 = 18 = 6 \times 3, \qquad \#\text{라운드-유형} = 3! = 6$$

💡 누구도 두 판을 동시에 둘 수 없으니, 한 라운드는 모든 선수를 상대 한 명과 짝지을 뿐 — 상대를 뒤섞은 것이다.

#4 변수 도입하기 6.EE.B.6 단계 2

개수에 이름 붙이기

가능한 여섯 짝짓기(순열)를 $\pi_1,\dots,\pi_6$이라 하고, $\pi_1$을 항등 짝짓기 $A\!-\!X, B\!-\!Y, C\!-\!Z$로 두자.
여섯 라운드 중 짝짓기 $\pi_i$를 쓰는 라운드 수를 $n_i \ge 0$이라 하면 $n_1 + \cdots + n_6 = 6$이다.
일정은 아홉 개의 상대 짝을 각각 정확히 두 번씩 나오게 해야 한다.

$$n_i \ge 0,\quad \sum_{i=1}^{6} n_i = 6$$

💡 긴 수열을 좇는 대신, 여섯 짝짓기 유형이 각각 몇 번 쓰이는지만 센다.

#15 다르게 정리하기 8.EE.C.8 단계 3

"각각 두 번"을 방정식으로

각 상대 짝에 대해, 그 짝을 포함하는 짝짓기들의 $n_i$를 더하면 $2$가 되어야 한다.
예를 들어 $A\!-\!X$는 항등 $\pi_1$과 $Y,Z$만 뒤바꾸는 짝짓기에 들어 있으므로 $n_1 + n_2 = 2$이다.
$3\times 3$ 상대 표의 아홉 칸을 이렇게 읽으면 $n_1+n_3=2$, $n_1+n_4=2$, $n_4+n_5=2$ 등 아홉 개의 방정식이 나온다.

$$n_1+n_2 = 2,\ \ n_1+n_3 = 2,\ \ n_1+n_4 = 2,\ \ n_4+n_5 = 2,\ \dots$$

💡 $3\times 3$ 격자의 각 칸이 정확히 두 번 방문되어야 하고, 이는 칸마다 일차방정식 하나일 뿐이다.

#7 작은 문제로 쪼개기 8.EE.C.8 단계 4

연립방정식 풀기

$t = n_1$(항등 라운드의 수)이라 두자.
방정식을 대입해 나가면 모든 개수가 정해진다: $n_2 = n_3 = n_4 = 2 - t$, $n_5 = n_6 = t$.
모든 개수는 $0$ 이상 $2$ 이하여야 하므로 가능한 값은 $t = 0, 1, 2$뿐이다.
따라서 합법적인 라운드 묶음은 정확히 세 유형이다.

$$(n_1,\dots,n_6) = (t,\,2-t,\,2-t,\,2-t,\,t,\,t),\qquad t \in \{0,1,2\}$$

💡 자유롭게 고를 값 하나(순수 항등 라운드 수)가 나머지를 모두 정하고, 그 값은 $0,1,2$뿐이다.

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

세 유형 나열

각 경우를 읽어낸다.
$t=1$: 여섯 짝짓기를 각각 한 번씩 쓴다(여섯 개의 서로 다른 라운드).
$t=0$: 세 개의 "맞바꿈" 짝짓기(호환)를 각각 두 번 쓰고 나머지는 안 쓴다.
$t=2$: 항등과 두 개의 "회전" 짝짓기($3$-순환)를 각각 두 번 쓴다.
세 유형 모두 상대 짝을 정확히 두 번씩 덮으므로 셋 다 합법이다.

$$t{=}1:\{\pi_1,\dots,\pi_6\};\quad t{=}0:\{\pi_2^2,\pi_3^2,\pi_4^2\};\quad t{=}2:\{\pi_1^2,\pi_5^2,\pi_6^2\}$$

💡 여섯 짝짓기를 한 번씩 쓰거나, 세 맞바꿈을 두 번씩, 또는 항등과 두 회전을 두 번씩 쓰는 것이다.

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

서로 다른 유형의 순서 세기

라운드는 순서대로 진행되므로 일정은 여섯 라운드의 순서 있는 배열이다.
$t=1$ 유형에서는 여섯 라운드가 모두 다르므로 순서의 수는 $6!$이다.

$$6! = 720$$

💡 서로 다른 여섯 라운드를 1라운드부터 6라운드까지 $6!$가지로 배치할 수 있다.

#7 작은 문제로 쪼개기 6.NS.B.2 단계 7

겹치는 유형의 순서 세기

$t=0$ 유형(및 $t=2$)에서는 세 짝짓기가 각각 두 번씩 나오므로 여섯 라운드가 똑같은 세 쌍을 이룬다.
서로 다른 순서의 수는 $6!$을 반복되는 짝짓기마다 $2!$로 나눈 값이다: $\frac{6!}{2!\,2!\,2!} = \frac{720}{8} = 90$.
겹치는 두 유형 모두 각각 $90$가지다.

$$\dfrac{6!}{2!\,2!\,2!} = \dfrac{720}{8} = 90$$

💡 똑같은 두 라운드는 자리를 바꿔도 새 일정이 아니므로, 반복되는 짝짓기마다 $2!$로 나눈다.

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

유형별 합산

전체 일정 수 $= 720$(모두 다름) $+ 90$($t=0$) $+ 90$($t=2$) $= 900$.
이는 선택지 (E)이다.

$$720 + 90 + 90 = 900 \;\Rightarrow\; \textbf{(E)}$$

💡 세 합법 유형은 서로 겹치지 않으므로 각 순서-개수를 그냥 더한다.

[1] #7 4.OA.A.3 경기 수를 센다: 각 센트럴 선수는 세 명의 노던 선수와 두 번씩 하므로 $3 \times 3 \times 2 = 18$경기다. 세 경기씩 여섯

[2] #4 6.EE.B.6 가능한 여섯 짝짓기(순열)를 $\pi_1,\dots,\pi_6$이라 하고, $\pi_1$을 항등 짝짓기 $A\!-\!X, B\!-\!Y, C\!

[3] #15 8.EE.C.8 각 상대 짝에 대해, 그 짝을 포함하는 짝짓기들의 $n_i$를 더하면 $2$가 되어야 한다. 예를 들어 $A\!-\!X$는 항등 $\pi_1$과

[4] #7 8.EE.C.8 $t = n_1$(항등 라운드의 수)이라 두자. 방정식을 대입해 나가면 모든 개수가 정해진다: $n_2 = n_3 = n_4 = 2 - t$,

[5] #2 7.SP.C.8 각 경우를 읽어낸다. $t=1$: 여섯 짝짓기를 각각 한 번씩 쓴다(여섯 개의 서로 다른 라운드). $t=0$: 세 개의 "맞바꿈" 짝짓기(호환

[6] #2 7.SP.C.8 라운드는 순서대로 진행되므로 일정은 여섯 라운드의 순서 있는 배열이다. $t=1$ 유형에서는 여섯 라운드가 모두 다르므로 순서의 수는 $6!$이

[7] #7 6.NS.B.2 $t=0$ 유형(및 $t=2$)에서는 세 짝짓기가 각각 두 번씩 나오므로 여섯 라운드가 똑같은 세 쌍을 이룬다. 서로 다른 순서의 수는 $6!$

[8] #7 5.OA.A.1 전체 일정 수 $= 720$(모두 다름) $+ 90$($t=0$) $+ 90$($t=2$) $= 900$. 이는 선택지 (E)이다.

검토

합리성 확인: 세 유형은 서로 다른 짝짓기 묶음을 쓰므로 진짜로 겹치지 않고, 따라서 더하는 것이 옳으며, 각 유형이 아홉 개의 상대 짝을 정확히 두 번씩 덮음을 확인했다. 모두 다른 경우의 수 $6! = 720$은 이미 선택지 (C)와 같은데, 이는 두 개의 "겹치는" 일정을 잊은 사람을 위한 함정 답이다. 올바른 총수는 두 개의 $90$을 더해 $900$에 이른다. 간단한 하한 점검: 여섯 개가 모두 다른 경우는 여러 유형 중 하나뿐이므로 일정은 $720$보다 많아야 하고, $900$은 우리의 정확한 계산이 내놓는 값 중 $720$을 넘는 가장 작은 선택지다. 모두 $900$을 가리킨다.

대안 접근: 선수를 한 명씩 상대 배정하기(도구 #7, 작은 문제로 쪼개기). 선수 $A$의 여섯 상대는 여섯 라운드에 걸쳐 $\frac{6!}{2!\,2!\,2!} = 90$가지 서로 다른 순서로 배열할 수 있다. $A$의 일정이 정해지면, 어느 라운드에서도 $C$에게 충돌이 생기지 않도록 $B$를 채우는 방법을 센다. 그 안쪽 개수를 곱하면 총합이 $90 \times 10 = 900$이 된다. 선수별 방법도 같은 (E)에 도달하여 순열 행렬 계산을 확인해 준다.

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

4.OA.A.3 Solve multi-step word problems using four operations with whole numbers (총 $18$경기를 세고 각 라운드가 모든 선수가 한 번씩 뛰는 일대일 짝짓기임을 이끌어내는 데 사용.)
6.EE.B.6 Use variables to represent numbers and write expressions to solve problems (여섯 짝짓기 유형 각각을 쓰는 라운드 수를 개수 $n_i$로 도입하는 데 사용.)
8.EE.C.8 Analyze and solve pairs of simultaneous linear equations ("각 짝이 두 번 나온다"는 아홉 조건을 일차 연립방정식으로 쓰고 하나의 매개변수 $t \in \{0,1,2\}$까지 푸는 데 사용.)
7.SP.C.8 Find probabilities of compound events using organized lists, tables, and simulation (합법적인 세 라운드-묶음 유형을 나열하고 모두 다른 유형의 $6!$ 순서를 세는 데 사용.)
6.NS.B.2 Fluently divide multi-digit numbers using the standard algorithm ($6! = 720$을 $2!\,2!\,2! = 8$로 나눠 겹치는 각 유형의 $90$ 순서를 얻는 데 사용.)
5.OA.A.1 Use parentheses, brackets, or braces in numerical expressions and evaluate (세 유형의 개수 $720 + 90 + 90$을 더해 최종 총수 $900$을 얻는 데 사용.)

⭐ 한 라운드를 두 팀을 짝짓는 완전한 뒤섞기 하나로 보고, 모든 대결이 두 번씩 일어나게 하면 일정 유형은 셋뿐이다: 서로 다른 여섯 뒤섞기($720$가지 순서) 또는 두 종류의 겹치는 유형(각 $90$가지)이라, $720 + 90 + 90 = 900$이 된다.