Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2022 AMC 10B Problems/Problem 18

Revision as of 21:16, 17 November 2022 by Tigerbw (talk | contribs)

Problem

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

Solution (Linear dependence, vector analysis)

Denote vector $\overrightarrow{i} = \left( i_1, i_2, i_3 \right)^T$ for $i \in \left\{ a, b, c \right\}$. Thus, we need to count how many vector tuples $\left( \overrightarrow{a} , \overrightarrow{b} , \overrightarrow{c} \right)$ are linearly dependent.

We do complementary counting.

First, the total number of vector tuples $\left( \overrightarrow{a} , \overrightarrow{b} , \overrightarrow{c} \right)$ is $\left( 2^3 \right)^3 = 512$.

Second, we count how many many vector tuples $\left( \overrightarrow{a} , \overrightarrow{b} , \overrightarrow{c} \right)$ are linearly independent.

To meet this condition, no vector can be a zero vector $\overrightarrow{0} = \left( 0, 0, 0 \right)^T$.

Next, we do the casework analysis.

Case $1^c$: Three vectors are all on axes.

In this case, the number of $\left( \overrightarrow{a} , \overrightarrow{b} , \overrightarrow{c} \right)$ is $3!$.

Case $2^c$: Two vectors are on axes and the third vector is not.

We construct such an instance in the following steps.

Step 1: We determine which two vectors lie on axes.

The number of ways is 3.

Step 2: For two vectors selected in Step 1, we determine which two axes they lie on.

The number of ways is $3 \cdot 2$.

Step 3: For the third unselected vector, we determine its value.

To make three vectors linear independent, the third vector cannot be on the plane formed by the first two vectors. So the number of ways is 3.

Following from the rule of product, the number of $\left( \overrightarrow{a} , \overrightarrow{b} , \overrightarrow{c} \right)$ in this case is $3 \cdot 3 \cdot 2 \cdot 3$.

Case $3^c$: One vector is on an axis and the other two are not.

We construct such an instance in the following steps.

Step 1: We determine which vector lies on an axis.

The number of ways is 3.

Step 2: For the selected vector, we determine which axis it lies on.

The number of ways is 3.

Step 3: We determine the values of the two unselected vectors.

First, to be linearly independent, these two vectors are distinct. Second, to be linearly independent, we cannot have one vector $(1,1,1)$ and another one that is a diagonal vector on the plane that is perpendicular to the first selected vector.

Thus, the number or ways in this step is $4 \cdot 3-2 = 10$.

Following from the rule of product, the number of $\left( \overrightarrow{a} , \overrightarrow{b} , \overrightarrow{c} \right)$ in this case is $3 \cdot 3 \cdot 10$.

Case $(4.4)^c$: No vector is on any axis.

In this case, any three distinct vectors are linearly independent. So the number of $\left( \overrightarrow{a} , \overrightarrow{b} , \overrightarrow{c} \right)$ in this case is $4 \cdot 3 \cdot 2$.

Putting all cases together, the number of vector tuples $\left( \overrightarrow{a} , \overrightarrow{b} , \overrightarrow{c} \right)$ that are linearly independent is \[ 8^3 - 3! - 3 \cdot 3 \cdot 2 \cdot 3 - 3 \cdot 3 \cdot 10 - 4 \cdot 3 \cdot 2 = \boxed{\textbf{(B) 338}}. \]

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Video Solution

https://youtu.be/pDYFn26LND0

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

See Also

2022 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 16 		Followed by
Problem 18
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_AMC_10B_Problems/Problem_18&oldid=182121"