22nd ASU 1988 Problem 19 A polygonal line connects two opposite vertices of a cube with side 2. Each segment of the line has length 3 and each vertex lies on the faces (or edges) of the cube. What is the smallest number of segments the line can have?
6 Solution Suppose one endpoint of a segment length 3 is at A. Evidently the other end could be at the edge midpoints B, C, D. It could also be on the circular arc connecting B and C (with center O and radius √5). Similarly, it could be on arcs connecting C and D, or B and D. We claim that if X is a point of one of these arcs other than its endpoints, then the only possible segment length 3 with an endpoint at X (and the other endpoint on the surface of the cube) is AX. wlog we can consider X to be on the arc BC. Take axes with origin O, so that A is (0,0,2). Suppose X is (a,b,0) and that the other endpoint of the segment is Y (x,y,z). Then XY 2 = (x-a) 2 + (y-b) 2 + z 2 = a 2 + b 2 + z 2 - x(2a-x) - y(2b-y) = 5 + z 2 - x(2a-x) - y(2b-y). But a, b > 1 since X is not an endpoint of the arc, so (2a-x) and (2b-y) are both positive. Hence -x(2a-x) - y(2b-y) ≤ 0 with equality iff x = y = 0. Similarly, z 2 ≤ 4 with equality iff z = 2. Hence XY 2 ≤ 9 with equality iff Y = A, which proves the claim. Thus if the next link of the polygonal line goes from A to anywhere except B, C, D, then it has to go back to A. So a minimal line must go to B, C, or D. Now from D the line can only go to A or O. For if it goes to Z (x,y,z), then we have DZ 2 = (x-2) 2 + (y-2) 2 + (z-1) 2 ≤ 2 2 + 2 2 + 1 2 = 3 2 with equality iff x = 0, y = 0 and z = 0 or 2. So let us take A as the starting point of the polygonal line. wlog the first segment is AD. Then the second segment must be DO (for a minimal line). Thus the best we can do with 2 segments is to move along an edge. It takes three such moves to get to the opposite corner, and hence at least 6 segments. But it is obvious that it can be done with 6 segments. 22nd ASU 1988 © John Scholes jscholes@kalva.demon.co.uk 6 December 2003 Last corrected/updated 6 Dec 03