2022 AMC 10B Problem 18

Problem 18 of 25IntermediateAlgebra Counting & Probability

Consider systems of three linear equations with unknowns

x,

y,

and

z,

\begin{cases} 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{cases}

where each of the coefficients is either

0

1

and the system has a solution other than

x=y=z=0.

For example, one such system is

\begin{cases} 1 x + 1 y + 0 z & = 0 \\ 0 x + 1 y + 1 z & = 0 \\ 0 x + 0 y + 0 z & = 0 \end{cases}

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

Solution

There are

2^9=512

ordered binary coefficient matrices. A homogeneous system has only the zero solution exactly when its three row vectors are linearly independent, so we count those matrices and subtract. An independent matrix must have three distinct nonzero rows. There are

7\cdot6\cdot5=210

ordered choices of such rows. Among three distinct nonzero binary vectors, dependence occurs exactly when one is the ordinary sum of the other two; the two summands must have disjoint nonempty supports. If the sum has support of size

2,

choose its two coordinates in

3

ways; its summands are the two corresponding unit vectors. If the sum has support of size

3,

choose which one coordinate forms one summand in

3

ways, with the other two coordinates forming the other summand. Thus there are

3+3=6

unordered dependent triples, each with

3!=6

row orders. Hence the number of independent matrices is

210-6\cdot6=174.

The desired number of singular matrices, and therefore of systems with a nonzero solution, is

512-174=338.

Thus, the answer is B .

Answer choices

Solution

More practice