AMC 10 · 2010 · #23

학년 7 counting

유형 Branching State Enumeration └ 세부 유형 Ordered Placement Count

systematic-enumerationcombinations-basicsymmetry-argument casework ↑ 선수 지식: systematic-enumeration

📏 긴 풀이 💡 3 개 인사이트

문제

$3 \times 3$ 배열의 칸에는 $1$ 부터 $9$ 까지의 모든 숫자가 들어가며, 모든 행과 열의 값이 증가하는 순서가 되도록 배열되어 있다. 이러한 배열은 몇 가지인가?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

AMC 10 2010 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $3 \times 3$ 격자에 숫자 $1$부터 $9$까지를 한 번씩 모두 채우되, 각 행은 왼쪽에서 오른쪽으로 커지고 각 열은 위에서 아래로 커지도록 한다. 이렇게 만들 수 있는 서로 다른 격자는 몇 개인가?

주어진 것: $3 \times 3$ 격자에 아홉 개의 숫자 $1, 2, \dots, 9$가 각각 정확히 한 번씩 들어간다; 각 행은 왼쪽에서 오른쪽으로 증가한다; 각 열은 위에서 아래로 증가한다; 보기: (A) $18$, (B) $24$, (C) $36$, (D) $42$, (E) $60$

구하는 것: 조건을 만족하는 격자의 개수

이해

계획

주요 도구: #2 빠짐없이 나열하기

보조 도구: #14 극단의 원리, #7 작은 문제로 쪼개기, #5 패턴 찾기

"몇 가지 배열인가"는 도구 #2(빠짐없이 나열하기)의 전형적인 신호다. 아홉 칸에 아홉 숫자를 무작정 나열하기에는 경우가 너무 많으므로, 먼저 도구 #14(극단의 원리)로 고정되는 칸을 못 박는다. 가장 작은 숫자는 왼쪽 위, 가장 큰 숫자는 오른쪽 아래에 강제되고, 가운데 값은 단 세 가지로 좁혀진다. 그러면 가운데 숫자를 기준으로 몇 개의 깔끔한 경우로 개수가 나뉜다 — 도구 #7(작은 문제로 쪼개기). 각 경우 안에서는 남은 숫자들이 작은 순서 묶음으로 떨어지므로 곱셈 원리로 쉽게 센다. 마지막으로 도구 #5(패턴 찾기)로 한 경우를 그 거울상에 재사용해 계산을 절반으로 줄인다.

실행 — 정답: D

#14 극단의 원리 1.NBT.B.3 단계 1

두 모서리 고정하기

왼쪽 위 칸 $a$는 자기 행과 열의 모든 값보다 작으므로, 나머지 여덟 숫자보다 모두 작다 — 따라서 $1$이어야 한다.
오른쪽 아래 칸 $i$는 자기 행과 열의 모든 값보다 크므로 $9$여야 한다.

$$a = 1, \quad i = 9$$

💡 전체에서 가장 작은 숫자는 그보다 작아야 할 것이 아무것도 없는 자리, 곧 왼쪽 위 모서리에만 올 수 있고, 가장 큰 숫자는 반대편 모서리에 온다.

#14 극단의 원리 1.NBT.B.3 단계 2

가운데 값 가두기

가운데 $e$는 $a$, $b$, $d$(위쪽과 왼쪽의 세 칸)보다 크므로, 적어도 세 숫자가 $e$보다 작아 $e \ge 4$가 된다.
또한 $f$, $h$, $i$(아래쪽과 오른쪽의 세 칸)보다 작으므로, 적어도 세 숫자가 더 커서 $e \le 6$이 된다.
따라서 가운데는 $4$, $5$, $6$ 중 하나다.

$$a,b,d < e < f,h,i \;\Rightarrow\; 4 \le e \le 6$$

💡 세 칸이 가운데보다 아래여야 하고 세 칸이 위여야 하므로, 가운데 숫자는 너무 작을 수도 너무 클 수도 없다.

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

가운데 숫자로 경우 나누기

가운데가 $4$인지 $5$인지 $6$인지에 따라 세 경우로 개수를 나눈다.
각 경우는 어떤 숫자들이 왼쪽 위 영역과 오른쪽 아래 영역에 강제되는지를 정해 주어, 남은 칸을 세기 쉽게 만든다.

