AMC 10 · 2024 · #25

학년 7 countinggeometry-2d

systematic-enumerationspatial-visualizationpattern-recognitioncombinations-basic identify-subproblemscaseworkpattern-recognition ↑ 선수 지식: systematic-enumerationspatial-visualization

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

문제

The figure below shows a dotted grid $8$ cells wide and $3$ cells tall consisting of $1''\times1''$ squares. Carl places $1$ -inch toothpicks along some of the sides of the squares to create a closed loop that does not intersect itself. The numbers in the cells indicate the number of sides of that square that are to be covered by toothpicks, and any number of toothpicks are allowed if no number is written. In how many ways can Carl place the toothpicks?

$\textbf{(A) }130\qquad\textbf{(B) }144\qquad\textbf{(C) }146\qquad\textbf{(D) }162\qquad\textbf{(E) }196$

답을 골라 클릭하세요.

(A)

130

(B)

144

(C)

146

(D)

162

(E)

196

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 가로 $8$ 칸, 세로 $3$ 칸의 점 격자에서 칼은 칸의 변을 따라 $1$ 인치 이쑤시개를 놓아 자기 자신과 교차하지 않는 하나의 닫힌 고리를 만듭니다. 가운데 줄의 $8$ 개 칸에는 모두 "$1$" 이 적혀 있어, 각 칸은 네 변 중 정확히 한 변이 고리 위에 있어야 합니다. 위·아래 줄의 칸에는 제약이 없습니다. 만들 수 있는 고리는 몇 개일까요?

주어진 것: 격자는 단위정사각형으로 된 $8 \times 3$; 이쑤시개는 자기교차 없는 하나의 닫힌 고리를 이룬다; 가운데 줄의 $8$ 개 칸은 각각 정확히 $1$ 개의 변이 고리에 포함; 위·아래 줄에는 변 개수 제약이 없다; 선택지: (A) $130$, (B) $144$, (C) $146$, (D) $162$, (E) $196$

구하는 것: 유효한 고리의 총 개수

이해

계획

주요 도구: #1 그림 그리기

보조 도구: #7 작은 문제로 쪼개기, #5 패턴 찾기

"가운데 칸마다 정확히 한 변" 이라는 규칙은 말로만 들으면 잡히지 않습니다. 그래서 첫 수는 도구 #1(그림 그리기): $8 \times 3$ 격자를 그려놓고 가운데 칸 하나하나에 대해 "네 변 중 어느 변이 고리 위에 있을까?" 라고 묻는 것입니다. 그림에서 곧바로 두 가지 구조 가족이 보이고, 도구 #7(작은 문제로 쪼개기)로 (A) 가운데 줄을 통과하지 않고 위 또는 아래에만 머무는 고리와 (B) 가운데 줄을 윗변 $T_i$ 와 아랫변 $B_i$ 를 섞어가며 "엮는" 고리로 셈을 분할할 수 있습니다. (B) 안에서는 도구 #5(패턴 찾기)가 받습니다 — 가운데 줄 안쪽 칸 하나하나가 독립적인 위/아래 선택이라, 자유 칸 개수에 따라 $2^k$ 꼴이 깔끔하게 나옵니다.

실행 — 정답: C

#1 그림 그리기 4.G.A.1 단계 1

격자를 그리고 가운데 줄 각 칸의 네 변에 이름을 붙입니다.
윗변은 $T_i$ ($y = 2$ 위), 아랫변은 $B_i$ ($y = 1$ 위), 세로 두 변은 $V_i$ 와 $V_{i+1}$ ($x = i, x = i+1$ 에서 $y = 1$ 과 $y = 2$ 사이).
규칙은 "$i = 0, 1, \dots, 7$ 각각에 대해 $\{T_i, B_i, V_i, V_{i+1}\}$ 중 정확히 하나가 고리 위에 있다" 입니다.

$$\text{모든 } i: \;\#\{T_i, B_i, V_i, V_{i+1}\} \cap \text{고리} = 1$$

💡 가운데 칸마다 후보 네 변에 이름을 붙이는 것은 4학년의 "점·선·선분 알아보기" — 말 문제를 "변 고르기" 문제로 바꿔줍니다.

