AMC 10 · 2022 · #18

학년 8 algebra

유형 Branching State Enumeration └ 세부 유형 Rule-Governed Process Simulation

systems-of-equationscomplementary-countingsystematic-enumerationlinear-algebra-basiccasework complementary-countingcaseworkidentify-subproblemseasier-related-problem ↑ 선수 지식: systems-of-equationscomplementary-counting

📏 긴 풀이 💡 4 개 인사이트

문제

Consider systems of three linear equations with unknowns $x$ , $y$ , and $z$ ,
\begin{align*} a_1 x + b_1 y + c_1 z & = 0 \ a_2 x + b_2 y + c_2 z & = 0 \ a_3 x + b_3 y + c_3 z & = 0 \end{align*}
where each of the coefficients is either $0$ or $1$ and the system has a solution other than $x=y=z=0$ .
For example, one such system is $\{ 1x + 1y + 0z = 0, 0x + 1y + 1z = 0, 0x + 0y + 0z = 0 \}$
with a nonzero solution of $\{x,y,z\} = \{1, -1, 1\}$ . How many such systems of equations are there?
(The equations in a system need not be distinct, and two systems containing the same equations in a
different order are considered different.)

답을 골라 클릭하세요.

(A)

302

(B)

338

(C)

340

(D)

343

(E)

344

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 미지수 $x, y, z$ 에 대한 동차 일차연립방정식 세 개로 이루어진 시스템 중 계수 9 개가 각각 $0$ 또는 $1$ 이고 자명하지 않은 해 (모두 $0$ 이 아닌 해) 가 존재하는 시스템의 개수를 구하세요. 식의 순서는 구별하고, 같은 식이 두 번 나와도 됩니다.

주어진 것: $i = 1, 2, 3$ 에 대해 계수 $a_i, b_i, c_i \in \{0, 1\}$ 로 총 $9$ 개; $(x, y, z) \ne (0, 0, 0)$ 인 해가 존재해야 함; 전체 가능한 시스템 수 = $2^9 = 512$; 선택지: (A) $302$, (B) $338$, (C) $340$, (D) $343$, (E) $344$

구하는 것: 계수가 $\{0, 1\}$ 이고 행이 $\mathbb{R}$ 위에서 일차종속 (즉 동차 시스템이 비자명 해를 가짐) 인 $3 \times 3$ 행렬의 개수

이해

계획

주요 도구: #16 관점 바꾸기

보조 도구: #7 작은 문제로 쪼개기, #9 더 쉬운 문제로 줄이기, #2 빠짐없이 나열하기

도구 #16 (관점 바꾸기): "비자명 해 존재" 와 "행이 일차종속" 은 같은 말. 반대 (행이 일차독립) 를 세는 게 훨씬 쉬우니 $512$ 에서 빼면 됩니다. 도구 #7 (쪼개기): 일차독립 개수를 두 갈래로 나눔 — $\mathbb{F}_2$ (mod $2$ 세상) 에서 독립인 경우와 $\mathbb{F}_2$ 에서는 종속이지만 $\mathbb{R}$ 에서는 독립인 경우. 도구 #9 (더 쉬운 문제): mod $2$ 세상에서는 행 독립이 "새 행이 이전 행들의 생성공간에 들어가지 않는다" 라는 깔끔한 선택수 계산. 도구 #2 (나열): 나머지 "$\mathbb{R}$ 에서만 독립" 인 행렬은 수가 적어 직접 열거 가능.

실행 — 정답: B

#16 관점 바꾸기 8.EE.A.1 단계 1

