IMO 1990 SL 17

Origin: NET

Problem

Unit cubes are made into beads by drilling a hole through them along a diagonal. The beads are put on a string in such a way that they can move freely in space under the restriction that the vertices of two neighboring cubes are touching. Let A be the beginning vertex and B be the end vertex. Let there be p \times q \times r cubes on the string (p, q, r \geq1). (a) Determine for which values of p, q, and r it is possible to build a block with dimensions p, q, and r. Give reasons for your answers. (b) The same question as (a) with the extra condition that A = B.

Solution

Let us set a coordinate system denoting the vertices of the block. The vertices of the unit cubes of the block can be described as {(x, y, z) | 0 \leq x \leqp, 0 \leqy \leqq, 0 \leqz \leqr}, and we restrict our attention to only these points. Suppose the point A is fixed at (a, b, c). Then for every other necklace point (x, y, z) numbers x −a, y −b, and z −c must be of equal parity. Conversely, every point (x, y, z) such that x−a, y−b, and z −c are of the same parity has to be a necklace point. Consider the graph G whose vertices are all such points and edges are all diagonals of the unit cubes through these points. In part (a) we are looking for an open or closed Euler path, while in part (b) we are looking for a closed Euler path. Necklace points in the interior of the (p, q, r) box have degree 8, points on the surface have degree 4, points on the edge have degree 2, and points on the corner have degree 1. A closed Euler path can be formed if and only if all vertices are of an even degree, while an open Euler path can be formed if and only if exactly two vertices have an odd degree. Hence the problem in part (a) amounts to being able to choose a point A such that 0 or 2 corner vertices are necklace vertices, whereas in part (b) no corner points can be necklace vertices. We distinguish two cases. (i) At least two of p, q, r, say p, q, are even. We can choose a = 1, b = c = 0. In this case none of the corners is a necklace point. Hence a closed Euler path exists. (ii) At most one of p, q, r is even. However one chooses A, exactly two necklace points are at the corners. Hence, an open Euler path exists, but it is impossible to form a closed path. Hence, in part (a), a box can be made of all (p, q, r) and in part (b) only those (p, q, r) where at least two of the numbers are even.