Problem of the Week 894

A Lattice Optimization Problem

Form a 7 x 8 rectangle on a sheet of graph paper; it has 56 squares. Cut the rectangle into pieces by cutting only along the lines of the grid, in such a way that each piece consists of 1, 2, 3, 4, or 5 squares. But minimize the total length of all the cuts.

For example, if you were to cut it into 56 single squares, the total cuts would amount to: (7*7) + (6*8) = 97 units. This is the worst way to do it.

Source: Quantum: Sept./Oct. 1999

© Copyright 1999 Stan Wagon. Reproduced with permission.

4 October 1999