The new highway promised a better and faster connection between A and B and a considerable reduction of congestion. Unfortunately there was an obstacle: the old mansion. This conflict was soon resolved in favor of the highway.
Shortly before the demolition of the mansion was about to start, a lover of old mansions found out that the colorfully tiled floors in the mansion were designed by the famous painter Mondriaan,and therefore had great cultural value. They should be saved. They should be removed from the mansion before the mansion will be demolished.
A floor moving expert was hired to accomplish the job. He decided to cut each floor into smaller pieces, in order to make it more tractable. He possessed a fine floor cutting tool which enabled him to cut a rectangular piece of floor into two smaller rectangular pieces, cutting parallel to one of the sides. Of course the cutting should be between tiles; cutting through a tile was not an option. This way the floor in Figure 1 could easily be cut into 9 tiles. The floor in Figure 2 however can not be cut into smaller pieces. The floor in Figure 3 can be cut into six pieces, but one of the parts will consist of several tiles.
While preparing for the job, the floor moving expert was anxious to know how large the remaining pieces could be: would they be heavy, very heavy or extremely heavy? What kind of floor lifting tool should be hired? Because the floors have a fixed thickness, and a fixed density, the weight of a piece of floor only depends upon its area.
Given a rectangular floor covered with rectangular tiles, find the area of the largest piece, after the floor is cut into the smallest possible pieces. The words smallest and largest refer to the area of the pieces. Cutting through a tile is not allowed. A cut through a rectangle is always parallel to one of the sides, and through the full length (or width) of the rectangle.