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$

Solution:

There are $2^9 =512$ total configurations. Now, we can use complementary counting to determine how many have more than one solution.

If a configuration has $3$ equations which don't contain redundant information, then it has only one solution.

This means every equation has to be different. Also, if any equation has $a,b,c =0,$ then it doesn't provide any information, making it redundant. This means we have $7$ choices for the first equation, $6$ choices for the second, and $5$ choices for the third.

This yields $210$ configurations. However, some configurations may still yield redundant information. If two equations add to the other equation, then there is a redundancy.

There are two cases for this to happen.

Case $1:$ $1$ of the equations has $a,b,c=1,$ another equation has $1$ of the variables being $1$ and the other equation has $2$ variables being $1.$ There are $3$ ways to choose which equation has every variable as $1.$ Then, there are $2$ ways to choose which variables have one variable being $1,$ and this equation has $3$ ways to choose which variable is $1.$ This case has $3\cdot 2\cdot 3=18$ configurations to exclude.

Case $2:$ $1$ of the equations has $2$ variables being $1,$ and the other two equations have only one variable being $1,$ with those variables being different from each other, but one of the variables chosen in the first equation. There are $3$ ways to choose the equation with $2$ variables being $1,$ there are $3$ ways to choose which variables are $1,$ and $2$ ways to choose the order of the other equations. This case has $3\cdot 2\cdot 3=18$ configurations to exclude.

There are a total of $210-18-18=174$ cases which have only one solution. This means $512-174=338$ configurations have multiple solutions, making at least one nonzero.

Thus, the answer is B .

2022 AMC 10B Problem 18

Solution:

Problem 18 in Other Years