AMC 10 · 2013 · #24

학년 8 counting

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

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

📏 긴 풀이 💡 4 개 인사이트

문제

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

답을 골라 클릭하세요.

(A)

540

(B)

600

(C)

720

(D)

810

(E)

900

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

풀이 과정

전략 빠짐없이 나열하기

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

1STEP 1

한 라운드는 일대일 짝짓기

18경기가 세 경기씩 여섯 라운드를 꽉 채우니 한 라운드는 A,B,C와 X,Y,Z의 짝짓기 — 3! = 6가지다.

3 × 3 × 2 = 18 = 6 × 3, #라운드-유형 = 3! = 6

2STEP 2

개수에 이름 붙이기

여섯 짝짓기를 π₁,…,π₆(π₁은 항등)이라 하고 π_i를 쓰는 라운드 수를 n_i라 하면 n₁ + … + n₆ = 6이다.

n_i ≥ 0, Σ_i=1⁶ n_i = 6

3STEP 3

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

각 상대 짝은 정확히 두 짝짓기에 들어 있으므로 3 × 3 표의 아홉 칸이 n₁ + n₂ = 2 꼴의 식 아홉 개를 준다.

n₁+n₂ = 2, n₁+n₃ = 2, n₁+n₄ = 2, n₄+n₅ = 2, …

4STEP 4

연립방정식 풀기

t = n₁이라 두면 n₂ = n₃ = n₄ = 2 - t, n₅ = n₆ = t로 정해지고, 개수가 0~2이므로 t = 0, 1, 2뿐이다.

(n₁,…,n₆) = (t, 2-t, 2-t, 2-t, t, t), t ∈ {0,1,2}

5STEP 5

세 유형 나열

t=1은 여섯 짝짓기를 한 번씩, t=0은 세 맞바꿈을, t=2는 항등과 두 회전을 두 번씩 쓴다. 셋 다 합법이다.

t=1:{π₁,…,π₆}; t=0:{π₂²,π₃²,π₄²}; t=2:{π₁²,π₅²,π₆²}

6STEP 6

서로 다른 유형의 순서 세기

라운드에 순서가 있으니 t=1의 서로 다른 여섯 라운드는 6! = 720가지로 배열된다.

6! = 720

7STEP 7

겹치는 유형의 순서 세기

겹치는 유형은 같은 라운드가 세 쌍이라 6!/2! 2! 2! = 90가지씩이다.

6!/2! 2! 2! = 720/8 = 90

8STEP 8

유형별 합산

세 유형은 겹치지 않으므로 더하면 720 + 90 + 90 = 900, 선택지 (E)이다.

720 + 90 + 90 = 900 → (E)

정답

900

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

💡핵심 정리

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

한 라운드는 일대일 짝짓기
개수에 이름 붙이기
"각각 두 번"을 방정식으로
연립방정식 풀기
세 유형 나열
서로 다른 유형의 순서 세기
겹치는 유형의 순서 세기
유형별 합산