$$\text{총합} = N(e{=}4) + N(e{=}5) + N(e{=}6)$$

💡 가운데의 기준값을 고정하면 하나의 어려운 개수 세기가 세 개의 작은 독립적인 세기로 바뀐다.

#2 빠짐없이 나열하기 3.OA.A.3 단계 4

가운데 = 4 세기

가운데보다 작은 세 숫자는 $4$보다 작은 $\{1,2,3\}$이다.
$a=1$이므로 칸 $b$와 $d$는 $\{2,3\}$을 순서만 바꿔 담는다($2$가지).
남은 숫자 $\{5,6,7,8\}$은 오른쪽 위 $c$, 오른쪽 가운데 $f$, 왼쪽 아래 $g$, 아래 가운데 $h$에 들어간다($i=9$).
남은 제약은 $c<f$(오른쪽 열)과 $g<h$(아래 행)뿐이고 둘은 서로 독립이다.
따라서 $\{5,6,7,8\}$ 중 오른쪽 열에 갈 두 개를 고르면 — 작은 쪽이 $c$, 큰 쪽이 $f$ — 나머지 두 개는 아래 행에 순서가 정해진 채 떨어진다: $\binom{4}{2}=6$가지.

$$N(e{=}4) = 2 \times \binom{4}{2} = 2 \times 6 = 12$$

💡 작은 숫자를 배치하고 나면, 남은 네 숫자를 순서가 정해진 쌍-쌍으로 나누는 것은 넷 중 둘을 고르는 일일 뿐이다.

#5 패턴 찾기 4.OA.C.5 단계 5

대칭으로 가운데 = 6 세기

모든 숫자 $k$를 $10-k$로 바꾸고 격자를 가운데를 중심으로 뒤집으면, 증가하는 행과 열이 다시 증가하는 행과 열로 바뀌고 가운데 $4$는 가운데 $6$으로 옮겨간다.
이는 두 경우 사이의 완벽한 일대일 대응이므로 개수가 같다.

$$k \mapsto 10-k \;\Rightarrow\; N(e{=}6) = N(e{=}4) = 12$$

💡 "$k$를 $10-k$로 바꾸기" 규칙은 작은 값과 큰 값을 맞바꾸는 거울이어서, 모든 가운데-$4$ 격자를 정확히 하나의 가운데-$6$ 격자와 짝지어 준다.

#2 빠짐없이 나열하기 3.OA.A.3 단계 6

가운데 = 5 세기

$a=1$, $i=9$이면 남은 작은 숫자 $\{2,3,4\}$와 큰 숫자 $\{6,7,8\}$이 $b,c,d,f,g,h$를 채운다.
행과 열 규칙에 따라 $b,d$는 작은 숫자, $f,h$는 큰 숫자로 강제된다.
그러면 작은 하나와 큰 하나를 $c$와 $g$에 나누어 넣게 된다.
$c$가 작고 $g$가 큰 경우: 작은 숫자 $\{2,3,4\}$가 $b,c,d$에 가되 $b<c$가 필요하고 $d$는 자유 — $3$가지 — 이며, 독립적으로 큰 숫자가 $f,h,g$에 가되 $g<h$가 필요하고 $f$는 자유 — $3$가지 — 이므로 $9$가지다.
$g$가 작고 $c$가 큰 경우는 그 거울상이라 다시 $9$가지다.

$$N(e{=}5) = (3 \times 3) + (3 \times 3) = 9 + 9 = 18$$

💡 가운데-$5$ 격자는 어느 대각선 칸이 작은 숫자를 담는지라는 자유도가 하나 더 있고, 각 선택은 정돈된 순서 삼중쌍 둘을 남긴다.

#2 빠짐없이 나열하기 2.NBT.B.5 단계 7

경우들 더하기

세 경우의 개수를 더해 조건을 만족하는 격자의 총수를 얻는다.

$$12 + 18 + 12 = 42 \;\Rightarrow\; \textbf{(D)}$$

💡 세 가지 가운데 값은 겹침 없이 모든 격자를 덮으므로 개수를 그냥 더하면 된다.

[1] #14 1.NBT.B.3 왼쪽 위 칸 $a$는 자기 행과 열의 모든 값보다 작으므로, 나머지 여덟 숫자보다 모두 작다 — 따라서 $1$이어야 한다. 오른쪽 아래 칸 $i

