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

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 .

2022 AMC 10B Problem 18

Answer: B

Difficulty rating: 1970

Solution:

Problem 18 in Other Years