Find the number of different lines containing $8$ points

Question

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

I don't understand why the following solution considers all possible lines. Can someone prove this?

Consider a pair of opposite faces of the cube. There are $4$ lines $l_i,1\leq i\leq 4$ with $8$ collinear points on the top face (for example one line contains the points $(i,i-2, 10)$ for $3\leq i\leq 10$). For each of these lines, draw a rectangular plane containing one of the $l_i$'s that is perpendicular to the top face. Each rectangular plane will contain $16$ lines containing $8$ points, $10$ of which are parallel to the top face and $6$ of which run diagonally through the rectangular plane. We can repeat this for each of the $3$ pairs of opposite faces to get $3\cdot 16\cdot 4=192$ possibilities.

The only possibilities that are overcounted are those lines passing through the diagonals of rectangular planes. There are $4$ rectangular planes perpendicular to one pair of opposite faces whose intersection with the top face of the cube contains $8$ points, so $4\cdot 6$ lines were overcounted, giving a total of $192-24 = 168.$

Also, which lines are overcounted exactly? I think one of the diagonals mentioned by the solution contains the points $(i,i-2, 11-i)$ for $3\leq i\leq 10$.

Source: https://artofproblemsolving.com/wiki/index.php/2017_AIME_II_Problems/Problem_14 (refer to solution 2)

Answer 1

For an 8 point line let $(a,b,c)$ be a shortest vector between adjacent points. Then $\gcd(a,b,c)=1$ and the same vector (up to sign) holds for all other adjacent pairs. Then the longest distance is $(7a,7b,7c)$. This is only possible if $a,b,c\in\{-1,0,1\}$. Also, to avoid more than 8 points, the first and last point must be on a suitable face … as desired.

Answer 2

I don't understand why the following solution considers all possible lines. Can someone prove this?

If a line containing exactly $8$ lattice points is parallel to a face of the cube, then the line is parallel to a line containing exactly $8$ lattice points on the face, so every such line is included in the lines written in the given solution.

If a line containing exactly $8$ lattice points is not parallel to the faces, then see case 1 in solution 1 saying

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

This explains that every such line is on a plane which is perpendicular to a face of the cube, and so every such line is included in the lines written in the given solution.

Also, which lines are overcounted exactly? I think one of the diagonals mentioned by the solution contains the points $(i,i-2, 11-i)$ for $3\leq i\leq 10$.

For each rectangular plane, there are four lines passing through a corner of the rectangular plane, and there are two lines which do not pass through any corner. The lines passing through a corner are overcounted, and the lines which do not pass through any corner are not overcounted. Therefore, there are $\dfrac{3\times 4\times 4}{2}=24$ overcounted lines.

The following $24$ lines are overcounted :

• The line containing $(i,i-2, 11-i)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $x-y-2=0$ and on the plane $y+z-9=0$.

• The line containing $(i,i-2, 13-i)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $x-y-2=0$ and on the plane $x+z-13=0$.

• The line containing $(i,i-2, i)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $x-y-2=0$ and on the plane $y-z+2=0$.

• The line containing $(i,i-2, i-2)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $x-y-2=0$ and on the plane $x-z-2=0$.

• The line containing $(i,9-i,11-i)\ (1\leq i\leq 8)$ is overcounted since the line is both on the plane $x+y-9=0$ and on the plane $y-z+2=0$.

• The line containing $(i,9-i,9-i)\ (1\leq i\leq 8)$ is overcounted since the line is both on the plane $x+y-9=0$ and on the plane $x+z-9=0$.

• The line containing $(i,9-i,i+2)\ (1\leq i\leq 8)$ is overcounted since the line is both on the plane $x+y-9=0$ and on the plane $x-z+2=0$.

• The line containing $(i,9-i,i)\ (1\leq i\leq 8)$ is overcounted since the line is both on the plane $x+y-9=0$ and on the plane $y+z-9=0$.

• The line containing $(i,i+2,11-i)\ (1\leq i\leq 8)$ is overcounted since the line is both on the plane $x-y+2=0$ and on the plane $y+z-13=0$.

• The line containing $(i,i+2,9-i)\ (1\leq i\leq 8)$ is overcounted since the line is both on the plane $x-y+2=0$ and on the plane $x+z-9=0$.

• The line containing $(i,i+2,i+2)\ (1\leq i\leq 8)$ is overcounted since the line is both on the plane $x-y+2=0$ and on the plane $x-z+2=0$.

• The line containing $(i,i+2,i)\ (1\leq i\leq 8)$ is overcounted since the line is both on the plane $x-y+2=0$ and on the plane $y-z-2=0$.

• The line containing $(i,13-i,13-i)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $x+y-13=0$ and on the plane $x+z-13=0$.

• The line containing $(i,13-i,11-i)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $x+y-13=0$ and on the plane $y-z-2=0$.

• The line containing $(i,13-i,i)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $x+y-13=0$ and on the plane $y+z-13=0$.

• The line containing $(i,13-i,i-2)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $x+y-13=0$ and on the plane $x-z-2=0$.

• The line containing $(i-2,13-i,11-i)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $y-z-2=0$ and on the plane $x+z-9=0$.

• The line containing $(i,i,i-2)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $y-z-2=0$ and on the plane $x-z-2=0$.

• The line containing $(i,11-i,i-2)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $y+z-9=0$ and on the plane $x-z-2=0$.

• The line containing $(i-2,i-2,11-i)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $y+z-9=0$ and on the plane $x+z-9=0$.

• The line containing $(i,11-i,13-i)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $y-z+2=0$ and on the plane $x+z-13=0$.

• The line containing $(i-2,i-2,i)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $y-z+2=0$ and on the plane $x-z+2=0$.

• The line containing $(i-2,13-i,i)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $y+z-13=0$ and on the plane $x-z+2=0$.

• The line containing $(i,i,13-i)\ (3\leq i\leq 10)$ is overcounted since the line is both on the plane $y+z-13=0$ and on the plane $x+z-13=0$.