#1 그림 그리기 4.G.A.1 단계 2

"공유 세로" 경우를 배제합니다.
$1 \le i \le 7$ 인 세로 선분 $V_i$ 는 가운데 두 칸이 공유합니다.
만약 $V_i$ 가 고리 위에 있으면 양쪽 두 칸 모두 "한 변 채움" 이 끝나므로 $T_{i-1}, B_{i-1}, T_i, B_i$ 는 모두 고리 밖이어야 합니다.
그러면 고리는 $V_i$ 의 끝점에서 위로도 가고 아래로도 가는 식으로 한 세로선에서 좁아져야 하고, 그림으로 그려보면 다른 가운데 칸들의 "한 변" 조건을 모두 지키면서 하나의 닫힌 비교차 고리로 닫을 수 없음을 확인할 수 있습니다.
따라서 내부 공유 세로 $V_1, \dots, V_7$ 은 절대 고리 위에 있지 않고, 가운데 칸의 "선택된 변" 은 $\{T_i, B_i, V_0 \,(i=0\text{일 때만}), V_8 \,(i=7\text{일 때만})\}$ 안에서만 나옵니다.

$$V_1, V_2, \dots, V_7 \notin \text{고리}$$

💡 $V_i$ 근처의 가상 고리를 그려보면 모순이 보입니다. "이 도형이 존재할 수 있는가" 를 기하 속성으로 판별하는 4학년식 접근입니다.

#7 작은 문제로 쪼개기 7.SP.C.8 단계 3

고리가 어디에 사느냐로 두 작은 문제로 나눕니다.
(A) 가운데 줄의 가로 내부를 전혀 건드리지 않고 위쪽 또는 아래쪽에만 머무는 고리.
(B) 가운데 줄을 가로지르며 윗변 $T_i$ 와 아랫변 $B_i$ 를 섞어 쓰는 "엮는" 고리 — 여기서 사용할 수 있는 세로 선분은 격자 가장자리 $V_0$ ($x = 0$) 와 $V_8$ ($x = 8$) 뿐이고, 나머지 연결은 위쪽 줄과 아래쪽 줄 안에서 이루어집니다.
(A) 와 (B) 가 유효한 고리 전부를 빠짐없이 덮으므로 답 $= \#(A) + \#(B)$.

$$\#\text{고리} = \#(A) + \#(B)$$

💡 셈을 서로 겹치지 않는 두 경우로 쪼개는 것은 7학년의 "표본공간·정리된 목록" 기법 — 어려운 셈 하나가 쉬운 셈 둘로 바뀝니다.

#1 그림 그리기 4.G.A.2 단계 4

(A) 의 개수를 셉니다.
엮지 않는 고리는 칸들로 이루어진 가로 직사각형의 경계입니다.
가운데 칸마다 정확히 한 변을 차지하는 경우는 두 가지뿐 — 위쪽 줄 전체 칸들의 경계 직사각형(이때 모든 $T_i$ 가 고리)과 아래쪽 줄 전체 칸들의 경계 직사각형(이때 모든 $B_i$ 가 고리).
그 외의 어떤 직사각형도 가운데 칸 일부를 빗나가거나 $V$ 변에 맞아 카운트를 깨뜨립니다.
따라서 $\#(A) = 2$.

$$\#(A) = 2$$

💡 그림으로 보면 두 직사각형만 통합니다 — 도형을 변·각으로 분류하는 4학년 기하.

#5 패턴 찾기 7.SP.C.8 단계 5

(B) 의 틀을 세웁니다.
엮는 고리는 가운데 줄을 가로질러야 하므로, $i = 0, 1, \dots, 7$ 각 칸의 "선택된 변" 은 윗변 $T_i$ 또는 아랫변 $B_i$ 중 하나입니다 (내부 공유 세로는 이미 모두 배제, $V_0, V_8$ 은 양쪽 끝 두 칸 $i = 0, 7$ 만 접합니다).
따라서 안쪽 여섯 칸 $i = 1, 2, \dots, 6$ 각각이 독립적인 위/아래 선택이 되고, 양끝 $i = 0$ 과 $i = 7$ 은 고리가 왼·오 가장자리에서 어떻게 닫히느냐에 따라 정해집니다.
안쪽 선택이 어떻든 위·아래 줄의 칸들(제약 없음)이 그에 맞춰 경로를 이어줄 수 있습니다.
그러므로 (B) 의 셈은 가장자리 닫힘에 따라 네 하위 경우로 나누고, 각 경우마다 안쪽 자유 칸 수만큼 $2$ 의 거듭제곱이 나옵니다.

