Latest revision as of 18:02, 31 December 2023

Problem

A $10\times10\times10$ grid of points consists of all points in space of the form $(i,j,k)$ , where $i$ , $j$ , and $k$ are integers between $1$ and $10$ , inclusive. Find the number of different lines that contain exactly $8$ of these points.

Solution 1

$Case \textrm{ } 1:$ The lines are not parallel to the faces

A line through the point $(a,b,c)$ must contain $(a \pm 1, b \pm 1, c \pm 1)$ 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 $(1,1,1)$ to $(10,10,10)$ . The lower endpoint of the desired lines must contain both a 1 and a 3, so it can be $(1,1,3), (1,2,3), (1,3,3)$ . If $\textrm{min} > 0$ then the point $(a-1,b-1,c-1)$ will also be on the line for example, 3 applies to the other end.

Accounting for permutations, there are $12$ ways, so there are $12 \cdot 4 = 48$ different lines for this case.

$Case \textrm{ } 2:$ The lines where the $x$ , $y$ , or $z$ is the same for all the points on the line.

WLOG, let the $x$ value stay the same throughout. Let the line be parallel to the diagonal from $(1,1,1)$ to $(1,10,10)$ . For the line to have 8 points, the $y$ and $z$ must be 1 and 3 in either order, and the $x$ value can be any value from 1 to 10. In addition, this line can be parallel to 6 face diagonals. So we get $2 \cdot 10 \cdot 6 = 120$ possible lines for this case.

The answer is, therefore, $120 + 48 = \boxed{168}$

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 $4$ lines say $l_1, l_2, l_3, l_4$ with exactly $8$ collinear points on the top face. For each of these lines, draw a rectangular plane that consists of one of the $l_i$ for $1 \leq i \leq 4$ and perpendicular to the top face.

There are $16$ lines in total on this plane. $10$ of which are parallel to one of the edges of the rectangular plane and $6$ of which are diagonals. There are $3$ pairs of opposite faces. So $3 \cdot 4 \cdot 16=192$ lines.

But we are overcounting the lines of the diagonals of those rectangular planes twice. There are $4$ rectangular planes perpendicular to one pair of opposite faces. Thus $4 \cdot 6=24$ lines are overcounted.

So the answer is $192-24=\boxed{168}$ .

Solution by phoenixfire

Solution 3

Considered the cases $(1, 2, ..., 8), (2, 3, ...,9), (3, 4, ..., 10)$ and reverse. Also, consider the constant subsequences of length 8 $(1, 1, ..., 1), (2, 2, ..., 2), ..., (10, 10, ..., 10)$ . Of all the triplets that work they cannot be extended to form another point on the line in the $10 \times 10 \times 10$ grid but we need to divide by 2 because reversing all the subsequences gives the same line. Thus the answer is $\frac{16^3 - 14^3 - 14^3 + 12^3}{2} = \boxed{168}$

Solution 4

The lines can be defined as starting from $(a, b, c)$ with "slope" (vector) $(d, e, f)$ . We impose the condition that at least one of $a - d, b - e, \textrm{ or } c - f$ is outside the range of $[1, 10]$ in order to ensure that $(a, b, c)$ is the first valid point on this line. Then, the line ranges from $(a, b, c), (a + d, b + e, c + f), \ldots, (a + 7d, b + 7e, c + 7f)$ , where $1 \le a + 7d, b + 7e, c + 7f \le 10$ , in which case at least one of $a + 8d, b + 8e, \textrm{ or } c + 8f$ is outside of the range $[1, 10]$ to ensure the line does not contain more than 8 points. For $1 \le a + 7d, b + 7e, c + 7f \le 10$ to be satisfied, the pairs $(a, d), (b, e), \textrm{ and } (c, f)$ can only be $(1, 0), (2, 0), \ldots (10, 0), (1, 1), (2, 1), (3, 1), (10, -1), (9, -1), \textrm{ and } (8, -1)$ . Notice that there are only two pairs such that $a + 8d, b + 8e, \textrm{ or } c + 8f \not \in [1, 10]$ , namely $(3, 1)$ and $(8, -1)$ . Thus, our line must contain at least one of these two pairs. In addition, only the two pairs $(1, 1)$ and $(10, -1)$ satisfy $a - d, b - e, \textrm{ or } c - f \not \in [1, 10]$ . 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 $(3, 1)$ and $(8, -1)$ , and 2 ways to choose from $(1, 1)$ and $(10, -1)$ . Then, there are 2 ways to choose the repeated pair. Next, we can arrange these pairs $3!/2! = 3$ ways. So, we have $2 \cdot 2 \cdot 2 \cdot 3 = 24.$

Case 2: We use 3 distinct important pairs

There are ${4 \choose 3}$ ways to choose the pairs (note that by pigeonhole principle, this guarantees we get at least one of each required pair). Then, there are $3! = 6$ ways to arrange it. We obtain $4 \cdot 6 = 24$ .

Case 3: We use 3 unique pairs, one that is not important.

Again, there are $2 \cdot 2 = 4$ ways to choose the important pairs. Then, there are 12 ways to choose the non-important pair. Again, there are $3! = 6$ ways to arrange it. So, we get $4 \cdot 12 \cdot 6 = 288$ .

Summing all of it up and dividing by two (since we over counted each line and its reversal), we get $\frac{24 + 24 + 288}{2} = \boxed{168}.$

~CrazyVideoGamez

Video Solution

https://youtu.be/wgaJMSo61_o

~MathProblemSolvingSkills.com

@@ 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.
-==Solution==
+==Solution 1==
-The easiest way to see the case where the lines are not parallel to the faces, is that 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.
+<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
-We look at the one from <math>(0,0,0)</math> to <math>(10,10,10)</math>. The lower endpoint of the desired lines must contain both a 0 and a 2 (if min > 0 then the point <math>(a-1,b-1,c-1)</math> will also be on the line for example, 2 applies to the other end), so it can be <math>(0,0,2), (0,1,2), (0,2,2)</math>. Accounting for permutations this is 12 ways, so 12*4 = 48 for this case. The answer is, therefore, <math>120 + 48 = \boxed{168}</math>
 =See Also=
 {{AIME box|year=2017|n=II|num-b=13|num-a=15}}
 {{MAA Notice}}

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

Page

Toolbox

Search

Difference between revisions of "2017 AIME II Problems/Problem 14"