AMC 10 · 2021 · #24

학년 7 arithmetic

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

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

문제

Arjun and Beth play a game in which they take turns removing one brick or two adjacent bricks from one "wall" among a set of several walls of bricks, with gaps possibly creating new walls. The walls are one brick tall. For example, a set of walls of sizes $4$ and $2$ can be changed into any of the following by one move: $(3,2),(2,1,2),(4),(4,1),(2,2),$ or $(1,1,2).$

Arjun plays first, and the player who removes the last brick wins. For which starting configuration is there a strategy that guarantees a win for Beth?

$\textbf{(A) }(6,1,1) \qquad \textbf{(B) }(6,2,1) \qquad \textbf{(C) }(6,2,2)\qquad \textbf{(D) }(6,3,1) \qquad \textbf{(E) }(6,3,2)$

답을 골라 클릭하세요.

(A)

(6,1,1)

(B)

(6,2,1)

(C)

(6,2,2)

(D)

(6,3,1)

(E)

(6,3,2)

보기 방식:

도구 + CCSS 풀이

이해

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

주어진 것: 두 플레이어, Arjun 먼저, 교대 진행; 각 차례: 벽 하나에서 벽돌 $1$ 개 또는 인접한 $2$ 개 제거; 제거 후 생기는 틈으로 벽이 더 작은 벽들로 쪼개질 수 있음; 마지막 벽돌을 가져간 쪽이 이김; 후보: (A) $(6,1,1)$, (B) $(6,2,1)$, (C) $(6,2,2)$, (D) $(6,3,1)$, (E) $(6,3,2)$ — 모두 세 벽 구성

구하는 것: Beth (두 번째 플레이어) 가 필승인 시작 배치 (P-position)

이해

계획

주요 도구: #9 더 쉬운 문제로 줄이기

보조 도구: #5 패턴 찾기, #2 빠짐없이 나열하기, #7 작은 문제로 쪼개기, #3 가능성 지우기

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

실행 — 정답: B

#9 더 쉬운 문제로 줄이기 7.NS.A.3 단계 1

작은 벽의 Grundy 수.
$G(0) = 0$ (수 없음, 직전 플레이어 승).
벽 크기 $1$: 한 수 후 빈 상태 (G $0$), 옵션 $\{0\}$, $G(1) = \text{mex}\{0\} = 1$.
벽 크기 $2$: 벽돌 $1$ 개 제거 $\to$ 벽 $(1)$ G $1$; 인접 $2$ 제거 $\to$ 빈, G $0$.
옵션 $\{0, 1\}$, $G(2) = 2$.

$$G(0) = 0,\; G(1) = 1,\; G(2) = 2$$

💡 작은 벽부터 G 값을 쌓아 올림. 새 G = 옵션 집합에 없는 가장 작은 비음정수.

#2 빠짐없이 나열하기 7.NS.A.3 단계 2

벽 크기 $3$.
수: 끝 벽돌 (1번이나 3번) 제거 $\to (2)$ G $2$; 가운데 (2번) 제거 $\to (1, 1)$ G $1 \oplus 1 = 0$; 인접 $2$ 제거 (1-2 또는 2-3) $\to (1)$ G $1$.
옵션 $\{0, 1, 2\}$, $G(3) = 3$.

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

💡 $3$ 벽 가운데 벽돌을 빼면 $(1, 1)$ 으로 갈라져 G 가 $0$ 이 된다.

#2 빠짐없이 나열하기 7.NS.A.3 단계 3

벽 크기 $4$.
수: 끝 벽돌 제거 $\to (3)$ G $3$; 2번 또는 3번 벽돌 제거 $\to (1, 2)$ 또는 $(2, 1)$, G $1 \oplus 2 = 3$; 인접 $2$ 끝 (1-2 또는 3-4) $\to (2)$ G $2$; 인접 $2$ 가운데 (2-3) $\to (1, 1)$ G $0$.
옵션 $\{0, 2, 3\}$, $G(4) = \text{mex}\{0, 2, 3\} = 1$.

$$G(4) = 1$$

💡 $n = 4$ 에서 mex 가 갑자기 $1$ 로 떨어짐 — 옵션이 $1$ 을 건너뜀.

#2 빠짐없이 나열하기 7.NS.A.3 단계 4

벽 크기 $5$.
수 결과 G 값들: $(4)$ G $1$; $(1, 3)$ G $1 \oplus 3 = 2$; $(2, 2)$ G $0$; $(3, 1)$ G $2$; $(3)$ G $3$; $(1, 2)$ G $3$; $(2, 1)$ G $3$.
옵션 $\{0, 1, 2, 3\}$, $G(5) = 4$.

$$G(5) = 4$$

💡 가운데 벽돌 제거 $\to (2, 2)$ G $0$ — mover 의 강한 방어 수.

#2 빠짐없이 나열하기 7.NS.A.3 단계 5

