2022 AMC 10B Problem 18

Question

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

or

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

\ 302

\ 338

\ 340

\ 343

\ 344

Answer: B

Concepts:system of equations complementary counting casework

Difficulty rating: 1970

Small hint:

For three distinct nonzero dependent rows, one row is the ordinary sum of two rows with disjoint supports

Big hint:

Count all binary coefficient matrices and subtract nonsingular ones

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 .