2
$\begingroup$

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)

$\endgroup$
3
  • 1
    $\begingroup$ Please give the source of the problem, together with the one of the (rather roughly explained) solution. Then please make clear which is the question you have. $\endgroup$
    – dan_fulea
    Commented Dec 26, 2021 at 20:31
  • $\begingroup$ The problem is 2017 AIME II #14 $\endgroup$ Commented Dec 26, 2021 at 21:19
  • $\begingroup$ @dan_fulea I added the source. $\endgroup$
    – user3472
    Commented Jan 8, 2022 at 17:25

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This is the answer to "I don't understand why the following solution considers all possible lines. Can someone prove this?" or to the question about the overcounted lines, that should be given exactly...? $\endgroup$
    – dan_fulea
    Commented Dec 26, 2021 at 20:33
  • $\begingroup$ @Hagen von Eitzen can you clarify dan_fulea's question? Also, can you elaborate on your answer? For instance, you can further justify why the same vector (up to sign) holds for all other adjacent points. $\endgroup$
    – user3472
    Commented Jan 8, 2022 at 17:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .