Maths Olympiad Prep

Library / /1060 of 1394

Geometry Difficulty 5.5 AIME, harder Prove it United States

Problem:
Determine the number of unordered triples of distinct points in the 4×4×44 \times 4 \times 4 lattice grid {0,1,2,3}3\{0,1,2,3\}^{3} that are collinear in R3\mathbb{R}^{3} (i.e. there exists a line passing through the three points).

Solution

Solution:
Answer: 376

Define a main plane to be one of the xyxy, yzyz, zxzx planes. Define a space diagonal to be a set of collinear points not parallel to a main plane. We classify the lines as follows:

(a) Lines parallel to two axes (i.e. orthogonal to a main plane). Notice that given a plane of the form v=kv = k, where v{x,y,z},k{0,1,2,3}v \in \{x, y, z\}, k \in \{0,1,2,3\}, there are 8 such lines, four in one direction and four in a perpendicular direction. There are 4×3=124 \times 3 = 12 such planes. However, each line lies in two of these (v,k)(v, k) planes, so there are 8×4×32=48\frac{8 \times 4 \times 3}{2} = 48 such lines. Each of these lines has 4 points, so there are 4 possible ways to choose 3 collinear points, giving 4×48=1924 \times 48 = 192 triplets.

(b) Diagonal lines containing four points parallel to some main plane. Consider a plane of the form (v,k)(v, k), as defined above. These each have 2 diagonals that contain 4 collinear points. Each of these diagonals uniquely determines v,kv, k so these diagonals are each counted once. There are 12 possible (v,k)(v, k) pairs, yielding 12×2×4=9612 \times 2 \times 4 = 96 triplets.

(c) Diagonal lines containing three points parallel to some main plane. Again, consider a plane (v,k)(v, k). By inspection, there are four such lines and one way to choose the triplet of points for each of these lines. This yields 4×12=484 \times 12 = 48 triplets.

(d) Main diagonals. There are four main diagonals, each with 4 collinear points, yielding 4×4=164 \times 4 = 16 triplets.

(e) Space diagonals containing three points. Choose one of the points in the set {1,2}3\{1,2\}^{3} to be the midpoint of the line. Since these 8 possibilities are symmetric, say we take the point (1,1,1)(1,1,1). There are four space diagonals passing through this point, but one is a main diagonal. So each of the 8 points has 3 such diagonals with 3 points each, yielding 8×3=248 \times 3 = 24 ways.

Adding all these yields 192+96+48+16+24=376192 + 96 + 48 + 16 + 24 = 376.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.