AMC 10 · 2022 · #18
Grade 8 algebraPick an answer.
AMC 10 2022 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
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.
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.
Nine independent on/off switches give 2⁹ matrices total.
8.EE.A.1Count The ComplementOnly-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.
Three equations have only the zero solution exactly when no row is a combination of the others.
8.EE.C.8Identify SubproblemsIndependent 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.
In mod-2 world the span of k independent rows has exactly 2^k vectors — line up the choices by elimination.
8.EE.C.8Solve An Easier Related ProblemMatrices dependent mod 2 but independent over R have even nonzero determinant; for 3×3 0/1 matrices that forces det A = ±2.
Even non-zero determinant for a 0/1 matrix can only be ± 2 — anything bigger is impossible at this size.
8.EE.C.8Identify SubproblemsThe 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.
Three rows each missing a different coordinate combine to a ± 2 determinant.
5.OA.A.1Make A Systematic ListNo other 0/1 matrix hits det ±2: zero or repeated rows give det 0, and the remaining cases leave exactly these 6 matrices.
The ± 2 matrices form one tight family — three rows of weight 2, each row missing a different column.
5.OA.A.1Make A Systematic ListMatrices with det ≠ 0 (only-zero-solution): 168 + 6 = 174. So the answer is 512 − 174 = 338, choice (B).
Total minus "only zero solution" leaves "has a non-zero solution."
4.OA.A.3Count The ComplementTotal = 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).