AMC 10 · 2021 · #24

학년 7 arithmetic

유형 Branching State Enumeration └ 세부 유형 Rule-Governed Process Simulation

sprague-grundy-theoremnim-gamerecursive-sequencepattern-recognition easier-related-problempattern-recognitionsystematic-enumeration ↑ 선수 지식: pattern-recognition

📏 긴 풀이 💡 4 개 인사이트 📊 도형

문제

Arjun 과 Beth 가 벽돌 게임을 한다. 각 "벽" 은 연속한 벽돌 묶음이고, 한 차례에 한 벽을 골라 벽돌 한 개 또는 인접한 두 개를 제거 (제거하면 가운데에 틈이 생겨 벽이 작게 쪼개질 수 있음). Arjun 이 먼저, 마지막 벽돌을 가져가는 쪽이 이김. 다섯 후보 시작 배치 (각각 세 벽) 중 두 번째 플레이어 Beth 가 반드시 이기는 배치는?

답을 골라 클릭하세요.

(A)

(6,1,1)

(B)

(6,2,1)

(C)

(6,2,2)

(D)

(6,3,1)

(E)

(6,3,2)

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

풀이 과정

전략 더 쉬운 문제로 줄이기

도구 #9 (더 쉬운 문제) — 크기 1, 2, 3, …, 6 인 단일 벽부터 Grundy 수를 차례로 구함. Sprague-Grundy 정리로 세 벽 합 게임도 자동 결정. 도구 #2 (빠짐없이 나열) — 각 n 에서 가능한 모든 수와 결과 Grundy 값 나열, mex 적용. 도구 #5 (패턴 찾기) — G(n) 이 어떻게 자라는지 관찰. 도구 #7 (쪼개기) — 세 벽 위치 Grundy = 세 벽 Grundy XOR. 도구 #3 (가능성 지우기) — XOR 가 0 인 후보만 P-position.

1STEP 1

작은 벽을 한 수 옵션의 mex 로: G(0)=0, G(1)=1, G(2)=2.

G(0) = 0, G(1) = 1, G(2) = 2

2STEP 2

크기 3: 가운데 벽돌 제거 → (1,1) XOR 0, 옵션 {0,1,2}, G(3)=3.

G(3) = mex{0, 1, 2} = 3

3STEP 3

크기 4: 옵션 {0,2,3} 이 1 을 건너뛰어 mex 가 급락 — G(4)=1.

G(4) = 1

4STEP 4

크기 5: 가운데 제거 → (2,2) XOR 0, 옵션 {0,1,2,3}, G(5)=4.

G(5) = 4

5STEP 5

크기 6: 옵션 {0,1,2,4} 에 3 이 빠져 핵심 벽 값은 G(6)=3.

G(6) = 3

6STEP 6

각 후보의 세 벽에 Sprague-Grundy XOR 적용: A=3, B=0, C=3, D=1, E=2.

G(A) = 3, G(B) = 0, G(C) = 3, G(D) = 1, G(E) = 2

7STEP 7

nim-값 0 인 유일한 P-position 이 후보 B; Arjun 이 뭘 둬도 깨지고 Beth 가 XOR 0 으로 되받아 이긴다.

G(B) = 0 → (B) (6, 2, 1)

정답

(6,2,1)

감각 점검. Grundy 표 G(1..6) = (1, 2, 3, 1, 4, 3) — 게시된 AoPS 풀이의 Sprague-Grundy 값과 일치. (B) (6, 2, 1) 의 XOR = 0 만 P-position 이고 나머지 네 후보는 모두 비-0 — Arjun 이 승리. 또한 다른 풀이의 "대칭 거울" 전략 (Beth 가 Arjun 수에 거울로 응수해 항상 마지막 벽돌 차지) 도 같은 결론.

💡핵심 정리

이 어려운 AMC 10 게임 문제도 사실 7학년 "작은 경우 차근차근 따져보기" 만으로 풀려요 — 크기 1~6 인 단일 벽의 Grundy 수를 mex 로 계산하면 1, 2, 3, 1, 4, 3. 후보 (B) (6, 2, 1) 의 XOR = 3 ⊕ 2 ⊕ 1 = 0 — 이 위치에선 Arjun 이 어떤 수를 둬도 Beth 가 받아칠 수 있어 Beth 필승. 답은 (B).

비슷한 유형 더 풀어보기