전체 공간 계산.
$9$ 개 칸이 각각 $0$ 또는 $1$ 이므로 시스템 수 $= 2^9 = 512$.
관점 바꾸기 (도구 #16): 답 $=$ $512$ $-$ (해가 오직 $x = y = z = 0$ 뿐인 시스템 수).

$$\text{전체} = 2^9 = 512$$

💡 독립인 $9$ 개의 켜고/끄기 스위치 → $2^9$ 가지 행렬.

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

동차 시스템 $A\vec{x} = \vec{0}$ 가 오직 영해만 갖는 것 $\iff$ 행 세 개가 $\mathbb{R}$ 위에서 일차독립 $\iff$ $\det A \ne 0$.
따라서 계수가 $\{0, 1\}$ 이고 행렬식이 $0$ 이 아닌 $3 \times 3$ 행렬 개수를 세는 문제.

$$\text{찾는 값: }\#\{A : \det A \ne 0\}$$

💡 세 식이 영해만 가지려면 어느 행도 다른 행들의 결합이 아니어야 함.

#9 더 쉬운 문제로 줄이기 8.EE.C.8 단계 3

경우 1: 행이 $\mathbb{F}_2$ (mod $2$) 에서 일차독립.
도구 #9 (더 쉬운 문제): mod $2$ 세상에서 각 행은 $8$ 개 벡터 중 하나.
1행은 영행 빼고 $7$ 가지.
2행은 1행의 생성공간 $\{\vec{0}, \text{1행}\}$ 을 피해 $6$ 가지.
3행은 1, 2행의 생성공간 (원소 $4$ 개) 을 피해 $4$ 가지.
따라서 $7 \cdot 6 \cdot 4 = 168$.
($0/1$ 행렬에서 $\det A \bmod 2 = \det A \bmod 2$ 이므로 mod $2$ 독립이면 $\mathbb{R}$ 위에서도 자동 독립.)

$$|\text{GL}_3(\mathbb{F}_2)| = 7 \cdot 6 \cdot 4 = 168$$

💡 mod $2$ 세상에서 $k$ 개 독립 벡터의 생성공간은 정확히 $2^k$ 개 — 하나씩 빼며 곱하기.

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

경우 2: $\mathbb{F}_2$ 에서는 종속이지만 $\mathbb{R}$ 에서는 독립.
이 경우 $\det A$ 가 짝수 ($\mathbb{F}_2$ 에서 행들의 어떤 결합이 $\vec{0}$ 이므로) 이면서 $0$ 이 아니므로 $|\det A| \ge 2$.
$0/1$ 항을 가진 $3 \times 3$ 행렬의 최대 $|\det|$ 는 정확히 $2$ (Hadamard 한계).
따라서 $\det A = \pm 2$.

$$\det A = \pm 2$$

💡 $0/1$ 행렬에서 $0$ 이 아닌 짝수 행렬식은 $\pm 2$ 만 가능.

#2 빠짐없이 나열하기 5.OA.A.1 단계 5

도구 #2 (나열): $\det = \pm 2$ 인 행렬 찾기.
무게 $2$ 인 세 행 $(1,1,0), (1,0,1), (0,1,1)$ 을 어떤 순서로 쓰면, mod $2$ 합이 $(0,0,0)$ 이므로 mod $2$ 종속.
하지만 $\det \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix} = 1(0 - 1) - 1(1 - 0) + 0 = -2$.
이 행렬 (및 행 순서를 바꾼 모든 행렬) 의 $\det = \pm 2$.
$3! = 6$ 가지.

$$\det \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix} = -2$$

💡 각 행이 서로 다른 좌표를 빠뜨린 무게-$2$ 세 행 → $\pm 2$ 행렬식.

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

다른 $0/1$ 행렬에서는 $\det = \pm 2$ 가 안 나옴.
간단 논증: 영행이 있으면 $\det = 0$, 같은 행이 두 번이면 $\det = 0$.
남은 사례를 손으로 확인하면 $\det = \pm 2$ 인 행렬은 위 $\{(1,1,0), (1,0,1), (0,1,1)\}$ 의 $6$ 순열뿐.

$$\#\{\det A = \pm 2\} = 6$$

💡 $\pm 2$ 행렬식 행렬은 "각 열이 한 번씩 빠진 무게-$2$ 세 행" 한 가족뿐.

#16 관점 바꾸기 4.OA.A.3 단계 7

합치기.
$\det A \ne 0$ (영해만 갖는 시스템): $168 + 6 = 174$.
도구 #16 으로 답 $= 512 - 174 = 338$, 즉 $\textbf{(B)}$.

$$512 - 174 = 338$$

💡 전체에서 "오직 영해" 를 빼면 "비자명 해 있음".

