AMC 10 · 2022 · #18

Grade 8 algebra

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

📏 Long solution 💡 4 insights

Problem

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.)

Pick an answer.

(A)

302

(B)

338

(C)

340

(D)

343

(E)

344

View mode:

Toolkit + CCSS Solution

Understand

Restated: 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).

Givens: Nine coefficients $a_i, b_i, c_i$ for $i = 1, 2, 3$, each $\in \{0, 1\}$; We want a solution $(x, y, z) \ne (0, 0, 0)$ to exist; Total possible systems = $2^9 = 512$; Choices: (A) $302$, (B) $338$, (C) $340$, (D) $343$, (E) $344$

Unknowns: Number of $3 \times 3$ coefficient matrices with entries in $\{0, 1\}$ whose rows are linearly dependent over $\mathbb{R}$ (so the homogeneous system has a nonzero solution)

Understand

Plan

Primary tool: #16 Change Focus / Complement

Secondary: #7 Identify Subproblems, #9 Solve an Easier Related Problem, #2 Make a Systematic List

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 $\mathbb{F}_2$ (the mod-$2$ world) or independent only over $\mathbb{R}$. Tool #9 (Easier Problem): pretend the entries live in $\mathbb{F}_2$ 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 $\mathbb{R}$ but not over $\mathbb{F}_2$) are few enough to enumerate.

Execute — Answer: B

#16 Change Focus / Complement 8.EE.A.1 Step 1

Count the universe.
Each of $9$ entries is $0$ or $1$, so there are $2^9 = 512$ systems.
By complement (Tool #16): answer $=$ $512$ $-$ (systems whose only solution is $x = y = z = 0$).

$$\text{Total} = 2^9 = 512$$

💡 Nine independent on/off switches give $2^9$ matrices total.

#7 Identify Subproblems 8.EE.C.8 Step 2

A homogeneous system $A\vec{x} = \vec{0}$ has only the zero solution iff the three rows of $A$ are linearly independent over $\mathbb{R}$.
Equivalently, $\det A \ne 0$.
So we need to count $3 \times 3$ matrices with $0/1$ entries and nonzero determinant.

$$\text{Want: }\#\{A : \det A \ne 0\}$$

💡 Three equations have only the zero solution exactly when no row is a combination of the others.

#9 Solve an Easier Related Problem 8.EE.C.8 Step 3

Sub-case 1: rows linearly independent over $\mathbb{F}_2$ (mod $2$).
Tool #9 (easier problem): in mod-$2$ land each row is one of $8$ vectors, but $\vec{0}$ is forbidden as row $1$ — that leaves $7$ choices.
Row $2$ must avoid the span $\{\vec{0}, \text{row 1}\}$ — $6$ choices.
Row $3$ must avoid the span of rows $1, 2$, a $4$-element plane — $4$ choices.
So $7 \cdot 6 \cdot 4 = 168$ matrices.
Over $\mathbb{R}$ these are automatically independent too (mod-$2$ independence implies real independence for $0/1$ matrices because $\det A \equiv \det A \pmod 2$).

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

💡 In mod-$2$ world the span of $k$ independent rows has exactly $2^k$ vectors — line up the choices by elimination.

#7 Identify Subproblems 8.EE.C.8 Step 4

Sub-case 2: rows linearly dependent over $\mathbb{F}_2$ but independent over $\mathbb{R}$.
Such an $A$ has even determinant (because over $\mathbb{F}_2$ the rows sum to $\vec{0}$ in some combination), but $\det A \ne 0$, so $|\det A| \ge 2$.
For $3 \times 3$ matrices with entries in $\{0, 1\}$, the maximum possible $|\det A|$ is exactly $2$ (Hadamard-type bound for $0/1$ entries gives $\le 2$).
So we need $\det A = \pm 2$.

$$\det A = \pm 2$$

💡 Even non-zero determinant for a $0/1$ matrix can only be $\pm 2$ — anything bigger is impossible at this size.

#2 Make a Systematic List 5.OA.A.1 Step 5

Tool #2 (Systematic List): enumerate the $\det = \pm 2$ matrices.
Try the three weight-$2$ rows $(1,1,0), (1,0,1), (0,1,1)$ in some order.
Their sum over $\mathbb{F}_2$ is $(0,0,0)$ — dependent mod $2$.
But $\det \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix} = 1(0 - 1) - 1(1 - 0) + 0 = -2$.
So this matrix (and any row-permutation of it) has $\det = \pm 2$.
There are $3! = 6$ orderings.

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

