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

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

m
Line 34: Line 34:
 
==Solution 3==
 
==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>
 
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 <math>d, e, f</math>. We impose the condition that at least one of <math>a-d</math>, <math>b - e</math>, or <math>c - f</math> be less than <math>1</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), \cdots, (a + 7d, b + 7e, c + 7f)</math>, where <math>a + 7d, b + 7e, c + 7f \le 10</math>, in which case at least one of <math>a + 8d</math>, <math>b + 8e</math>, or <math>c + 8f</math> be greater than 10 to ensure the line does not contain more than 8 points.
  
  

Revision as of 17:07, 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 $d, e, f$. We impose the condition that at least one of $a-d$, $b - e$, or $c - f$ be less than $1$ 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), \cdots, (a + 7d, b + 7e, c + 7f)$, where $a + 7d, b + 7e, c + 7f \le 10$, in which case at least one of $a + 8d$, $b + 8e$, or $c + 8f$ be greater than 10 to ensure the line does not contain more than 8 points.


Video Solution

https://youtu.be/wgaJMSo61_o

~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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_AIME_II_Problems/Problem_14&oldid=209238"