IMO 1978 SL 14

Origin: VIE

Problem

Prove that it is possible to place 2n(2n + 1) parallelepipedic (rectangular) pieces of soap of dimensions 1 \times 2 \times (n + 1) in a cubic box with edge 2n + 1 if and only if n is even or n = 1. Remark. It is assumed that the edges of the pieces of soap are parallel to the edges of the box.

Solution

We label the cells of the cube by (a1, a2, a3), ai \in{1, 2, . . ., 2n + 1}, in a natural way: for example, as Cartesian coordinates of centers of the cells ((1, 1, 1) is one corner, etc.). Notice that there should be (2n + 1)3 − 2n(2n + 1) \cdot 2(n + 1) = 2n + 1 void cells, i.e., those not covered by any piece of soap. n = 1. In this case, six pieces of soap 1\times2\times2 can be placed on the following positions: [(1, 1, 1), (2, 2, 1)], [(3, 1, 1), (3, 2, 2)], [(2, 3, 1), (3, 3, 2)] and the symmetric ones with respect to the center of the box. (Here [A, B] denotes the rectangle with opposite corners at A, B.) n is even. Each of the 2n + 1 planes Pk = {(a1, a2, k) | ai = 1, . . . , 2n + 1} can receive 2n pieces of soap: In fact, Pk can be partitioned into four n \times (n + 1) rectangles at the corners and the central cell, while an n \times (n + 1) rectangle can receive n/2 pieces of soap. n is odd, n > 1. Let us color a cell (a1, a2, a3) blue, red, or yellow if exactly three, two or one ai respectively is equal to n + 1. Thus there are 1 blue, 6n red, and 12n2 yellow cells. We notice that each piece of soap must contain at least one colored cell (because 2(n+1) > 2n+1). Also, every piece of soap contains an even number (actually, 1 \cdot 2, 1(n + 1), or 2(n + 1)) of cells in Pk. On the other hand, 2n + 1 cells are void, i.e., one in each plane. There are several cases for a piece of soap S: (i) S consists of 1 blue, n + 1 red and n yellow cells; (ii) S consists of 2 red and 2n yellow cells (and no blue cells); (iii) S contains 1 red cell, n+1 yellow cells, and the are rest uncolored; (iv) S contains 2 yellow cells and no blue or red ones. From the descriptions of the last three cases, we can deduce that if S contains r red cells and no blue, then it contains exactly 2 + (n −1)r red ones. (∗) Now, let B1, . . . , Bk be all boxes put in the cube, with a possible exception for the one covering the blue cell: thus k = 2n(2n + 1) if the blue cell is void, or k = 2n(2n + 1) −1 otherwise. Let ri and yi respectively be the numbers of red and yellow cells inside Bi. By (∗) we have y1 + \cdot \cdot \cdot + yk = 2k + (n −1)(r1 + \cdot \cdot \cdot + rk). If the blue cell is void, then r1 + \cdot \cdot \cdot + rk = 6n and consequently y1 + \cdot \cdot \cdot + yk =

4n(2n+1)+6n(n−1) = 14n2 −2n, which is impossible because there are only 12n2 < 14n2−2n yellow cells. Otherwise, r1+\cdot \cdot \cdot+rk \geq5n−2 (because n + 1 red cells are covered by the box containing the blue cell, and one can be void) and consequently y1 + \cdot \cdot \cdot + yk \geq4n(2n + 1)−2+(n−1)(5n−2) = 13n2−3n; since there are n more yellow cells in the box containing the blue one, this counts for 13n2 −2n > 12n2 (n \geq3), again impossible. Remark. The following solution of the case n odd is simpler, but does not work for n = 3. For k = 1, 2, 3, let mk be the number of pieces whose long sides are perpendicular to the plane \pik(ak = n + 1). Each of these mk pieces covers exactly 2 cells of \pik, while any other piece covers n + 1, 2(n + 1), or none. It follows that 4n2 + 4n −2mk is divisible by n + 1, and so is 2mk. This further implies that 2m1 + 2m2 + 2m3 = 4n(2n + 1) is a multiple of n + 1, which is impossible for each odd n except n = 1 and n = 3.