IMO 2000 SL C2

Origin: ITA | Category: Combinatorics

Problem

A brick staircase with three steps of width 2 is made of twelve unit cubes. Determine all integers n for which it is possible to build a cube of side n using such bricks.

Solution

Since the volume of each brick is 12, the side of any such cube must be divisible by 6. Suppose that a cube of side n = 6k can be built using n3 12 = 18k3 bricks. Set a coordinate system in which the cube is given as [0, n] \times [0, n] \times [0, n] and color in black each unit cube [2p, 2p + 1] \times [2q, 2q + 1] \times [2r, 2r + 1]. There are exactly n3 9 = 27k3 black cubes. Each brick covers either one or three black cubes, which is in any case an odd number. It follows that the total number of black cubes must be even, which implies that k is even. Hence 12 | n. On the other hand, two bricks can be fitted together to give a 2\times3\times4 box. Using such boxes one can easily build a cube of side 12, and consequently any cube of side divisible by 12.