AMC 10 · 2008 · #21

학년 7 counting

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

permutations-basiccasework systematic-enumeration ↑ 선수 지식: permutations-basic

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

문제

둥근 탁자 둘레에 의자 10개가 일정한 간격으로 놓여 있고, 시계 방향으로 1부터 10까지 번호가 매겨져 있다. 부부 5쌍(남자 5명, 여자 5명)이 남녀가 번갈아 앉도록 자리에 앉는다. 어떤 사람도 자기 배우자의 바로 옆자리에 앉을 수 없고, 배우자의 탁자 건너편 정면 자리에도 앉을 수 없다. 이 규칙을 모두 지키는 자리 배치가 몇 가지인지 센다.

답을 골라 클릭하세요.

(A)

$\ 240$

(B)

$\ 360$

(C)

$\ 480$

(D)

$\ 540$

(E)

$\ 720$

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

풀이 과정

전략 작은 문제로 쪼개기

남자의 규칙과 여자의 규칙이 서로 얽혀 있으므로, 도구 #7(작은 문제로 쪼개기)로 세기를 두 단계로 깔끔하게 나눈다. 먼저 번갈아 앉는 규칙만으로 남자 5명을 앉히고, 그 다음 남자를 고정한 채 아내 5명이 남편의 옆이나 정면을 피해 반대 성별 자리를 채우는 방법을 센다. 도구 #1(그림 그리기)로 기하 구조를 눈에 보이게 만든다. 어떤 의자가 옆이고 어떤 의자가 정면인지 표시하면 각 남자의 금지된 세 자리를 바로 읽어낼 수 있다. 도구 #2(빠짐없이 나열하기)로 각 아내에게 앉을 수 있는 자리가 두 개뿐임을 보이고, 그 선택들이 하나의 고리로 맞물려 여자 배치가 단 두 가지만 살아남음을 확인한다. 남자 경우의 수와 여자 경우의 수를 곱하면 답이 나온다.

1STEP 1

남자 5명 앉히기

남자는 홀수 자리 전부 또는 짝수 자리 전부를 차지하니 2가지, 그 안의 배열은 5! = 120가지, 곱하면 240가지다.

2 × 5! = 2 × 120 = 240

2STEP 2

각 아내가 앉을 수 있는 자리 찾기

남자를 1,3,5,7,9에 고정하면 1의 남자는 2·10·6을 막아 아내 자리가 {4,8}뿐이다. 다른 아내도 두 자리씩만 남는다.

man 1→{4,8}, 3→{6,10}, 5→{8,2}, 7→{10,4}, 9→{2,6}

3STEP 3

아내를 사슬처럼 연결: 두 가지뿐

선택지가 맞물려 아내 1이 4에 앉으면 7→10, 3→6, 9→2, 5→8로 강제되고, 8에 앉으면 거울상이다. 배치는 2가지뿐이다.

{1 → 4,7 → 10,3 → 6,9 → 2,5 → 8} or {1 → 8,5 → 2,9 → 6,3 → 10,7 → 4}

4STEP 4

두 단계를 곱하기

남자 배치 240가지 각각에 아내 배치 2가지가 붙으므로 240 × 2 = 480, 보기 (C)이다.

240 × 2 = 480

정답

480

배우자 규칙이 없다면 번갈아 앉는 배치는 2 × 5! × 5! = 2 × 120 × 120 = 28800가지다. '옆도 안 되고 정면도 안 된다'는 규칙이 여자의 120가지 배열을 단 2가지로 줄여 240 × 2 = 480이 된다. 결과는 양의 정수이고, '여자 때문에 × 2'라는 구조가 예측하는 대로 남자 경우의 수 240의 배수이며, 보기 중 240의 배수는 480뿐이다 — 모두 보기 (C)와 일치한다.

💡핵심 정리

얽힌 자리 세기 문제는 단계로 쪼개서 — 한 무리를 먼저 앉히고, 조건이 다음 무리를 얼마나 좁히는지 세어 — 각 단계의 경우의 수를 곱하면 된다.

남자 5명 앉히기
각 아내가 앉을 수 있는 자리 찾기
아내를 사슬처럼 연결: 두 가지뿐
두 단계를 곱하기

남자 5명 앉히기

각 아내가 앉을 수 있는 자리 찾기

아내를 사슬처럼 연결: 두 가지뿐

두 단계를 곱하기

비슷한 유형 더 풀어보기