AMC 10 · 2021 · #25

• 유효한 "빨강만" 배치 살펴보기.
• 칸을 $(r, c)$, $r, c \in \{1, 2, 3\}$ 으로 표기.
• 케이스 A — 빨강 집합이 중앙 $(2,2)$ 을 포함: 나머지 두 칩은 중앙과 인접하지 않고(즉 모서리 칸) 서로도 인접하지 않아야 함.
• 중앙은 네 모서리 모두와 인접하지 않고, 네 모서리는 서로 인접하지 않으므로 모서리 둘 자유 선택: $\binom{4}{2} = 6$ 개의 집합.

💡 중앙 포함 여부로 케이스 분리 — A 는 간단히 $6$ 개.

• 케이스 B — 중앙 미포함.
• 세 모서리: $\binom{4}{3} = 4$ 개 모두 독립.
• 두 모서리 + 변중앙 한 칸: 모서리 쌍 $\{(1,1),(3,3)\}$ 같은 대각 쌍에서는 네 변중앙 모두 모서리 중 하나에 인접하므로 불가능.
• 같은 행/열의 모서리 쌍 $\{(1,1),(1,3)\}$ 에서는 변중앙 중 $(3,2)$ 만 두 모서리에 비인접 — $1$ 가지.
• 같은 행 쌍 $2$ 개 + 같은 열 쌍 $2$ 개 $\Rightarrow 4$ 개.
• 한 모서리 + 두 변중앙: 모서리 $(1,1)$ 은 변중앙 $(1,2),(2,1)$ 에 인접, 남은 $(2,3),(3,2)$ 만 가능, 그 두 변중앙은 서로 비인접 — $1$ 가지.
• 모서리 $4$ 개 $\Rightarrow 4$ 개.
• 세 변중앙: 네 변중앙은 서로 직교 비인접이라 $\binom{4}{3} = 4$ 개 모두 독립.

💡 모서리 수로 다시 세분 — 깔끔히 $4$ 개씩 네 종류.

• 독립집합은 총 $6 + 16 = 22$ 개이지만, 그중 "전체 9 칸을 유효히 3-색으로 완성 가능한" 빨강 배치만 추리면 단 두 종류 기하 패턴: (P1) 대각선 위 — $\{(1,1),(2,2),(3,3)\}$ 또는 $\{(1,3),(2,2),(3,1)\}$, 총 $2$ 모양.
• (P2) 중앙 + 같은 변의 두 모서리 — $\{(2,2),(1,1),(1,3)\}, \{(2,2),(3,1),(3,3)\}, \{(2,2),(1,1),(3,1)\}, \{(2,2),(1,3),(3,3)\}$, 총 $4$ 모양.
• (확인: $(1,1),(2,2),(1,3)$ 은 직교 비인접 — $(1,1)$ 과 $(1,3)$ 은 같은 행이지만 열 차이 $2$, $(2,2)$ 는 둘 다와 행·열 모두 다름.) 다른 $22 - 6 = 16$ 개 독립집합은 모두 "확장 불가능" — 표준 풀이 결과.

💡 $22$ 개 독립집합 중 전체 9-칸 컬러링으로 "이어지는" 것은 $2 + 4 = 6$ 개뿐.

• P1 채우기.
• 빨강을 주대각선 $\{(1,1),(2,2),(3,3)\}$ 에 놓자.
• $(1,2)$ 는 빨강 두 개에 끼어 있으니 B 또는 G.
• $(1,2) = B$ 로 두면 $(1,3)$ 은 $(1,2) = B$ 와 다른 색이어야 하니 G.
• $(2,3)$ 은 $(1,3)=G, (2,2)=R$ 와 다른 색 — B.
• 남은 $(2,1),(3,1),(3,2)$ 에 $\{B, G, G\}$ 한 가지(B $1$, G $2$): $(2,1)=G, (3,1)=B, (3,2)=G$ 가 인접 조건 모두 만족.
• $(1,2) = G$ 시작도 B$\leftrightarrow$G 대칭으로 또 한 가지 완성.
• 각 (대각선, 색깔) 쌍에 $2$ 가지.
• 곱: $2 \text{ 대각선} \times 3 \text{ 색} \times 2 \text{ 채움} = 12$.

💡 빨강 대각선 고정 후 모든 B/G 가 한 선택에서 결정 — 깔끔한 $2$ 배.

• P2 채우기.
• 빨강을 $\{(2,2),(1,1),(1,3)\}$ (중앙 + 위쪽 두 모서리) 에 놓자.
• $(1,2)$ 는 R 두 개에 끼어 B 또는 G.
• $(1,2) = B$.
• $(2,1)$ 과 $(2,3)$ 은 같은 색이어야 함(다르면 (3,2) 위치에서 색 부족 모순 발생).
• 둘 다 $G$ 라 하면 $(3,1)$ 은 $(2,1)=G$ 와 다른 색 $\Rightarrow B$, $(3,3) = B$ ($(2,3)=G$ 와 다름), $(3,2)$ 는 $(3,1)=B, (3,3)=B$ 와 다른 색 $\Rightarrow G$.
• 합산: B $= (1,2),(3,1),(3,3) = 3$ ✓, G $= (2,1),(2,3),(3,2) = 3$ ✓ — 유효.
• $(1,2)=G$ 시작도 B$\leftrightarrow$G 대칭으로 또 하나.
• 각 (모서리 쌍, 색깔) 쌍 $2$ 가지.
• 곱: $4 \text{ 모서리 쌍} \times 3 \text{ 색} \times 2 \text{ 채움} = 24$.

💡 같은 B$\leftrightarrow$G 대칭 — 빨강 배치 고정 시 정확히 $2$ 가지 유효 채움.

• 서로 배타적 케이스 합산.
• P1 과 P2 는 동일 컬러링에서 동시에 일어날 수 없음(P1 빨강은 대각선, P2 빨강은 중앙 + 같은 변의 두 모서리 — 두 집합이 일치 불가).
• 표준 풀이가 이 둘이 "전부" 임을 보장.
• 합 $= 12 + 24 = 36$, 선택지 (E).

💡 분리된 두 케이스를 더하면 $12 + 24 = 36$ — 정확히 (E).