AHSME 1981 #22 - Number of lines that pass through four distinct points

How many lines in a three dimensional rectangular coordinate system pass through four distinct points of the form $(i, j, k)$ where $i$, $j$, and $k$ are positive integers not exceeding four?

$\text{(A)} \ 60 \qquad \text{(B)} \ 64 \qquad \text{(C)} \ 72 \qquad \text{(D)} \ 76 \qquad \text{(E)} \ 100$

I am interested in knowing why my solution below is incorrect:

Any line in 3D space is characterized by an initial point and a vector.

Starting with an initial point of form $(x, y, z)$ and a vector of $(\Delta x, \Delta y, \Delta z)$ you can get other points on the line by adding the vector to the initial point. Since we are interested in a line that passes through four points, the fourth point on this line will be $(x + 3\Delta x, y + 3\Delta y, z + 3\Delta z)$

You need each of these points to be between 1 and 4 (inclusive). If the initial and final points are within the boundary then all points inbetween will also be.

Thus if, $$1 \leq x\leq 4$$

and $$1 \leq x + 3\Delta x \leq 4$$ then you have the following choices:

$x = 1$ and $\Delta x = 0, 1$

$x = 2$ and $\Delta x = 0$

$x = 3$ and $\Delta x = 0$

$x = 4$ and $\Delta x = 0$

Resulting in a total of $1\cdot2 + 1\cdot1 + 1\cdot1 + 1\cdot1 = 5$ valid for $x$ and $\Delta x$. The same holds true for the $y$ and $z$ cases, resulting in a total of $5^3$ total choices.

However, because the points need to be distinct a vector of $(0, 0, 0)$ is not allowed, and thus we must subtract all cases where $\Delta x = 0$, which make up $(1\cdot1 + 1\cdot1 + 1\cdot1 + 1\cdot1)^3$ cases.

The total is thus $5^3 - 4^3 = 61$. However, the correct answer is 76. Why did I not get the right answer?

You’re assuming that $\Delta x,\Delta y,\Delta z\ge 0$ but that doesn’t cover all of the possibilities. The diagonal that runs from $\langle 1,4,4\rangle$ to $\langle 4,1,1\rangle$, for instance, isn’t covered by any of your cases.

• That adds the case of $x = 4$, $\Delta x = -1, 0$. Which still does not lead to the right answer, however. – 1110101001 Dec 12 '14 at 5:43
• @1110101001: That’s not the only case that it adds. You’re missing every diagonal along which at least one coordinate increases while another decreases. – Brian M. Scott Dec 12 '14 at 5:45
• I don't quite get what you mean. When you add in the cases of $x = 4$ and $\Delta x = -1$ to the others to get a total of 6 cases and then cube it to account for the y and z, are you not including all possibilities? Referring to the table posted by @turkeyhundt I don't see any cases which are not covered by this – 1110101001 Dec 12 '14 at 5:50
• @1110101001: If you're making the calculation that I think you're making, you're now counting some diagonals twice, once from each end. – Brian M. Scott Dec 12 '14 at 5:58
• @1110101001: You're welcome! – Brian M. Scott Dec 12 '14 at 6:08

You can think of it in a physical sense instead of math.

For each pair of opposite faces, there are 16 lines that can go through the $4\times4$ cube perpendicularly. So that's $3\times 16=48$.

And for each pair of diagonally opposite edges, there are 4 lines that will go through 4 lattice points. So that's $6\times 4 = 24$

Then for each opposite pair of vertices there is one line. $4\times 1$

Add them up and you get 76 :)

ETA: Doesn't really address your question, but I think these are all the point vector solutions.

\begin{array}{|c|c|c|} \hline (x,y,z)& (\Delta x, \Delta y, \Delta z) & \text{count}\\ \hline (1,y,z) & (1, 0, 0) & 16\\ \hline (x,1,z) & (0, 1, 0) & 16\\ \hline (x,y,1) & (0, 0, 1) & 16\\ \hline (1,1,z) & (1, 1, 0) & 4\\ \hline (4,1,z) & (-1, 1, 0) & 4\\ \hline (1,y,1) & (1, 0, 1) & 4\\ \hline (4,y,1) & (-1, 0, 1) & 4\\ \hline (x,1,1) & (0, 1, 1) & 4\\ \hline (x,4,1) & (0, -1, 1) & 4\\ \hline (1,1,1) & (1, 1, 1) & 1\\ \hline (1,4,4) & (1, -1, -1) & 1\\ \hline (4,1,4) & (-1, 1, -1) & 1\\ \hline (4,4,1) & (-1, -1, 1) & 1\\ \hline \end{array}

• I am interested as to why my solution was incorrect. I already know the answer and how to get it another way. – 1110101001 Dec 12 '14 at 5:02
• Ah, my bad. Misread the question. – turkeyhundt Dec 12 '14 at 5:02
• It's fine. Still keep your answer up though. – 1110101001 Dec 12 '14 at 5:03

Just reading your solution, when I got to the part about $x = 4$, then $\Delta x = -1$ is a permissible condition and I stopped right there.

Reading a bit further, we can also immediately see that your enumeration is flawed in a second way, which is that the choices of $(x, \Delta x)$, $(y, \Delta y)$, and $(z, \Delta z)$ are not independent of each other, which is what you are assuming when writing $5^3$.

• wouldn't that case already be accounted for with $x=1$ and $\Delta x = 1$ – turkeyhundt Dec 12 '14 at 5:16
• No. For what choices of $(x, y, z)$ and $(\Delta x, \Delta y, \Delta z)$ where none of the $\Delta$ are negative, can you obtain the line passing through $(4,1,1), (3,2,2), (2,3,3), (1,4,4)$? – heropup Dec 12 '14 at 5:20
• Ah yes. I was definitely missing that. – turkeyhundt Dec 12 '14 at 5:21
• Why aren't the choices of (x, dx)... independent of each other? Doesn't the value you choose for (x, dx) have no impact on the others? – 1110101001 Dec 12 '14 at 5:39