IMO 1976 · Problem 3

A rectangular box can be filled completely with unit cubes. If one places as many cubes as possible, each with volume 2, in the box, so that their edges are parallel to the edges of the box, one can fill exactly 40% of the box. Determine the possible dimensions of all such boxes.

Official text of the problem. Official problem paper (PDF)

Answer

The dimensions, up to permutation, are \[ \boxed{2\times3\times5\quad\text{and}\quad2\times5\times6.} \]

Solution

Let the side lengths of the box be \(a,b,c\). They are positive integers: along each edge of the box, the two perpendicular boundary planes force any unit cube meeting that edge in a nonzero segment to contribute a whole unit edge, with its adjacent faces in those planes. These unit edges have disjoint interiors and partition the box edge.

Put \[ s=\sqrt[3]{2},\qquad f(n)=\left\lfloor\frac ns\right\rfloor. \] The larger cubes have side length \(s\). Since the prescribed filled volume is positive, each box dimension is at least \(s\), and therefore \(a,b,c\ge2\).

We first prove that the maximum number of larger cubes is \[ N=f(a)f(b)f(c). \] A rectangular grid attains this number. For the upper bound, place the box at \([0,a]\times[0,b]\times[0,c]\), and assign to a cube with lower corner \((x,y,z)\) the label \[ \left(\left\lfloor\frac xs\right\rfloor, \left\lfloor\frac ys\right\rfloor, \left\lfloor\frac zs\right\rfloor\right). \] Since \(0\le x\le a-s\), the first label has \(f(a)\) possible values; similarly, the other labels have \(f(b)\) and \(f(c)\) possibilities. Two cubes with the same label would have lower coordinates differing by less than \(s\) in every direction, so their interiors would overlap. Thus all labels are distinct, proving the upper bound.

The volume condition now gives \[ 2f(a)f(b)f(c)=\frac25abc. \] Writing \(R(n)=f(n)/n\), we obtain \[ R(a)R(b)R(c)=\frac15. \tag{1} \]

Cubing the endpoints shows that \[ \frac54<s<\frac97. \] Consequently, \[ f(2)=1,\qquad f(3)=2,\qquad f(4)=3,\qquad f(5)=3, \] and, for every positive integer \(n\), \[ R(n)\le\frac1s<\frac45. \tag{2} \]

We also claim that \[ R(n)\ge\frac23 \quad\text{for every integer }n\ge3,\ n\ne5. \tag{3} \] Every such integer can be written as \(n=3u+4v\), where \(u,v\) are nonnegative integers: according to its residue modulo \(3\), use \(n=3u\), \(n=3u+4\), or \(n=3u+8\). Hence, using the inequality \(\lfloor x+y\rfloor\ge\lfloor x\rfloor+\lfloor y\rfloor\), \[ f(n)\ge u f(3)+v f(4) =2u+3v \ge\frac23(3u+4v)=\frac{2n}{3}. \] This proves (3). Together with \(R(5)=3/5\), it implies \[ R(n)\ge\frac35\qquad(n\ge3). \tag{4} \]

If all three dimensions were at least \(3\), then (4) would give \[ R(a)R(b)R(c)\ge\left(\frac35\right)^3 =\frac{27}{125}>\frac15, \] contradicting (1). Thus one dimension is \(2\); relabel so that \(a=2\).

There cannot be a second dimension equal to \(2\), because (2) would then give \[ R(a)R(b)R(c)<\frac12\cdot\frac12\cdot\frac45=\frac15. \] Therefore \(b,c\ge3\), and (1) becomes \[ R(b)R(c)=\frac25. \] If neither \(b\) nor \(c\) were \(5\), (3) would make their product at least \(4/9>2/5\). Thus, after interchanging them if necessary, \(b=5\), and \[ R(c)=\frac23. \]

Since \(f(c)=2c/3\) is an integer, write \(c=3k\), where \(k\) is a positive integer. The equality \(f(3k)=2k\) implies \[ \frac{3k}{s}<2k+1, \] and hence \[ k<\frac{s}{3-2s}<3. \] The last inequality follows from \(s<9/7\). Therefore \(k=1\) or \(2\), giving \(c=3\) or \(6\).

Finally, \(f(6)=4\). The two proposed boxes admit unit-cube tilings, and their maximum filled fractions are respectively \[ \frac{2(1\cdot2\cdot3)}{2\cdot3\cdot5} =\frac25, \qquad \frac{2(1\cdot3\cdot4)}{2\cdot5\cdot6} =\frac25. \] Thus both work, and the classification is complete.

The solution was checked against John Scholes' IMO solution archive (Kalva).