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 개 인사이트

문제

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

답을 골라 클릭하세요.

(A)

302

(B)

338

(C)

340

(D)

343

(E)

344

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

풀이 과정

전략 관점 바꾸기

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

1STEP 1

9 칸이 각각 0 또는 1 이므로 시스템은 2⁹ = 512 개. 관점 바꾸기: 답 = 512 − (오직 영해만 갖는 수).

전체 = 2⁹ = 512

2STEP 2

오직 영해 ⇔ 세 행이 R 위에서 독립 ⇔ det A ≠ 0. 그래서 행렬식이 0 이 아닌 3×3 0/1 행렬을 셉니다.

찾는 값: #{A : det A ≠ 0}

3STEP 3

mod 2 에서 독립: 1행 7 · 2행 6 · 3행 4 = 168. mod 2 독립이면 R 위에서도 독립.

|GL₃(F₂)| = 7 · 6 · 4 = 168

4STEP 4

mod 2 에서는 종속이나 R 에서 독립이면 행렬식은 0 아닌 짝수 — 3×3 0/1 행렬에선 det A = ±2 뿐.

det A = ± 2

5STEP 5

무게-2 세 행 (1,1,0),(1,0,1),(0,1,1): mod 2 합 0, det = −2; 3! = 6 순열 모두 ±2.

det 1 & 1 & 0 ; 1 & 0 & 1 ; 0 & 1 & 1 = -2

6STEP 6

다른 0/1 행렬은 det ±2 불가: 영행·중복행은 det 0, 나머지 확인하면 이 6 개뿐.

#{det A = ± 2} = 6

7STEP 7

det ≠ 0 (오직 영해): 168 + 6 = 174. 따라서 답 = 512 − 174 = 338, 즉 (B).

512 - 174 = 338

정답

338

비율 확인:

\frac{338}{512}

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

💡핵심 정리

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

비슷한 유형 더 풀어보기