3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That adds the case of $x = 4$, $\Delta x = -1, 0$. Which still does not lead to the right answer, however. $\endgroup$ – 1110101001 Dec 12 '14 at 5:43
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Dec 12 '14 at 5:45
  • $\begingroup$ 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 $\endgroup$ – 1110101001 Dec 12 '14 at 5:50
  • $\begingroup$ @1110101001: If you're making the calculation that I think you're making, you're now counting some diagonals twice, once from each end. $\endgroup$ – Brian M. Scott Dec 12 '14 at 5:58
  • 1
    $\begingroup$ @1110101001: You're welcome! $\endgroup$ – Brian M. Scott Dec 12 '14 at 6:08
2
$\begingroup$

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}

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

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

$\endgroup$
  • $\begingroup$ wouldn't that case already be accounted for with $x=1$ and $\Delta x = 1$ $\endgroup$ – turkeyhundt Dec 12 '14 at 5:16
  • $\begingroup$ 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)$? $\endgroup$ – heropup Dec 12 '14 at 5:20
  • $\begingroup$ Ah yes. I was definitely missing that. $\endgroup$ – turkeyhundt Dec 12 '14 at 5:21
  • $\begingroup$ 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? $\endgroup$ – 1110101001 Dec 12 '14 at 5:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.