Difference between revisions of "2017 AIME II Problems/Problem 14"
(→Solution) |
(→Solution 4) |
||
(8 intermediate revisions by 3 users not shown) | |||
Line 2: | Line 2: | ||
A <math>10\times10\times10</math> grid of points consists of all points in space of the form <math>(i,j,k)</math>, where <math>i</math>, <math>j</math>, and <math>k</math> are integers between <math>1</math> and <math>10</math>, inclusive. Find the number of different lines that contain exactly <math>8</math> of these points. | A <math>10\times10\times10</math> grid of points consists of all points in space of the form <math>(i,j,k)</math>, where <math>i</math>, <math>j</math>, and <math>k</math> are integers between <math>1</math> and <math>10</math>, inclusive. Find the number of different lines that contain exactly <math>8</math> of these points. | ||
− | ==Solution== | + | ==Solution 1== |
− | The | + | <math>Case \textrm{ } 1:</math> The lines are not parallel to the faces |
+ | |||
+ | A line through the point <math>(a,b,c)</math> must contain <math>(a \pm 1, b \pm 1, c \pm 1)</math> on it as well, as otherwise, the line would not pass through more than 5 points. This corresponds to the 4 diagonals of the cube. | ||
+ | |||
+ | We look at the one from <math>(1,1,1)</math> to <math>(10,10,10)</math>. The lower endpoint of the desired lines must contain both a 1 and a 3, so it can be <math>(1,1,3), (1,2,3), (1,3,3)</math>. If <math>\textrm{min} > 0</math> then the point <math>(a-1,b-1,c-1)</math> will also be on the line for example, 3 applies to the other end. | ||
+ | |||
+ | Accounting for permutations, there are <math>12</math> ways, so there are <math>12 \cdot 4 = 48</math> different lines for this case. | ||
+ | |||
+ | |||
+ | |||
+ | <math>Case \textrm{ } 2:</math> The lines where the <math>x</math>, <math>y</math>, or <math>z</math> is the same for all the points on the line. | ||
+ | |||
+ | WLOG, let the <math>x</math> value stay the same throughout. Let the line be parallel to the diagonal from <math>(1,1,1)</math> to <math>(1,10,10)</math>. For the line to have 8 points, the <math>y</math> and <math>z</math> must be 1 and 3 in either order, and the <math>x</math> value can be any value from 1 to 10. In addition, this line can be parallel to 6 face diagonals. So we get <math>2 \cdot 10 \cdot 6 = 120</math> possible lines for this case. | ||
+ | |||
+ | The answer is, therefore, <math>120 + 48 = \boxed{168}</math> | ||
+ | |||
+ | Solution by stephcurry added to the wiki by Thedoge edited by Rapurt9 and phoenixfire | ||
+ | |||
+ | ==Solution 2== | ||
+ | Look at one pair of opposite faces of the cube. There are <math>4</math> lines say <math>l_1, l_2, l_3, l_4</math> with exactly <math>8</math> collinear points on the top face. For each of these lines, draw a rectangular plane that consists of one of the <math>l_i</math> for <math>1 \leq i \leq 4</math> and perpendicular to the top face. | ||
+ | |||
+ | There are <math>16</math> lines in total on this plane. <math>10</math> of which are parallel to one of the edges of the rectangular plane and <math>6</math> of which are diagonals. There are <math>3</math> pairs of opposite faces. So <math>3 \cdot 4 \cdot 16=192</math> lines. | ||
+ | |||
+ | But we are overcounting the lines of the diagonals of those rectangular planes twice. There are <math>4</math> rectangular planes perpendicular to one pair of opposite faces. Thus <math>4 \cdot 6=24</math> lines are overcounted. | ||
+ | |||
+ | So the answer is <math>192-24=\boxed{168}</math>. | ||
+ | |||
+ | Solution by phoenixfire | ||
+ | |||
+ | ==Solution 3== | ||
+ | Considered the cases <math>(1, 2, ..., 8), (2, 3, ...,9), (3, 4, ..., 10)</math> and reverse. Also, consider the constant subsequences of length 8 <math>(1, 1, ..., 1), (2, 2, ..., 2), ..., (10, 10, ..., 10)</math>. Of all the triplets that work they cannot be extended to form another point on the line in the <math>10 \times 10 \times 10</math> grid but we need to divide by 2 because reversing all the subsequences gives the same line. Thus the answer is <cmath> \frac{16^3 - 14^3 - 14^3 + 12^3}{2} = \boxed{168} </cmath> | ||
+ | |||
+ | ==Solution 4== | ||
+ | The lines can be defined as starting from <math>(a, b, c)</math> with "slope" (vector) <math>(d, e, f)</math>. We impose the condition that at least one of <math>a - d, b - e, \textrm{ or } c - f</math> is outside the range of <math>[1, 10]</math> in order to ensure that <math>(a, b, c)</math> is the first valid point on this line. Then, the line ranges from <math>(a, b, c), (a + d, b + e, c + f), \ldots, (a + 7d, b + 7e, c + 7f)</math>, where <math>1 \le a + 7d, b + 7e, c + 7f \le 10</math>, in which case at least one of <math>a + 8d, b + 8e, \textrm{ or } c + 8f</math> is outside of the range <math>[1, 10]</math> to ensure the line does not contain more than 8 points. For <math>1 \le a + 7d, b + 7e, c + 7f \le 10</math> to be satisfied, the pairs <math>(a, d), (b, e), \textrm{ and } (c, f)</math> can only be <math>(1, 0), (2, 0), \ldots (10, 0), (1, 1), (2, 1), (3, 1), (10, -1), (9, -1), \textrm{ and } (8, -1)</math>. Notice that there are only two pairs such that <math>a + 8d, b + 8e, \textrm{ or } c + 8f \not \in [1, 10]</math>, namely <math>(3, 1)</math> and <math>(8, -1)</math>. Thus, our line must contain at least one of these two pairs. In addition, only the two pairs <math>(1, 1)</math> and <math>(10, -1)</math> satisfy <math>a - d, b - e, \textrm{ or } c - f \not \in [1, 10]</math>. Thus, we must also include at least one of these two pairs as well. Let us call these 4 pairs "important" pairs. Finally, we can include any valid pair for our third pair. | ||
+ | |||
+ | Case 1: We repeat one of the important pairs | ||
+ | |||
+ | There are 2 ways to choose from <math>(3, 1)</math> and <math>(8, -1)</math>, and 2 ways to choose from <math>(1, 1)</math> and <math>(10, -1)</math>. Then, there are 2 ways to choose the repeated pair. Next, we can arrange these pairs <math>3!/2! = 3</math> ways. So, we have <math>2 \cdot 2 \cdot 2 \cdot 3 = 24.</math> | ||
+ | |||
+ | Case 2: We use 3 distinct important pairs | ||
+ | |||
+ | There are <math>{4 \choose 3}</math> ways to choose the pairs (note that by pigeonhole principle, this guarantees we get at least one of each required pair). Then, there are <math>3! = 6</math> ways to arrange it. We obtain <math>4 \cdot 6 = 24</math>. | ||
+ | |||
+ | Case 3: We use 3 unique pairs, one that is not important. | ||
+ | |||
+ | Again, there are <math>2 \cdot 2 = 4</math> ways to choose the important pairs. Then, there are 12 ways to choose the non-important pair. Again, there are <math>3! = 6</math> ways to arrange it. So, we get <math>4 \cdot 12 \cdot 6 = 288</math>. | ||
+ | |||
+ | Summing all of it up and dividing by two (since we over counted each line and its reversal), we get <math>\frac{24 + 24 + 288}{2} = \boxed{168}.</math> | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php?title=User:Crazyvideogamez CrazyVideoGamez] | ||
+ | |||
+ | ==Video Solution== | ||
+ | |||
+ | https://youtu.be/wgaJMSo61_o | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
+ | |||
+ | |||
− | |||
=See Also= | =See Also= | ||
{{AIME box|year=2017|n=II|num-b=13|num-a=15}} | {{AIME box|year=2017|n=II|num-b=13|num-a=15}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 17:02, 31 December 2023
Problem
A grid of points consists of all points in space of the form , where , , and are integers between and , inclusive. Find the number of different lines that contain exactly of these points.
Solution 1
The lines are not parallel to the faces
A line through the point must contain on it as well, as otherwise, the line would not pass through more than 5 points. This corresponds to the 4 diagonals of the cube.
We look at the one from to . The lower endpoint of the desired lines must contain both a 1 and a 3, so it can be . If then the point will also be on the line for example, 3 applies to the other end.
Accounting for permutations, there are ways, so there are different lines for this case.
The lines where the , , or is the same for all the points on the line.
WLOG, let the value stay the same throughout. Let the line be parallel to the diagonal from to . For the line to have 8 points, the and must be 1 and 3 in either order, and the value can be any value from 1 to 10. In addition, this line can be parallel to 6 face diagonals. So we get possible lines for this case.
The answer is, therefore,
Solution by stephcurry added to the wiki by Thedoge edited by Rapurt9 and phoenixfire
Solution 2
Look at one pair of opposite faces of the cube. There are lines say with exactly collinear points on the top face. For each of these lines, draw a rectangular plane that consists of one of the for and perpendicular to the top face.
There are lines in total on this plane. of which are parallel to one of the edges of the rectangular plane and of which are diagonals. There are pairs of opposite faces. So lines.
But we are overcounting the lines of the diagonals of those rectangular planes twice. There are rectangular planes perpendicular to one pair of opposite faces. Thus lines are overcounted.
So the answer is .
Solution by phoenixfire
Solution 3
Considered the cases and reverse. Also, consider the constant subsequences of length 8 . Of all the triplets that work they cannot be extended to form another point on the line in the grid but we need to divide by 2 because reversing all the subsequences gives the same line. Thus the answer is
Solution 4
The lines can be defined as starting from with "slope" (vector) . We impose the condition that at least one of is outside the range of in order to ensure that is the first valid point on this line. Then, the line ranges from , where , in which case at least one of is outside of the range to ensure the line does not contain more than 8 points. For to be satisfied, the pairs can only be . Notice that there are only two pairs such that , namely and . Thus, our line must contain at least one of these two pairs. In addition, only the two pairs and satisfy . Thus, we must also include at least one of these two pairs as well. Let us call these 4 pairs "important" pairs. Finally, we can include any valid pair for our third pair.
Case 1: We repeat one of the important pairs
There are 2 ways to choose from and , and 2 ways to choose from and . Then, there are 2 ways to choose the repeated pair. Next, we can arrange these pairs ways. So, we have
Case 2: We use 3 distinct important pairs
There are ways to choose the pairs (note that by pigeonhole principle, this guarantees we get at least one of each required pair). Then, there are ways to arrange it. We obtain .
Case 3: We use 3 unique pairs, one that is not important.
Again, there are ways to choose the important pairs. Then, there are 12 ways to choose the non-important pair. Again, there are ways to arrange it. So, we get .
Summing all of it up and dividing by two (since we over counted each line and its reversal), we get
Video Solution
~MathProblemSolvingSkills.com
See Also
2017 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 13 |
Followed by Problem 15 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.