AMC 10 · 2022 · #19

• 안쪽 $3 \times 3$ 격자를 라벨링: 네 모서리 $C_1, C_2, C_3, C_4$, 네 가장자리 $E_N, E_S, E_E, E_W$, 중앙 $M$.
• 기억할 사실: 모서리는 주변에 이웃 $3$ 개 (가장자리 두 개 + 중앙), 가장자리는 주변 이웃 $5$ 개, 중앙은 주변 $8$ 개 모두가 이웃.

💡 $3 \times 3$ 한 번 그리고 각 위치마다 이웃 수를 세어 두기 — 모서리 (드문), 가장자리 (중간), 중앙 (전부).

• 경우 1: 중앙 $M$ 이 처음에 채워짐.
• $M$ 이 살아남으려면 채워진 주변 칸이 $2$ 또는 $3$ 개.
• 다른 모든 주변 칸은 비어야 하므로, 채워진 칸은 이웃 합 (중앙 $M = 1$ 포함) 이 $2$ 또는 $3$ 이 되지 말아야 하고, 빈 칸은 이웃 합이 정확히 $3$ 이 되지 말아야 함.

💡 중앙은 모든 칸의 이웃이라 독립적으로 다룰 수밖에 없음.

• 경우 1.1: $M$ 의 채워진 주변 정확히 $2$ 개, $P_1, P_2$.
• 각 $P_i$ 가 죽으려면 이웃 합 ($M$ 에서 $1$ + 다른 주변 채워진 이웃) $\ne 2, 3$, 즉 $P_1, P_2$ 가 서로 이웃이 아니어야 함.
• 빈 주변 칸이 $P_1, P_2$ 둘 다와 이웃이면 $1 + 2 = 3$ 으로 부활 — 금지.
• 이 조건을 만족하는 비이웃 쌍은 정반대 모서리 쌍 $\{C_1, C_3\}$, $\{C_2, C_4\}$ 두 가지뿐.

💡 정반대 모서리 쌍만 서로 비이웃이면서 공통 빈 이웃을 갖지 않음.

• 경우 1.2: $M$ 의 채워진 주변 $3$ 개 $P_1, P_2, P_3$.
• 각 $P_i$ 가 죽으려면 다른 주변 채워진 이웃이 $0$ 개여야 함 ($P_i$ 의 총 이웃 합 = $1 + 0 = 1$, $\ne 2, 3$).
• 세 칸이 상호 비이웃.
• 하지만 어떤 독립집합을 잡아도 두 칸과 동시에 이웃인 빈 주변 칸이 존재 — 부활.
• $0$ 가지.

💡 상호 비이웃인 세 주변 칸은 항상 "공통 이웃" 빈 칸을 만들어 그 칸이 부활.

경우 1 합계: $2$ 가지.

💡 정반대 모서리 쌍 둘뿐.

• 경우 2: $M$ 이 처음에 빔.
• $M$ 이 부활하려면 채워진 주변 정확히 $3$ 개 $P_1, P_2, P_3$.
• 각 $P_i$ 가 죽으려면 다른 채워진 주변 이웃이 $0$ 또는 $1$ 개 ($\ne 2, 3$).
• 각 빈 주변 칸의 채워진 이웃 수 $\ne 3$.
• 채워진 세 칸의 모양을 인접 그래프 차수로 분류.

💡 세 채워진 칸 중 어느 칸도 다른 둘과 동시에 이웃이 아니고, 바깥 빈 칸 중 세 칸 모두를 이웃으로 가진 칸도 없음.

• 모양 A — 모서리 세 개 (서로 비이웃): $\binom{4}{3} = 4$ 가지.
• 각 빈 칸이 이웃하는 채워진 칸 수는 $\le 2$.
• 유효.
• $\Rightarrow 4$ 가지.

💡 네 모서리 중 하나만 비우는 선택.

• 모양 B — 한 변에 있는 두 모서리 + 정반대 가장자리 (예: $C_1, C_2, E_S$).
• 서로 비이웃, 셋 모두에 이웃인 빈 칸 없음.
• 두 모서리가 어느 변에 있는지 선택 $4$ 가지.
• $\Rightarrow 4$ 가지.

💡 한 변의 양 모서리 + 그 반대편 외로운 가장자리.

• 모양 C — 한 모서리에서 만나는 두 가장자리 + 대각선 반대 모서리 (예: $E_N, E_W, C_3$, 두 가장자리는 모서리 $C_1$ 에서 만남, $C_1$ 은 비어 있음).
• 두 가장자리는 서로 이웃 (차수 $1$), 멀리 떨어진 $C_3$ 는 둘 모두에 비이웃.
• 모서리 $C_1$ 위치를 $4$ 곳 중에서 선택.
• $\Rightarrow 4$ 가지.

💡 한 모서리에서 만나는 두 가장자리 + 대각선 끝 모서리.

• 모양 D — 한 모서리 + 그에 이웃한 한 가장자리 (L 형태) + 대각선 반대 모서리 (예: $C_1, E_N, C_3$).
• $C_1$ 과 $E_N$ 은 이웃 (차수 $1$), $C_3$ 는 둘 모두에 비이웃.
• 모서리 $4$ 곳 $\times$ 이웃 가장자리 $2$ 선택 $= 8$ 가지.

💡 L 자 (모서리 + 그 옆 가장자리 하나) 를 한 모서리에 두고, 대각선 끝 모서리도 채움.

• 경우 2 합계: $4 + 4 + 4 + 8 = 20$.
• 경우 1 과 합쳐 총 $= 2 + 20 = 22$.
• 답 $\textbf{(C)}\ 22$.

💡 서로 배반인 두 경우를 합치기.