[2] #14 1.NBT.B.3 가운데 $e$는 $a$, $b$, $d$(위쪽과 왼쪽의 세 칸)보다 크므로, 적어도 세 숫자가 $e$보다 작아 $e \ge 4$가 된다. 또한

[3] #7 7.SP.C.8 가운데가 $4$인지 $5$인지 $6$인지에 따라 세 경우로 개수를 나눈다. 각 경우는 어떤 숫자들이 왼쪽 위 영역과 오른쪽 아래 영역에 강제되는

[4] #2 3.OA.A.3 가운데보다 작은 세 숫자는 $4$보다 작은 $\{1,2,3\}$이다. $a=1$이므로 칸 $b$와 $d$는 $\{2,3\}$을 순서만 바꿔 담는

[5] #5 4.OA.C.5 모든 숫자 $k$를 $10-k$로 바꾸고 격자를 가운데를 중심으로 뒤집으면, 증가하는 행과 열이 다시 증가하는 행과 열로 바뀌고 가운데 $4$는

[6] #2 3.OA.A.3 $a=1$, $i=9$이면 남은 작은 숫자 $\{2,3,4\}$와 큰 숫자 $\{6,7,8\}$이 $b,c,d,f,g,h$를 채운다. 행과 열

[7] #2 2.NBT.B.5 세 경우의 개수를 더해 조건을 만족하는 격자의 총수를 얻는다.

검토

합리성 확인: 세 경우 $e=4,5,6$은 빠짐이 없고(가운데는 다른 값일 수 없다) 서로 배타적(한 격자의 가운데 숫자는 하나)이므로, $12+18+12=42$로 더하는 것은 타당하다. $e=4$와 $e=6$ 사이의 대칭이 같은 개수로 나타나는 것도 좋은 내부 일관성 점검이다. 총합 $42$는 보기 (D)와 일치하며, $3\times3$ 증가 채움(정사각형 $3\times3$의 표준 영 타블로) 개수가 $9!/(5\cdot4\cdot3\cdot4\cdot3\cdot2\cdot3\cdot2\cdot1) = 362880/8640 = 42$라는 알려진 결과와도 맞는다.

대안 접근: 훅 길이 공식(영 타블로 이론에 적용한 도구 #9, 더 쉬운 문제로 줄이기)은 답을 한 번에 준다. $3\times3$ 정사각형의 훅 길이는 $\begin{smallmatrix}5&4&3\\4&3&2\\3&2&1\end{smallmatrix}$이고, 개수는 $9!$을 이들의 곱으로 나눈 $362880/8640 = 42$이다. 더 빠르지만 경우 나누기가 드러내는 구조를 감춘다. 둘 다 (D)를 준다.

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

1.NBT.B.3 Compare two two-digit numbers using symbols (숫자의 대소를 정렬해 $1$을 왼쪽 위 모서리, $9$를 오른쪽 아래에 강제하고, 가운데 숫자를 $\{4,5,6\}$으로 좁히는 데 사용.)
7.SP.C.8 Find probabilities of compound events using organized lists, tables, and simulation (가운데 숫자를 기준으로 전체 개수 세기를 경우로 정리하고 각 경우 안의 유효한 배치를 빠짐없이 나열하는 데 사용.)
3.OA.A.3 Solve multiplication and division word problems within 100 (각 경우 안에서 곱셈 세기 원리를 적용($e{=}4$에서 $2\times6$, $e{=}5$의 각 소경우에서 $3\times3$)하는 데 사용.)
4.OA.C.5 Generate a number or shape pattern following a given rule (규칙 $k\mapsto10-k$를 대칭으로 적용해 모든 가운데-$4$ 격자를 가운데-$6$ 격자와 짝지어 두 경우가 개수를 공유하도록 하는 데 사용.)
2.NBT.B.5 Fluently add and subtract within 100 (세 경우의 개수 $12+18+12$를 더해 총합 $42$에 도달하는 데 사용.)

⭐ 고정되는 칸부터 못 박자 — 왼쪽 위에 $1$, 오른쪽 아래에 $9$, 가운데는 $4$, $5$, $6$뿐이다 — 그다음 가운데 경우마다 따로 세면 $12+18+12=42$이다.