💡 Three rows each missing a different coordinate combine to a $\pm 2$ determinant.

#2 Make a Systematic List 5.OA.A.1 Step 6

Show no other $0/1$ matrices reach $\det = \pm 2$.
Quick argument: $|\det A| \le \prod \|\text{row}_i\|$.
With $0/1$ rows, max $\|\cdot\| = \sqrt{3}$, and only weight-$2$ or weight-$3$ rows can contribute meaningfully.
Eliminating cases (zero row $\Rightarrow \det = 0$; equal rows $\Rightarrow \det = 0$; checking the small remaining cases by hand) confirms the only $\det = \pm 2$ matrices are the $6$ permutations of $\{(1,1,0), (1,0,1), (0,1,1)\}$.

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

💡 The $\pm 2$ matrices form one tight family — three rows of weight $2$, each row missing a different column.

#16 Change Focus / Complement 4.OA.A.3 Step 7

Combine.
Matrices with $\det A \ne 0$ (only-trivial-solution systems): $168 + 6 = 174$.
By Tool #16 the answer is $512 - 174 = 338$, choice $\textbf{(B)}$.

$$512 - 174 = 338$$

💡 Total minus "only zero solution" leaves "has a non-zero solution."

[1] #16 8.EE.A.1 Count the universe. Each of $9$ entries is $0$ or $1$, so there are $2^9 = 512$

[2] #7 8.EE.C.8 A homogeneous system $A\vec{x} = \vec{0}$ has only the zero solution iff the thr

[3] #9 8.EE.C.8 Sub-case 1: rows linearly independent over $\mathbb{F}_2$ (mod $2$). Tool #9 (ea

[4] #7 8.EE.C.8 Sub-case 2: rows linearly dependent over $\mathbb{F}_2$ but independent over $\m

[5] #2 5.OA.A.1 Tool #2 (Systematic List): enumerate the $\det = \pm 2$ matrices. Try the three

[6] #2 5.OA.A.1 Show no other $0/1$ matrices reach $\det = \pm 2$. Quick argument: $|\det A| \le

[7] #16 4.OA.A.3 Combine. Matrices with $\det A \ne 0$ (only-trivial-solution systems): $168 + 6

Review

Reasonableness: Sanity-check the proportion: $338 / 512 \approx 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 \cdot 8^2 - \dots$ — 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 = \pm 2$ would land on $344$ (=$338 + 6$, double-counting the $\pm 2$ block) or $302$ (=$338 - 36$, dropping all weight-$2$ matrices). $338$ is the cleanly-computed answer.

Alternative: Tool #13 (Convert to Algebra) — direct casework by which rows of $A$ are zero. Sub-cases: (i) one or more zero rows ($\Rightarrow \det = 0$ automatically), (ii) all rows nonzero but with a repeated row, (iii) all rows distinct and nonzero with row-dependence. Tedious enumeration but no $\mathbb{F}_2$ trick required — converges on $338$ as well.

CCSS standards used (min grade 8)

8.EE.A.1 Know and apply the properties of integer exponents (Counting the total number of $0/1$ matrices as $2^9 = 512$.)
8.EE.C.8 Analyze and solve pairs of simultaneous linear equations (Connecting "nonzero solution exists" to row dependence and to $\det A = 0$ — the structural backbone of the problem.)
5.OA.A.1 Use parentheses, brackets, or braces in numerical expressions and evaluate (Evaluating the $3 \times 3$ determinant $1(0 - 1) - 1(1 - 0) + 0 = -2$ for the weight-$2$ matrix.)
4.OA.A.3 Solve multi-step word problems using four operations with whole numbers (Combining counts $168 + 6 = 174$ and computing $512 - 174 = 338$.)

⭐ Total $= 2^9 = 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 = \pm 2$. The remaining $512 - 174 = 338$ systems have a non-zero solution, choice $\textbf{(B)}$.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: B

Review

CCSS standards used (min grade 8)

More like this