Competition · AMC preparation · step 4 of 4

AMC 10 · 2022B · #18

Grade 8 algebra

Archetype Branching State Enumeration └ Sub-archetype Rule-Governed Process Simulation

systems-of-equationscomplementary-countingsystematic-enumerationlinear-algebra-basiccasework complementary-countingcaseworkidentify-subproblemseasier-related-problem ↑ Prerequisites: systems-of-equationscomplementary-counting

📏 Long solution 💡 4 insights

Problem

Count the systems of three homogeneous linear equations in x, y, z whose nine coefficients are each 0 or 1 and which have a nonzero solution. Treat each equation's coefficients as an ordered triple, and treat the three equations as an ordered list (order matters; equations may repeat).

Pick an answer.

(A)

302

(B)

338

(C)

340

(D)

343

(E)

344

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

How to solve

Strategy Change Focus / Complement

Tool #16 (Complement): "has a nonzero solution" splits exactly into "rows linearly dependent" — and the opposite (rows linearly independent) is far easier to count, so subtract from 512. Tool #7 (Subproblems): split the linearly-independent count into two sub-cases based on whether the rows are independent over F₂ (the mod-2 world) or independent only over R. Tool #9 (Easier Problem): pretend the entries live in F₂ first — then row independence is a clean "each new row not in span of previous" choice count. Tool #2 (Systematic List): the leftover cases (independent over R but not over F₂) are few enough to enumerate.

1STEP 1

Count all the matrices

Each of the 9 entries is 0 or 1, so there are 2⁹ = 512 systems. Complement: answer = 512 minus the systems whose only solution is all-zero.

Total = 2⁹ = 512

2STEP 2

Restate as a determinant condition

Only-zero-solution means the three rows are independent over R, i.e. det A ≠ 0. So count the 3×3 0/1 matrices with nonzero determinant.

Want: #{A : det A ≠ 0}

3STEP 3

Count the odd determinants

Independent mod 2: row 1 has 7 options, row 2 has 6, row 3 has 4, so 7·6·4 = 168. Mod-2 independence forces real independence here.

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

4STEP 4

Set up the second sub-case

Matrices dependent mod 2 but independent over R have even nonzero determinant; for 3×3 0/1 matrices that forces det A = ±2.

det A = ± 2

5STEP 5

List the determinant 2 matrices

The weight-2 rows (1,1,0), (1,0,1), (0,1,1) sum to zero mod 2 yet give det = −2; their 3! = 6 orderings all have det ±2.

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

6STEP 6

Show no others work

No other 0/1 matrix hits det ±2: zero or repeated rows give det 0, and the remaining cases leave exactly these 6 matrices.

#{det A = ± 2} = 6

7STEP 7

Subtract from the total

Matrices with det ≠ 0 (only-zero-solution): 168 + 6 = 174. So the answer is 512 − 174 = 338, choice (B).

512 - 174 = 338

Answer

338

Sanity-check the proportion:

\frac{338}{512}

≈ 66% of systems have a non-trivial solution. That feels right — most random 0/1 matrices are singular because they include a zero row, a repeated row, or rows summing mod 2 to zero. Quick edge cases: the system with all 9 zero entries has every (x, y, z) as a solution — yes, it's counted. Systems where two equations are identical are also counted (and they're plentiful — by counting, 3 · 8² - … — the 338 count includes all of them). Each of the choices 302, 338, 340, 343, 344 is close together, so an off-by-6 slip in counting det = ± 2 would land on 344 (=338 + 6, double-counting the ± 2 block) or 302 (=338 - 36, dropping all weight-2 matrices). 338 is the cleanly-computed answer.

💡Key takeaway

Total = 2⁹ = 512. Subtract the 174 "only-zero-solution" systems — 168 with rows independent mod 2, plus 6 extra matrices whose rows sum to zero mod 2 but still have det = ± 2. The remaining 512 - 174 = 338 systems have a non-zero solution, choice (B).

Count all the matrices
Restate as a determinant condition
Count the odd determinants
Set up the second sub-case
List the determinant 2 matrices
Show no others work
Subtract from the total

A parent dashboard for the family lives at sensimlab.com.