$$\text{안쪽 선택: } 2 \times 2 \times \dots \times 2 = 2^6 = 64 \text{ (가장자리 닫힘 한 경우당)}$$

💡 안쪽 가운데 칸 하나하나가 서로 독립인 위/아래 동전 던지기 — 7학년의 "$n$ 개 독립 선택 = $2^n$ 결과" 곱셈 원리 그대로입니다.

#5 패턴 찾기 7.SP.C.8 단계 6

$x = 0$ 과 $x = 8$ 에서 어떻게 닫히는지에 따른 네 하위 경우를 셉니다.
(B1) 양쪽 가장자리 모두로 닫힘: $V_0$ 과 $V_8$ 이 모두 고리 위 → 칸 $i = 0$ 과 $i = 7$ 의 선택 변이 강제로 $V_0, V_8$ 이 되고, 안쪽 $i = 1, \dots, 6$ 만 자유 → $2^6 = 64$ 가지.
(B2) 왼쪽 $V_0$ 만으로 닫힘 (오른쪽은 위·아래 줄로 닫힘): $i = 0$ 은 $V_0$ 으로 강제, $i = 7$ 은 다른 안쪽 칸들처럼 자유 위/아래가 되지만 위·아래 경로의 페리티가 안쪽 칸 하나를 잠그므로 자유 칸은 결국 다섯 개 → $2^5 = 32$ 가지.
(B3) 오른쪽 $V_8$ 만으로 닫힘: 좌우 대칭으로 $2^5 = 32$ 가지.
(B4) 양쪽 가장자리 모두 사용 안 함 ($V_0, V_8$ 모두 고리 밖): $i = 0$ 과 $i = 7$ 모두 위·아래 페리티로 잠기고, 안쪽 네 칸만 자유 → $2^4 = 16$ 가지.

$$\#(B) = 2^6 + 2^5 + 2^5 + 2^4 = 64 + 32 + 32 + 16 = 144$$

💡 가장자리 닫힘 선택이 안쪽 칸 몇 개를 잠그고 몇 개를 풀어주느냐만 정해지면, 나머지는 자유 칸 수만큼의 $2$ 의 거듭제곱 — 층층이 쌓은 독립 선택의 표본공간 셈.

#7 작은 문제로 쪼개기 7.SP.C.8 단계 7

두 작은 문제의 셈을 더합니다.
4단계에서 $\#(A) = 2$, 6단계에서 $\#(B) = 144$.
총 $= 2 + 144 = 146$, 선택지 (C).

$$\#\text{고리} = 2 + 144 = 146 \;\Rightarrow\; \textbf{(C)}$$

💡 서로 겹치지 않는 경우들의 셈은 그대로 더하면 끝 — 모든 유효 고리가 (A), (B1), (B2), (B3), (B4) 중 정확히 하나에 들어갔습니다.

[1] #1 4.G.A.1 격자를 그리고 가운데 줄 각 칸의 네 변에 이름을 붙입니다. 윗변은 $T_i$ ($y = 2$ 위), 아랫변은 $B_i$ ($y = 1$ 위),

[2] #1 4.G.A.1 "공유 세로" 경우를 배제합니다. $1 \le i \le 7$ 인 세로 선분 $V_i$ 는 가운데 두 칸이 공유합니다. 만약 $V_i$ 가 고리

[3] #7 7.SP.C.8 고리가 어디에 사느냐로 두 작은 문제로 나눕니다. (A) 가운데 줄의 가로 내부를 전혀 건드리지 않고 위쪽 또는 아래쪽에만 머무는 고리. (B)