벽 크기 $6$.
수 결과 G 값들: 끝 벽돌 $\to (5)$ G $4$; 2번 또는 5번 $\to (1, 4)$ G $1 \oplus 1 = 0$; 3번 또는 4번 $\to (2, 3)$ G $2 \oplus 3 = 1$; 인접 $2$ 끝 $\to (4)$ G $1$; 인접 $2$ 위치 2-3 또는 4-5 $\to (1, 3)$ 또는 $(3, 1)$ G $1 \oplus 3 = 2$; 인접 $2$ 가운데 3-4 $\to (2, 2)$ G $0$.
옵션 $\{0, 1, 2, 4\}$, $G(6) = \text{mex}\{0, 1, 2, 4\} = 3$.

$$G(6) = 3$$

💡 $\{0, 1, 2, 4\}$ 에서 $3$ 이 빠져 있어 mex $= 3$.

#7 작은 문제로 쪼개기 7.NS.A.3 단계 6

Sprague-Grundy XOR 적용.
세 벽 위치의 Grundy 수 = $G(w_1) \oplus G(w_2) \oplus G(w_3)$.
(A) $(6, 1, 1)$: $3 \oplus 1 \oplus 1 = 3$.
(B) $(6, 2, 1)$: $3 \oplus 2 \oplus 1 = 0$.
(C) $(6, 2, 2)$: $3 \oplus 2 \oplus 2 = 3$.
(D) $(6, 3, 1)$: $3 \oplus 3 \oplus 1 = 1$.
(E) $(6, 3, 2)$: $3 \oplus 3 \oplus 2 = 2$.

$$G(\text{A}) = 3,\; G(\text{B}) = 0,\; G(\text{C}) = 3,\; G(\text{D}) = 1,\; G(\text{E}) = 2$$

💡 독립 벽 = 독립 Nim 더미. XOR 로 합쳐짐.

#3 가능성 지우기 7.NS.A.3 단계 7

P-position (다음 플레이어 패) 는 Grundy 가 $0$.
유일한 G $= 0$ 후보는 (B) $(6, 2, 1)$.
Arjun 이 첫 수를 두면 그 결과의 Grundy 값이 반드시 $\neq 0$ 이 되어 Beth 가 다음 수로 다시 $0$ 으로 되돌릴 수 있음.
따라서 Beth 필승.

$$G(\text{B}) = 0 \Rightarrow \textbf{(B)} \;(6, 2, 1)$$

💡 Grundy $0$ = mover 가 막혔다는 뜻 — 모든 수가 상대에게 유리한 비-$0$ 위치 제공.

[1] #9 7.NS.A.3 작은 벽의 Grundy 수. $G(0) = 0$ (수 없음, 직전 플레이어 승). 벽 크기 $1$: 한 수 후 빈 상태 (G $0$), 옵션 $

[2] #2 7.NS.A.3 벽 크기 $3$. 수: 끝 벽돌 (1번이나 3번) 제거 $\to (2)$ G $2$; 가운데 (2번) 제거 $\to (1, 1)$ G $1 \o

[3] #2 7.NS.A.3 벽 크기 $4$. 수: 끝 벽돌 제거 $\to (3)$ G $3$; 2번 또는 3번 벽돌 제거 $\to (1, 2)$ 또는 $(2, 1)$, G

[4] #2 7.NS.A.3 벽 크기 $5$. 수 결과 G 값들: $(4)$ G $1$; $(1, 3)$ G $1 \oplus 3 = 2$; $(2, 2)$ G $0$; $

[5] #2 7.NS.A.3 벽 크기 $6$. 수 결과 G 값들: 끝 벽돌 $\to (5)$ G $4$; 2번 또는 5번 $\to (1, 4)$ G $1 \oplus 1 =

[6] #7 7.NS.A.3 Sprague-Grundy XOR 적용. 세 벽 위치의 Grundy 수 = $G(w_1) \oplus G(w_2) \oplus G(w_3)$.

[7] #3 7.NS.A.3 P-position (다음 플레이어 패) 는 Grundy 가 $0$. 유일한 G $= 0$ 후보는 (B) $(6, 2, 1)$. Arjun 이

검토

합리성 확인: 감각 점검. 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 수에 거울로 응수해 항상 마지막 벽돌 차지) 도 같은 결론.

대안 접근: 도구 #5 (패턴 + 작은 케이스) — Sprague-Grundy 정리 없이도, $(6, 2, 1)$ 에서 Arjun 의 모든 수에 대해 Beth 가 대칭 거울 응수를 찾을 수 있음을 직접 확인. AoPS 풀이 1, 4 는 이 "쌍-거울" 논증을 직접 사용. 단, Sprague-Grundy 가 더 깔끔하고 빠름.

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

7.NS.A.3 유리수 사칙연산을 이용한 실생활 문제 해결 (mex (집합에서 빠진 가장 작은 비음정수) 계산, 작은 비음정수의 이진 XOR, 그리고 벽 $1$~$6$ 의 재귀적 Grundy 값 계산.)

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

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: B

검토

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

비슷한 유형 더 풀어보기