[1] #16 8.EE.A.1 전체 공간 계산. $9$ 개 칸이 각각 $0$ 또는 $1$ 이므로 시스템 수 $= 2^9 = 512$. 관점 바꾸기 (도구 #16): 답 $=$

[2] #7 8.EE.C.8 동차 시스템 $A\vec{x} = \vec{0}$ 가 오직 영해만 갖는 것 $\iff$ 행 세 개가 $\mathbb{R}$ 위에서 일차독립 $\

[3] #9 8.EE.C.8 경우 1: 행이 $\mathbb{F}_2$ (mod $2$) 에서 일차독립. 도구 #9 (더 쉬운 문제): mod $2$ 세상에서 각 행은 $8

[4] #7 8.EE.C.8 경우 2: $\mathbb{F}_2$ 에서는 종속이지만 $\mathbb{R}$ 에서는 독립. 이 경우 $\det A$ 가 짝수 ($\mathbb

[5] #2 5.OA.A.1 도구 #2 (나열): $\det = \pm 2$ 인 행렬 찾기. 무게 $2$ 인 세 행 $(1,1,0), (1,0,1), (0,1,1)$ 을 어

[6] #2 5.OA.A.1 다른 $0/1$ 행렬에서는 $\det = \pm 2$ 가 안 나옴. 간단 논증: 영행이 있으면 $\det = 0$, 같은 행이 두 번이면 $\d

[7] #16 4.OA.A.3 합치기. $\det A \ne 0$ (영해만 갖는 시스템): $168 + 6 = 174$. 도구 #16 으로 답 $= 512 - 174 = 33

검토

합리성 확인: 비율 확인: $338 / 512 \approx 66\%$ 의 시스템이 비자명 해를 가짐 — 합리적. 무작위 $0/1$ 행렬은 영행, 같은 행 반복, 행들의 mod $2$ 합이 $\vec{0}$ 등으로 자주 특이행렬이 되니까. 극단 사례: $9$ 개 계수가 모두 $0$ 인 시스템은 모든 $(x, y, z)$ 가 해 — 당연히 $338$ 에 포함됨. 두 식이 같은 시스템도 다수 포함. 선택지 $302, 338, 340, 343, 344$ 가 가까이 모여 있어, $\pm 2$ 행렬 $6$ 개를 잘못 처리하면 $344$ (=$338 + 6$, 중복 계산) 나 $302$ (=$338 - 36$, 무게-$2$ 누락) 로 빠질 수 있음. $338$ 이 깔끔한 답.

대안 접근: 도구 #13 (대수로 바꾸기) — 영행 개수에 따른 직접 경우 나누기. (i) 영행 한 개 이상 ($\det = 0$ 자동), (ii) 모두 비영행이지만 같은 행이 반복, (iii) 세 행이 모두 다르고 비영인데도 일차종속. 지루하지만 $\mathbb{F}_2$ 기법 없이도 $338$ 에 도달.

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

8.EE.A.1 정수 지수의 성질 알고 적용 (전체 $0/1$ 행렬 수를 $2^9 = 512$ 로 계산.)
8.EE.C.8 이원 연립일차방정식 분석·해결 ("비자명 해 존재" 를 "행의 일차종속" 및 "$\det A = 0$" 으로 연결 — 문제의 구조적 뼈대.)
5.OA.A.1 괄호를 이용한 수식 평가 (무게-$2$ 행렬의 행렬식 $1(0 - 1) - 1(1 - 0) + 0 = -2$ 계산.)
4.OA.A.3 네 가지 연산을 이용한 여러 단계 문장제 풀기 ($168 + 6 = 174$, $512 - 174 = 338$ 의 단계별 산수.)

⭐ 전체 $= 2^9 = 512$. "오직 영해" 인 $174$ 개 시스템을 빼기 — mod $2$ 에서 행 독립인 $168$ + mod $2$ 에서는 종속이지만 $\det = \pm 2$ 인 무게-$2$ 행 세 개의 $6$ 순열. 남은 $512 - 174 = 338$ 가 비자명 해를 가짐, 답은 $\textbf{(B)}$.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: B

검토

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

비슷한 유형 더 풀어보기