[4] #1 4.G.A.2 (A) 의 개수를 셉니다. 엮지 않는 고리는 칸들로 이루어진 가로 직사각형의 경계입니다. 가운데 칸마다 정확히 한 변을 차지하는 경우는 두 가지

[5] #5 7.SP.C.8 (B) 의 틀을 세웁니다. 엮는 고리는 가운데 줄을 가로질러야 하므로, $i = 0, 1, \dots, 7$ 각 칸의 "선택된 변" 은 윗변 $

[6] #5 7.SP.C.8 $x = 0$ 과 $x = 8$ 에서 어떻게 닫히는지에 따른 네 하위 경우를 셉니다. (B1) 양쪽 가장자리 모두로 닫힘: $V_0$ 과 $V_

[7] #7 7.SP.C.8 두 작은 문제의 셈을 더합니다. 4단계에서 $\#(A) = 2$, 6단계에서 $\#(B) = 144$. 총 $= 2 + 144 = 146$, 선

검토

합리성 확인: 분해 $2 + 64 + 32 + 32 + 16 = 146$ 의 모양이 자연스럽습니다. 평범한 직사각형 두 개에 더해, $2$ 의 거듭제곱 가족 $\{16, 32, 32, 64\}$ 가 비율 $1{:}2{:}2{:}4$ 로 나오는데, 이는 자유 안쪽 칸 수 $4, 5, 5, 6$ 과 그대로 맞아떨어집니다. 격자의 좌우 대칭 덕에 (B2) 와 (B3) 의 셈이 같아야 하고, 실제로 $32 = 32$ 로 일치 — 공짜 확인입니다. 답 $146$ 은 선택지에 정확히 있으며, 인접 오답 $144$ 는 평범한 직사각형 두 개를 빼먹은 값이고, $130$ 이나 $162$ 는 그림이 지지하지 않는 비대칭 셈에서 나옵니다.

대안 접근: 도구 #3(가능성 좁히기)을 선택지에 적용합니다. $146 - 2 = 144 = 16 + 32 + 32 + 64$ 처럼 격자의 좌우 대칭(중간 두 항이 같음)을 그대로 반영하면서 "평범한 직사각형 두 개 + 서로 다른 $2$ 의 거듭제곱 합" 으로 분해되는 값은 (C) $146$ 뿐입니다. $130, 144, 162, 196$ 은 평범한 직사각형 두 개를 빼먹었거나 대칭 경우를 중복으로 세거나 그런 분해가 아예 안 됩니다. 평범한 두 직사각형 고리가 존재함만 그림으로 확인하면 (C) 가 곧바로 좁혀집니다.

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

4.G.A.1 이차원 도형에서 점·직선·선분·반직선·각·수직·평행을 그리고 알아보기 ($8 \times 3$ 격자를 그리고 가운데 칸의 후보 네 변 $T_i, B_i, V_i, V_{i+1}$ 에 이름을 붙인 뒤, 내부 공유 세로 선분이 고리에 들어갈 수 없음을 그림으로 확인.)
4.G.A.2 평행·수직선이나 특정 크기 각의 유무로 이차원 도형 분류하기 (엮지 않는 경우에서 가운데 줄 규칙을 만족하는 직사각형 고리가 위쪽 줄 경계와 아래쪽 줄 경계 단 두 개뿐임을 도형 분류로 인식.)
7.SP.C.8 정리된 목록·표·나무그림 등으로 복합 사건의 확률을 구하고, 곱셈 원리로 경우의 수 세기 (서로 겹치지 않는 경우(엮지 않는 경우 vs 엮는 경우의 네 가장자리 하위 경우)로 분할하고, 각 엮는 하위 경우를 안쪽 자유 칸의 독립적 위/아래 선택에서 나오는 $2$ 의 거듭제곱으로 셈.)

⭐ 어려워 보이는 셈도 그림을 그려놓고 칸마다 "한 변은 어디?" 라는 독립적 yes/no 를 묻는 순간 작아집니다. 여기서는 자유로운 가운데 칸 하나하나가 위/아래 동전 던지기였고, $2 + 2^4 + 2^5 + 2^5 + 2^6 = 146$ 으로 선택지 (C) 에 도착합니다.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: C

검토

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

비슷한 유형 더 풀어보기