2022 AMC 10B Problem 18

P16-20~8 minPrint

Systems of Equations Basic Counting Split into exhaustive cases and handle each Count the complement and subtract from the total

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

Show solution without answering

Key insight

A nonzero solution exists exactly when one equation adds nothing new: it is all zeros, it repeats another, or it is the sum of the other two.

Solution

Each equation is fixed by its three coefficients, like $1\,1\,0$ for $x + y = 0$ . There are $2^3 = 8$ possible rows, so there are $8 \times 8 \times 8 = 512$ systems. We sort them by whether some equation "adds nothing new".

Key fact. Two equations in three unknowns never pin down a single answer; there is always a whole line of solutions, including nonzero ones. For example, $x + y = 0$ and $y + z = 0$ are solved by $(1, -1, 1)$ . So if one of the three equations adds no new information, the system has a nonzero solution.

Case 1: some equation is all zeros ( $0 = 0$ ). It says nothing, so only two real equations are left, and there is a nonzero solution. Count systems with at least one zero row: all systems minus those with none, $8^3 - 7^3 = 512 - 343 = 169$ .

Case 2: no zero row, but two equations are the same. Again only two different equations, so there is a nonzero solution. With $7$ nonzero rows there are $7^3 = 343$ systems; those with three different rows number $7 \times 6 \times 5 = 210$ . So $343 - 210 = 133$ systems have a repeat.

Case 3: three different nonzero equations. Solve the first two, then see which third equation still allows a nonzero solution. Up to renaming the letters, every pair of different nonzero rows is one of these:

first two equations	their solutions	rows that these solutions also satisfy
$x = 0,\ y = 0$	$(0, 0, t)$	$100,\ 010,\ 110$
$x = 0,\ x + y = 0$	$(0, 0, t)$	$100,\ 010,\ 110$
$x = 0,\ y + z = 0$	$(0, t, -t)$	$100,\ 011,\ 111$
$x = 0,\ x + y + z = 0$	$(0, t, -t)$	$100,\ 011,\ 111$
$x + y = 0,\ x + y + z = 0$	$(t, -t, 0)$	$001,\ 110,\ 111$
$x + y = 0,\ x + z = 0$	$(t, -t, -t)$	$110,\ 101$ only

(Here $t$ is any number. A row like $011$ is satisfied by $(0, t, -t)$ because $0 + t - t = 0$ .)

So three different nonzero rows share a nonzero solution only when they form one of these groups, where one row is the sum of the other two:
$\{100, 010, 110\},\ \{100, 001, 101\},\ \{010, 001, 011\},\ \{100, 011, 111\},\ \{010, 101, 111\},\ \{001, 110, 111\}.$
That is $6$ groups, and each can be put in $3 \times 2 \times 1 = 6$ orders, giving $36$ systems.

Total. $169 + 133 + 36 = 338$ .

The answer is $\boxed{\textbf{(B)}\ 338}$ .

Why this works

A system like this has only the all-zero answer when its three equations are "truly different", meaning none can be made from the others. So the question is really asking when an equation is redundant: it is empty, it is a copy, or it is the sum of the other two. Order matters and repeats are allowed, so count ordered lists all the way through.

Alternative approach

Count the systems with only the zero solution and subtract from $512$ . The first row can be any of the $7$ nonzero rows and the second any of the $6$ others. The third row must avoid every row that the first two already "produce" (zero, the two rows themselves, and their sum or difference if that is a $0$ - $1$ row). In most cases that rules out $4$ rows, leaving $4$ choices; but when the first two are like $110$ and $101$ (two 1s each), their sum and difference are not $0$ - $1$ rows, only $3$ rows are ruled out, and $5$ choices remain. There are $6$ such ordered pairs out of $42$ . So there are $36 \times 4 + 6 \times 5 = 174$ systems with only the zero solution, and $512 - 174 = 338$ with a nonzero one.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Think of each equation as its coefficient row, one of the $8$ vectors in $\{0,1\}^3$ ; a system is an ordered triple of rows, $8^3 = 512$ in all. Three homogeneous equations have a nonzero solution exactly when the rows are linearly dependent, i.e. one row is a combination of the other two (each equation is a plane through the origin; three such planes share a line iff their normals are coplanar).

Count the dependent triples in three exclusive cases.

A zero row. Then only two real equations remain, and two equations in three unknowns always have a nonzero solution. Triples with at least one row $000$ : $8^3 - 7^3 = 512 - 343 = 169$ .

No zero row, a repeated row. Again only two distinct equations. Ordered triples of nonzero rows that are not all distinct: $7^3 - 7 \cdot 6 \cdot 5 = 343 - 210 = 133$ .

Three distinct nonzero rows, dependent. Suppose $w$ is a combination of $u$ and $v$ . Comparing coordinates where $u$ and $v$ have entries $(1,0)$ , $(0,1)$ , $(1,1)$ forces the coefficients into $\{0, \pm1\}$ , and since $w \ne 0, u, v$ , one row must be the sum of the other two. The sum of two $0$ - $1$ rows is again a $0$ - $1$ row only if they share no $1$ s, giving the sets
$\{100, 010, 110\},\ \{100, 001, 101\},\ \{010, 001, 011\},\ \{100, 011, 111\},\ \{010, 101, 111\},\ \{001, 110, 111\}.$
Six sets, each in $3! = 6$ orders: $36$ .

Total: $169 + 133 + 36 = 338$ .

The answer is $\boxed{\textbf{(B)}\ 338}$ .

Review in the AoPS books

Introduction to Algebra, Chapter 5: Multi-Variable Linear Equations (§5.2, §5.3, §5.6)
Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)
Intermediate Algebra, Chapter 1: Basic Techniques for Solving Equations (§1.4)