Difference between revisions of "2022 AMC 10B Problems/Problem 18"
Phillipzeng (talk | contribs) |
MRENTHUSIASM (talk | contribs) |
||
(8 intermediate revisions by 5 users not shown) | |||
Line 79: | Line 79: | ||
<math>8^3 = 512</math> total systems. Note that no two equations by themselves can force <math>x = y = z = 0</math>. Therefore no system with Equation 1 or with repeated equations can force <math>x = y = z = 0</math>. | <math>8^3 = 512</math> total systems. Note that no two equations by themselves can force <math>x = y = z = 0</math>. Therefore no system with Equation 1 or with repeated equations can force <math>x = y = z = 0</math>. | ||
− | + | '''Case 1:''' Equation 8 (<math>x + y + z = 0</math>) is present. | |
− | Case | + | Case 1a: Equation 8, and two equations from <math>\{5, 6, 7\}</math>. |
There are <math>\binom{3}{2} = 3</math> ways to choose two equations from <math>\{5, 6, 7\}</math> and <math>3! = 6</math> ways to arrange each case. The number of options that force <math>x = y = z = 0</math> is <math>3 \cdot 3! = 18</math>. | There are <math>\binom{3}{2} = 3</math> ways to choose two equations from <math>\{5, 6, 7\}</math> and <math>3! = 6</math> ways to arrange each case. The number of options that force <math>x = y = z = 0</math> is <math>3 \cdot 3! = 18</math>. | ||
− | Case | + | Case 1b: Equation 8, one equation from <math>\{5, 6, 7\}</math>, and one equation from <math>\{2, 3, 4\}</math>. |
There are <math>\binom{3}{1} = 3</math> ways to choose one equation from <math>\{5, 6, 7\}</math>. WLOG let us choose Equation 7. Given <math>x + y + z = 0</math> and <math>y + z = 0</math>, we conclude that <math>x = 0</math>. The third equation can be either <math>y = 0</math> or <math>z = 0</math>. There are <math>3!</math> ways to arrange each case. The number of options that force <math>x = y = z = 0</math> is <math>3 \cdot 2 \cdot 3! = 36</math>. | There are <math>\binom{3}{1} = 3</math> ways to choose one equation from <math>\{5, 6, 7\}</math>. WLOG let us choose Equation 7. Given <math>x + y + z = 0</math> and <math>y + z = 0</math>, we conclude that <math>x = 0</math>. The third equation can be either <math>y = 0</math> or <math>z = 0</math>. There are <math>3!</math> ways to arrange each case. The number of options that force <math>x = y = z = 0</math> is <math>3 \cdot 2 \cdot 3! = 36</math>. | ||
− | Case | + | Case 1c: Equation 8, and two equations from <math>\{2, 3, 4\}</math>. |
There are <math>\binom{3}{2} = 3</math> ways to choose two equations from <math>\{2, 3, 4\}</math> and <math>3! = 6</math> ways to arrange each case. Each of these cases forces <math>x = y = z = 0</math>. <math>3 \cdot 3! = 18</math> total options. | There are <math>\binom{3}{2} = 3</math> ways to choose two equations from <math>\{2, 3, 4\}</math> and <math>3! = 6</math> ways to arrange each case. Each of these cases forces <math>x = y = z = 0</math>. <math>3 \cdot 3! = 18</math> total options. | ||
− | + | '''Case 2:''' Equation 8 is <math>\textbf{not}</math> present, at least one equation from <math>\{5, 6, 7\}</math> is present. | |
− | Case | + | Case 2a: Equations <math>\{5, 6, 7\}</math> are all present. |
There are <math>3!</math> ways to arrange the three equations. <math>6</math> options. | There are <math>3!</math> ways to arrange the three equations. <math>6</math> options. | ||
− | Case | + | Case 2b: Two equations from <math>\{5, 6, 7\}</math> are present. One equation from <math>\{2, 3, 4\}</math> is present. |
There are <math>\binom{3}{2}</math> ways to choose two equations from <math>\{5, 6, 7\}</math>. WLOG let Equations 5 and 6 be in our system: <math>x + y = 0</math> and <math>x + z = 0</math>. Any equation from <math>\{2, 3, 4\}</math> will force <math>x = y = z = 0</math>. There are <math>3!</math> ways to arrange the equations. The number of options that force <math>x = y = z = 0</math> is <math>\binom{3}{2} \cdot \binom{3}{1} \cdot 3! = 54</math>. | There are <math>\binom{3}{2}</math> ways to choose two equations from <math>\{5, 6, 7\}</math>. WLOG let Equations 5 and 6 be in our system: <math>x + y = 0</math> and <math>x + z = 0</math>. Any equation from <math>\{2, 3, 4\}</math> will force <math>x = y = z = 0</math>. There are <math>3!</math> ways to arrange the equations. The number of options that force <math>x = y = z = 0</math> is <math>\binom{3}{2} \cdot \binom{3}{1} \cdot 3! = 54</math>. | ||
− | Case | + | Case 2c: One equation from <math>\{5, 6, 7\}</math> is present. Two equations from <math>\{2, 3, 4\}</math> are present. |
There are <math>\binom{3}{1}</math> ways to choose one equation from <math>\{5, 6, 7\}</math>. WLOG let Equation 5 (<math>x + y = 0</math>) be present. One of the two equations from <math>\{2, 3, 4\}</math> must be Equation 4, <math>z = 0</math>, since it is the only equation that restricts <math>z</math>. The last equation can be either 2 or 3. There are <math>3!</math> ways to arrange the equations. The number of options that force <math>x = y = z = 0</math> is <math>\binom{3}{1} \cdot \binom{2}{1} \cdot 3! = 36</math>. | There are <math>\binom{3}{1}</math> ways to choose one equation from <math>\{5, 6, 7\}</math>. WLOG let Equation 5 (<math>x + y = 0</math>) be present. One of the two equations from <math>\{2, 3, 4\}</math> must be Equation 4, <math>z = 0</math>, since it is the only equation that restricts <math>z</math>. The last equation can be either 2 or 3. There are <math>3!</math> ways to arrange the equations. The number of options that force <math>x = y = z = 0</math> is <math>\binom{3}{1} \cdot \binom{2}{1} \cdot 3! = 36</math>. | ||
− | + | '''Case 3:''' Only equations <math>\{2, 3, 4\}</math> are present. | |
There are <math>3!</math> ways to arrange the three equations. <math>6</math> options. | There are <math>3!</math> ways to arrange the three equations. <math>6</math> options. | ||
Line 115: | Line 115: | ||
~numerophile | ~numerophile | ||
− | ==Solution 3 (Complementary Counting, Linear Dependence, Vector Analysis)== | + | ==Solution 3 (Complementary Counting)== |
+ | |||
+ | The total number of possible systems is <math>2^9 = 512</math>, with <math>8</math> possible sets of coefficients per equation. We will use complementary counting to find the number of systems which only have the solution <math>(0, 0, 0)</math> and subtract that from the total. Similar to what is observed in Solution 2, if any equation is repeated or <math>0x + 0y + 0z = 0</math>, there will only be two or fewer equations for three variables, making one unique solution impossible. Therefore, we must choose <math>3</math> different equations from <math>7</math> possible ones, giving <math>7 \cdot 6 \cdot 5 = 210</math> systems. However, there are two exceptions to consider, which will have more than one solution. The first is of the form <math>x + y + z = 0</math>, <math>x + y = 0</math>, <math>z = 0</math>; the second is of the form <math>x = 0</math>, <math>y = 0</math>, <math>x + y = 0</math>. In both cases, there are <math>3</math> ways to choose the variables in the equations, and then <math>6</math> ways to arrange them, giving <math>2 \cdot 3 \cdot 6 = 36</math> exceptions. Subtracting this gives <math>210 - 36 = 174</math> systems with only one solution, and the answer is then <math>512 - 174 = \boxed{\textbf{(B)}\ 338}</math>. | ||
+ | |||
+ | ~phillipzeng | ||
+ | |||
+ | ==Solution 4 (Complementary Counting, Linear Dependence, Vector Analysis)== | ||
Denote vector <math>\overrightarrow{i} = \left( i_1, i_2, i_3 \right)^T</math> for <math>i \in \left\{ a, b, c \right\}</math>. | Denote vector <math>\overrightarrow{i} = \left( i_1, i_2, i_3 \right)^T</math> for <math>i \in \left\{ a, b, c \right\}</math>. | ||
Line 188: | Line 194: | ||
\] | \] | ||
</cmath> | </cmath> | ||
− | |||
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ||
− | |||
− | |||
− | |||
− | |||
==Video Solution== | ==Video Solution== | ||
Line 205: | Line 206: | ||
~ pi_is_3.14 | ~ pi_is_3.14 | ||
+ | ==Video Solution by Interstigation== | ||
+ | https://youtu.be/Z9qYTUEn3Ig | ||
+ | |||
+ | ~Interstigation | ||
== See Also == | == See Also == | ||
{{AMC10 box|year=2022|ab=B|num-b=17|num-a=19}} | {{AMC10 box|year=2022|ab=B|num-b=17|num-a=19}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 00:22, 24 September 2024
Contents
Problem
Consider systems of three linear equations with unknowns , , and , where each of the coefficients is either or and the system has a solution other than . For example, one such system is with a nonzero solution of . 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 1 (Casework)
Let and
We wish to count the ordered triples of row matrices. We perform casework:
- Exactly two of and are equal.
- All of and are different.
- Exactly one of and is
- The sum of two of and is equal to the third matrix.
- If then
- If then
There are options for Once is chosen, and are uniquely determined.
In this case, we have ordered triples
For there are options for Once is chosen, is uniquely determined, and has options. So, there are ordered triples
Similarly, for each of and there are ordered triples
In this case, we have ordered triples
There are two subcases:
For there are options for and options for So, there are ordered triples
Similarly, for each of and there are ordered triples
In this subcase, we have ordered triples
For
More generally, if consists of one and two 's, then has options, and is uniquely determined. So, there are ordered triples
More generally, if consists of two 's and one then and are uniquely determined. So, there are ordered triples
There are ordered triples
Similarly, for each of and there are ordered triples
In this subcase, we have ordered triples
Together, the answer is
~MRENTHUSIASM
Solution 2 (Complementary Counting)
We will use complementary counting and do casework on the equations.
There are possible equations:
Equation 1:
Equation 2:
Equation 3:
Equation 4:
Equation 5:
Equation 6:
Equation 7:
Equation 8:
We will continue to refer to the equations by their number on this list.
total systems. Note that no two equations by themselves can force . Therefore no system with Equation 1 or with repeated equations can force .
Case 1: Equation 8 () is present.
Case 1a: Equation 8, and two equations from .
There are ways to choose two equations from and ways to arrange each case. The number of options that force is .
Case 1b: Equation 8, one equation from , and one equation from .
There are ways to choose one equation from . WLOG let us choose Equation 7. Given and , we conclude that . The third equation can be either or . There are ways to arrange each case. The number of options that force is .
Case 1c: Equation 8, and two equations from .
There are ways to choose two equations from and ways to arrange each case. Each of these cases forces . total options.
Case 2: Equation 8 is present, at least one equation from is present.
Case 2a: Equations are all present.
There are ways to arrange the three equations. options.
Case 2b: Two equations from are present. One equation from is present.
There are ways to choose two equations from . WLOG let Equations 5 and 6 be in our system: and . Any equation from will force . There are ways to arrange the equations. The number of options that force is .
Case 2c: One equation from is present. Two equations from are present.
There are ways to choose one equation from . WLOG let Equation 5 () be present. One of the two equations from must be Equation 4, , since it is the only equation that restricts . The last equation can be either 2 or 3. There are ways to arrange the equations. The number of options that force is .
Case 3: Only equations are present.
There are ways to arrange the three equations. options.
We add up the cases: total systems force . Thus do not.
~numerophile
Solution 3 (Complementary Counting)
The total number of possible systems is , with possible sets of coefficients per equation. We will use complementary counting to find the number of systems which only have the solution and subtract that from the total. Similar to what is observed in Solution 2, if any equation is repeated or , there will only be two or fewer equations for three variables, making one unique solution impossible. Therefore, we must choose different equations from possible ones, giving systems. However, there are two exceptions to consider, which will have more than one solution. The first is of the form , , ; the second is of the form , , . In both cases, there are ways to choose the variables in the equations, and then ways to arrange them, giving exceptions. Subtracting this gives systems with only one solution, and the answer is then .
~phillipzeng
Solution 4 (Complementary Counting, Linear Dependence, Vector Analysis)
Denote vector for . Thus, we need to count how many vector tuples are linearly dependent.
We do complementary counting.
First, the total number of vector tuples is .
Second, we count how many many vector tuples are linearly independent.
To meet this condition, no vector can be a zero vector .
Next, we do the casework analysis.
Case : Three vectors are all on axes.
In this case, the number of is .
Case : 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 .
Step 2: For two vectors selected in Step 1, we determine which two axes they lie on.
The number of ways is .
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 .
Following from the rule of product, the number of in this case is .
Case : 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 .
Step 2: For the selected vector, we determine which axis it lies on.
The number of ways is .
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 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 .
Following from the rule of product, the number of in this case is .
Case : No vector is on any axis.
In this case, any three distinct vectors are linearly independent. So the number of in this case is .
Putting all cases together, the number of vector tuples that are linearly independent is ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Video Solution
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Video Solution by OmegaLearn Using Casework
~ pi_is_3.14
Video Solution by Interstigation
~Interstigation
See Also
2022 AMC 10B (Problems • Answer Key • Resources) | ||
Preceded by Problem 17 |
Followed by Problem 19 | |
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.