AMC 10 · 2021 · #22

학년 7 logic

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

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

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

문제

두 사람이 벽돌 줄을 두고 가져가기 게임을 합니다. 한 차례에 벽돌 하나 또는 이웃한 벽돌 둘을 한 줄에서만 가져가고, 빈 틈이 생기면 줄이 쪼개집니다. 먼저 두는 사람이 있고 마지막 벽돌을 가져간 사람이 이깁니다. 다섯 보기 중에서 나중에 두는 사람이 이기는 시작 배치를 고르세요.

답을 골라 클릭하세요.

(A)

(6,1,1)

(B)

(6,2,1)

(C)

(6,2,2)

(D)

(6,3,1)

(E)

(6,3,2)

풀이 과정

전략 더 쉬운 문제로 줄이기

도구 #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

작은 줄부터 값 매기기

빈 줄부터 값을 매깁니다.

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

2STEP 2

세 개짜리 줄

갈 수 있는 값에 없는 가장 작은 수를 씁니다.

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

3STEP 3

네 개짜리 줄

값이 다시 작아질 수도 있습니다.

G(4) = 1

4STEP 4

다섯 개짜리 줄

같은 방법으로 이어 갑니다.

G(5) = 4

5STEP 5

여섯 개짜리 줄

필요한 마지막 값까지 구합니다.

G(6) = 3

6STEP 6

보기마다 합치기

각 보기의 값을 배타적 합으로 합칩니다.

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

7STEP 7

0이 되는 것 고르기

0이 되는 것은 6, 2, 1입니다.

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