AMC 10 · 2021 · #25
학년 5 counting문제
How many ways are there to place 3 indistinguishable red chips, 3 indistinguishable blue chips, and 3 indistinguishable green chips in the squares of a 3×3 grid so that no two chips of the same color are directly adjacent to each other, either vertically or horizontally?
답을 골라 클릭하세요.
AMC 10 2021 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.
도구 + CCSS 풀이
이해
문제 재정리: 구별할 수 없는 빨강 칩 $3$ 개, 파랑 칩 $3$ 개, 초록 칩 $3$ 개를 $3 \times 3$ 격자의 $9$ 칸에 한 칸당 한 칩씩 놓되, 같은 색의 두 칩이 변(가로 또는 세로) 으로 인접하지 않도록 배치하는 방법의 수를 구하세요.
주어진 것: $3 \times 3$ 격자, 총 $9$ 칸; 빨강 $3$ 개, 파랑 $3$ 개, 초록 $3$ 개 — 같은 색끼리는 구별 불가; 인접 조건: 같은 색의 두 칩이 가로 또는 세로 변을 공유하지 않음; 대각선 인접은 허용; 선택지: (A) $12$, (B) $18$, (C) $24$, (D) $30$, (E) $36$
구하는 것: 유효한 배치(컬러링) 의 수
이해
문제 재정리: 구별할 수 없는 빨강 칩 $3$ 개, 파랑 칩 $3$ 개, 초록 칩 $3$ 개를 $3 \times 3$ 격자의 $9$ 칸에 한 칸당 한 칩씩 놓되, 같은 색의 두 칩이 변(가로 또는 세로) 으로 인접하지 않도록 배치하는 방법의 수를 구하세요.
주어진 것: $3 \times 3$ 격자, 총 $9$ 칸; 빨강 $3$ 개, 파랑 $3$ 개, 초록 $3$ 개 — 같은 색끼리는 구별 불가; 인접 조건: 같은 색의 두 칩이 가로 또는 세로 변을 공유하지 않음; 대각선 인접은 허용; 선택지: (A) $12$, (B) $18$, (C) $24$, (D) $30$, (E) $36$
계획
주요 도구: #2 빠짐없이 나열하기
보조 도구: #1 그림 그리기, #7 작은 문제로 쪼개기, #9 더 쉬운 문제로 줄이기, #3 가능성 지우기
도구 #9(더 쉬운 문제) — 우선 "빨강 한 색만 인접 없이 놓는 방법" 을 묻는 더 쉬운 부분문제로 시작. 도구 #2(빠짐없이 나열) — $3 \times 3$ 의 3-원소 독립집합을 모두 나열. 도구 #1(그림 그리기) — 각 독립집합을 스케치해 패턴을 시각화. 도구 #7(작은 문제로 쪼개기) — 빨강 배치마다 남은 $6$ 칸에 $3$ B + $3$ G 채우는 방법 수 세기. 도구 #3(가능성 지우기) — 선택지 $\{12, 18, 24, 30, 36\}$ 모두 $6$ 의 배수라 패턴 인식에 도움.
실행 — 정답: E
5.G.B.4 단계 1 - 유효한 "빨강만" 배치 살펴보기.
- 칸을 $(r, c)$, $r, c \in \{1, 2, 3\}$ 으로 표기.
- 케이스 A — 빨강 집합이 중앙 $(2,2)$ 을 포함: 나머지 두 칩은 중앙과 인접하지 않고(즉 모서리 칸) 서로도 인접하지 않아야 함.
- 중앙은 네 모서리 모두와 인접하지 않고, 네 모서리는 서로 인접하지 않으므로 모서리 둘 자유 선택: $\binom{4}{2} = 6$ 개의 집합.
💡 중앙 포함 여부로 케이스 분리 — A 는 간단히 $6$ 개.
5.G.B.4 단계 2 - 케이스 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$ 개씩 네 종류.
5.G.B.4 단계 3 - 독립집합은 총 $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$ 개뿐.
4.OA.A.3 단계 4 - 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$ 배.
4.OA.A.3 단계 5 - 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$ 가지 유효 채움.
5.NBT.B.5 단계 6 - 서로 배타적 케이스 합산.
- P1 과 P2 는 동일 컬러링에서 동시에 일어날 수 없음(P1 빨강은 대각선, P2 빨강은 중앙 + 같은 변의 두 모서리 — 두 집합이 일치 불가).
- 표준 풀이가 이 둘이 "전부" 임을 보장.
- 합 $= 12 + 24 = 36$, 선택지 (E).
💡 분리된 두 케이스를 더하면 $12 + 24 = 36$ — 정확히 (E).
5.G.B.4 유효한 "빨강만" 배치 살펴보기. 칸을 $(r, c)$, $r, c \in \{1, 2, 3\}$ 으로 표기. 케이스 A — 빨강 집합이 중앙 5.G.B.4 케이스 B — 중앙 미포함. 세 모서리: $\binom{4}{3} = 4$ 개 모두 독립. 두 모서리 + 변중앙 한 칸: 모서리 쌍 ${(1, 5.G.B.4 독립집합은 총 $6 + 16 = 22$ 개이지만, 그중 "전체 9 칸을 유효히 3-색으로 완성 가능한" 빨강 배치만 추리면 단 두 종류 기하 패 4.OA.A.3 P1 채우기. 빨강을 주대각선 $\{(1,1),(2,2),(3,3)\}$ 에 놓자. $(1,2)$ 는 빨강 두 개에 끼어 있으니 B 또는 G. 4.OA.A.3 P2 채우기. 빨강을 $\{(2,2),(1,1),(1,3)\}$ (중앙 + 위쪽 두 모서리) 에 놓자. $(1,2)$ 는 R 두 개에 끼어 B 5.NBT.B.5 서로 배타적 케이스 합산. P1 과 P2 는 동일 컬러링에서 동시에 일어날 수 없음(P1 빨강은 대각선, P2 빨강은 중앙 + 같은 변의 두 모 검토
합리성 확인: 감각 점검. 단순 셈으로 $\tfrac{9!}{3!\,3!\,3!} = 1680$ 개 무제한 컬러링 중 $36$ 은 약 $2\%$ — 빡빡한 인접 제약에 어울리는 비율. 격자는 $D_4$ 대칭(회전 + 반사, 총 $8$) 이고, $D_4$ 작용 하에 두 대각선은 한 궤도, 네 변(상하좌우) 도 한 궤도로 깔끔. 색 라벨 $3$ 과 합쳐 $12 + 24 = 36$ 이 대칭 수와 일관. (B$\leftrightarrow$G 스왑이 빨강 배치 안에서 $\times 2$ 배 곱해지는 부분도 두 케이스에서 일관.)
대안 접근: 도구 #10(직접 만져보기): 색 칩으로 종이 격자 위에 빨강을 먼저 놓고 유효 모양 $6$ 개($2$ 대각선 + $4$ 중앙+변모서리쌍) 를 모두 시도, 각 모양에서 B/G 채움 $2$ 가지를 손으로 확인. 색 라벨 $3$ 을 곱해 $6 \cdot 2 \cdot 3 = 36$ 검산. 어린 학습자가 가장 빨리 "보이는" 풀이.
사용된 CCSS 표준 (최저 학년 5)
4.OA.A.3네 가지 연산을 이용한 여러 단계 문장제 해결 ("# 모양 $\times$ # 색 $\times$ # B/G 채움" 의 곱셈으로 각 패턴 합 계산.)5.NBT.B.5표준 알고리즘으로 다자릿 정수 능숙히 곱하기 ($2 \cdot 3 \cdot 2 = 12, \;4 \cdot 3 \cdot 2 = 24, \;12 + 24 = 36$ 계산.)5.G.B.4성질을 기준으로 평면도형 분류 (독립 3-칸 집합을 기하 종류(대각선, 세 모서리, 중앙+모서리 쌍, 변중앙 셋 등) 로 분류해 유효 배치 식별.)
⭐ 이 AMC 10 문제는 이미 배운 5학년 빠짐없이 나열·곱셈만 있으면 풀려요 — 한 색(빨강) 의 유효 배치 모양은 $2$ 가지 대각선과 $4$ 가지 "중앙 + 같은 변의 두 모서리" 만 가능, 각각에서 나머지 $6$ 칸을 B/G 로 채우는 방법은 정확히 $2$ 가지; 여기에 색깔 $3$ 가지를 곱하고 합하면 $2 \cdot 3 \cdot 2 + 4 \cdot 3 \cdot 2 = 12 + 24 = 36$.
⭐ 이 AMC 10 문제는 이미 배운 5학년 빠짐없이 나열·곱셈만 있으면 풀려요 — 한 색(빨강) 의 유효 배치 모양은 $2$ 가지 대각선과 $4$ 가지 "중앙 + 같은 변의 두 모서리" 만 가능, 각각에서 나머지 $6$ 칸을 B/G 로 채우는 방법은 정확히 $2$ 가지; 여기에 색깔 $3$ 가지를 곱하고 합하면 $2 \cdot 3 \cdot 2 + 4 \cdot 3 \cdot 2 = 12 + 24 = 36$.
비슷한 유형 더 풀어보기
같은 archetype · 비슷한 학년부터.
