You have a rectangular cake of a given length and width, and want to divide it into a certain number of equal-area rectangular pieces. Each cut you make must be parallel to the sides of the cake, and must completely cut one of the existing pieces into two parts. (Therefore, cutting the cake into N pieces will require exactly N-1 cuts.)
You prefer square pieces to those with a larger aspect ratio. (Here, we define the "aspect ratio" of a piece to be the length of its longer side divided by the length of its shorter side.) You should cut the cake in such a way as to minimize the maximum aspect ratio of all the resulting pieces.
For example, if the cake is 2x3, and you want to cut it into six pieces,
you can cut it into six 1x1 pieces.
Each piece has an aspect ratio of 1.0, which is the smallest possible aspect ratio.
Therefore, this solution is optimal.
One way to cut a 5x5 cake into 5 pieces is to first cut it into two pieces of sizes 2x5 and 3x5.
Cut the smaller of these two in half (each of size 2 x 5/2)
and the larger in thirds (each of size 3 x 5/3).
The largest aspect ratio of these five pieces is 3/(5/3) = 1.8.
There is no way to cut this cake into 5 equal-area pieces that all have an aspect ratio of less than 1.8
|