systematic-enumerationcaseworkspatial-visualizationcellular-automatoncombinations-basiccaseworksystematic-enumerationidentify-subproblemsphysical-representation↑ 선수 지식:systematic-enumerationspatial-visualization
Each square in a 5×5 grid is either filled or empty, and has up to eight adjacent neighboring squares, where neighboring squares share either a side or a corner. The grid is transformed by the following rules:
Any filled square with two or three filled neighbors remains filled. Any empty square with exactly three filled neighbors becomes a filled square. All other squares remain empty or become empty.
A sample transformation is shown in the figure below.
Suppose the 5×5 grid has a border of empty squares surrounding a 3×3 subgrid. How many initial configurations will lead to a transformed grid consisting of a single filled square in the center after a single transformation? (Rotations and reflections of the same configuration are considered different.)
문제 재정리: 테두리가 비어 있는 $5 \times 5$ Conway 식 격자에서, 한 번 변환 후 중앙 칸 하나만 채워지는 처음 상태 (안쪽 $3 \times 3$) 의 개수를 구하세요.
주어진 것: 변환 규칙: 채워진 칸은 이웃 중 채워진 칸이 $2$ 또는 $3$ 개일 때만 유지; 빈 칸은 정확히 $3$ 개일 때만 채워짐; 나머지는 모두 빈 칸; 이웃은 대각선 포함 — 한 칸 당 최대 $8$ 개; 테두리는 항상 비어 있으므로 안쪽 $9$ 칸만 채워질 수 있음; 목표: 변환 후 중앙 칸만 채워지고 나머지 $8$ 칸은 모두 빔; 선택지: (A) $14$, (B) $18$, (C) $22$, (D) $26$, (E) $30$
구하는 것: 그 한 칸 결과로 이어지는 처음 $3 \times 3$ 상태의 가짓수
이해
문제 재정리: 테두리가 비어 있는 $5 \times 5$ Conway 식 격자에서, 한 번 변환 후 중앙 칸 하나만 채워지는 처음 상태 (안쪽 $3 \times 3$) 의 개수를 구하세요.
주어진 것: 변환 규칙: 채워진 칸은 이웃 중 채워진 칸이 $2$ 또는 $3$ 개일 때만 유지; 빈 칸은 정확히 $3$ 개일 때만 채워짐; 나머지는 모두 빈 칸; 이웃은 대각선 포함 — 한 칸 당 최대 $8$ 개; 테두리는 항상 비어 있으므로 안쪽 $9$ 칸만 채워질 수 있음; 목표: 변환 후 중앙 칸만 채워지고 나머지 $8$ 칸은 모두 빔; 선택지: (A) $14$, (B) $18$, (C) $22$, (D) $26$, (E) $30$
계획
주요 도구: #7 작은 문제로 쪼개기
보조 도구: #1 그림 그리기, #2 빠짐없이 나열하기, #10 직접 만져보기
도구 #7 (쪼개기): 중앙 칸이 처음에 "채워짐" 인지 "비어 있음" 인지로 두 경우로 분할 — 추론 방식이 매우 다름. 중앙 채워짐: 이웃 중 $2$ 또는 $3$ 개의 주변 칸이 채워져야 하고, 모든 주변 칸은 비도록 죽거나 그대로 비어야 함. 중앙 비어 있음: 정확히 $3$ 개의 주변 채워진 칸이 있어야 하고 결과적으로 모두 비어야 함. 도구 #1 (그림): 모서리 $C$, 가장자리 $E$, 중앙 $M$ 으로 표시한 $3 \times 3$ 그림으로 이웃 관계 추적. 도구 #2 (나열): 각 경우의 조건을 갖고 작은 유한 집합을 빠짐없이 훑기. 도구 #10 (만져보기): 그래프 종이에 동전을 놓고 손으로 이웃 세기.
실행 — 정답: C
#1 그림 그리기 K.G.A.1단계 1
안쪽 $3 \times 3$ 격자를 라벨링: 네 모서리 $C_1, C_2, C_3, C_4$, 네 가장자리 $E_N, E_S, E_E, E_W$, 중앙 $M$.
기억할 사실: 모서리는 주변에 이웃 $3$ 개 (가장자리 두 개 + 중앙), 가장자리는 주변 이웃 $5$ 개, 중앙은 주변 $8$ 개 모두가 이웃.
💡 세 채워진 칸 중 어느 칸도 다른 둘과 동시에 이웃이 아니고, 바깥 빈 칸 중 세 칸 모두를 이웃으로 가진 칸도 없음.
#2 빠짐없이 나열하기 3.OA.A.3단계 7
모양 A — 모서리 세 개 (서로 비이웃): $\binom{4}{3} = 4$ 가지.
각 빈 칸이 이웃하는 채워진 칸 수는 $\le 2$.
유효.
$\Rightarrow 4$ 가지.
$$\text{모양 A: } 4$$
💡 네 모서리 중 하나만 비우는 선택.
#2 빠짐없이 나열하기 3.OA.A.3단계 8
모양 B — 한 변에 있는 두 모서리 + 정반대 가장자리 (예: $C_1, C_2, E_S$).
서로 비이웃, 셋 모두에 이웃인 빈 칸 없음.
두 모서리가 어느 변에 있는지 선택 $4$ 가지.
$\Rightarrow 4$ 가지.
$$\text{모양 B: } 4$$
💡 한 변의 양 모서리 + 그 반대편 외로운 가장자리.
#2 빠짐없이 나열하기 3.OA.A.3단계 9
모양 C — 한 모서리에서 만나는 두 가장자리 + 대각선 반대 모서리 (예: $E_N, E_W, C_3$, 두 가장자리는 모서리 $C_1$ 에서 만남, $C_1$ 은 비어 있음).
두 가장자리는 서로 이웃 (차수 $1$), 멀리 떨어진 $C_3$ 는 둘 모두에 비이웃.
모서리 $C_1$ 위치를 $4$ 곳 중에서 선택.
$\Rightarrow 4$ 가지.
$$\text{모양 C: } 4$$
💡 한 모서리에서 만나는 두 가장자리 + 대각선 끝 모서리.
#2 빠짐없이 나열하기 3.OA.A.3단계 10
모양 D — 한 모서리 + 그에 이웃한 한 가장자리 (L 형태) + 대각선 반대 모서리 (예: $C_1, E_N, C_3$).
$C_1$ 과 $E_N$ 은 이웃 (차수 $1$), $C_3$ 는 둘 모두에 비이웃.
모서리 $4$ 곳 $\times$ 이웃 가장자리 $2$ 선택 $= 8$ 가지.
$$\text{모양 D: } 8$$
💡 L 자 (모서리 + 그 옆 가장자리 하나) 를 한 모서리에 두고, 대각선 끝 모서리도 채움.
#7 작은 문제로 쪼개기 2.OA.A.1단계 11
경우 2 합계: $4 + 4 + 4 + 8 = 20$.
경우 1 과 합쳐 총 $= 2 + 20 = 22$.
답 $\textbf{(C)}\ 22$.
$$\text{총합} = 2 + 20 = 22$$
💡 서로 배반인 두 경우를 합치기.
[1]
#1 K.G.A.1안쪽 $3 \times 3$ 격자를 라벨링: 네 모서리 $C_1, C_2, C_3, C_4$, 네 가장자리 $E_N, E_S, E_E, E_W$
[2]
#7 1.OA.A.2경우 1: 중앙 $M$ 이 처음에 채워짐. $M$ 이 살아남으려면 채워진 주변 칸이 $2$ 또는 $3$ 개. 다른 모든 주변 칸은 비어야 하므로
[3]
#2 3.OA.D.8경우 1.1: $M$ 의 채워진 주변 정확히 $2$ 개, $P_1, P_2$. 각 $P_i$ 가 죽으려면 이웃 합 ($M$ 에서 $1$ + 다른
[4]
#2 3.OA.D.8경우 1.2: $M$ 의 채워진 주변 $3$ 개 $P_1, P_2, P_3$. 각 $P_i$ 가 죽으려면 다른 주변 채워진 이웃이 $0$ 개여야
[5]
#7 1.OA.A.2경우 1 합계: $2$ 가지.
[6]
#7 1.OA.A.2경우 2: $M$ 이 처음에 빔. $M$ 이 부활하려면 채워진 주변 정확히 $3$ 개 $P_1, P_2, P_3$. 각 $P_i$ 가 죽으려면
[7]
#2 3.OA.A.3모양 A — 모서리 세 개 (서로 비이웃): $\binom{4}{3} = 4$ 가지. 각 빈 칸이 이웃하는 채워진 칸 수는 $\le 2$. 유효
[8]
#2 3.OA.A.3모양 B — 한 변에 있는 두 모서리 + 정반대 가장자리 (예: $C_1, C_2, E_S$). 서로 비이웃, 셋 모두에 이웃인 빈 칸 없음.
[9]
#2 3.OA.A.3모양 C — 한 모서리에서 만나는 두 가장자리 + 대각선 반대 모서리 (예: $E_N, E_W, C_3$, 두 가장자리는 모서리 $C_1$ 에서
[10]
#2 3.OA.A.3모양 D — 한 모서리 + 그에 이웃한 한 가장자리 (L 형태) + 대각선 반대 모서리 (예: $C_1, E_N, C_3$). $C_1$ 과 $
[11]
#7 2.OA.A.1경우 2 합계: $4 + 4 + 4 + 8 = 20$. 경우 1 과 합쳐 총 $= 2 + 20 = 22$. 답 $\textbf{(C)}\ 22$
검토
합리성 확인: 확인: 각 모양이 회전 대칭이므로 $4$ 또는 $8$ 가지가 자연스럽고, 모양 D 만 반사 대칭이 없어 $\times 2$ 로 $8$ 가지. 경우 1 의 $2$ 는 "대각선 모서리 쌍만이 중앙 유지 + 부활 방지 조건을 둘 다 만족" 이라는 직관과 일치. 총합 $22$ 는 (C). 인접 오답 ($18, 26$) 은 모양 D 를 잘못 세거나 ($\pm 4$) 모양 C 를 빠뜨릴 때 빠지기 쉬운 함정.
대안 접근: 도구 #10 (직접 만져보기): $3 \times 3$ 격자에 동전 $3$ 개를 올려 보고 손으로 이웃을 세는 검증. $2^9 = 512$ 모든 초기 상태를 직접 돌릴 시간은 없지만, 채워진 칸이 $2$ 또는 $3$ 개인 상태로 줄이면 ($\binom{9}{2} + \binom{9}{3} = 36 + 84 = 120$), 한 시간 안에 전수조사 가능.
사용된 CCSS 표준 (최저 학년 3)
K.G.A.1 위·아래·옆 등으로 위치 기술하기 (안쪽 $3 \times 3$ 격자를 모서리·가장자리·중앙으로 라벨링하고 이웃 관계 추적.)
1.OA.A.2 세 수의 합이 $20$ 이내인 문장제 풀기 (채워진 이웃 수 ($1 + 2 = 3$ 등) 를 더해 생존·부활 규칙 점검.)
3.OA.D.8 $100$ 이내 사칙연산 두 단계 문장제 풀기 (부분 경우 조건 (비이웃, 공통 이웃 없음) 을 조합해 유효 패턴 선별.)
3.OA.A.3 $100$ 이내 곱셈·나눗셈 문장제 풀기 (각 모양의 회전 대칭 복사본 개수를 기본 구성 $\times$ 회전수로 계산.)
