Intro

Sol Golomb’s Rectangle Puzzle
image/svg+xml

Solomon Golomb, in addition to being a major figure in communication theory and a legendary USC professor, loved puzzles. Besides Cheskers and his creation of polyominoes — which inspired Tetris — he authored Golomb’s Puzzle Column in the IEEE Information Society Newsletter.

hero This original rectangle puzzle ran in the 1996 IEEE newsletter.

Rectangles with Consecutive-Integer Sides

Say you’re given the following challenge: create a set of five rectangles that have sides of length 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10 units. You can combine sides in a variety of ways: for example, you could create a set of rectangles with dimensions 1 x 3, 2 x 4, 5 x 7, 6 x 8 and 9 x 10.

  1. How many different sets of five rectangles are possible?
  2. What are the maximum and minimum values for the total areas of the five rectangles? 

Bonus Challenges

  1. What other values for the total areas of the five rectangles are possible?
  2. Which sets of rectangles may be assembled to form a square?

Solution

  1. The number of distinct sets of rectangles is 945. Pick one of the ten numbers, and you can pair it with nine different partners. In each case, you have eight numbers left, so you can pick one and pair it with seven different partners. Continuing, you can pick one of the remaining six and pair it in five different ways, and so on. So the number of distinct combinations is 9x7x5x3x1, or 945. 
  1. For the maximum area, you cannot do better than 190 for the set consisting of 1×2, 3×4, 5×6, 7×8 and 9×10. The largest side length is 10, and if you do not pair it with the 9, you cannot make up the lost area. For example, 10×9 plus 8×7 equals 146, but 10×8 plus 9×7 is only 143. Continuing, you should next pair the 8 and 7 to get the maximum possible area, then the 6 and 5, and so on.

By converse argument, I think the minimum area is 110 for the set consisting of 1×10, 2×9, 3×8, 4×7 and 5×6.

  1. All numbers between the min and max except for 176, 185, 188 and 189. If you rearrange (1,2), (3,4) from the max of 190 to (1,3), (2,4), you get the next possible highest of 187. If you rearrange them to (1,4), (2,3) you get 186. But 185 is not possible, nor 188 and 189.

To get 111, rearrange (1,10), (2,9) from the min to (1,9), (2,10).

In other words, you can work up from 110 to 111 but not down from 190 to 189: 1 x 10 + 2 x 9 = 10 + 18 = 28, and 1 x 9 + 2 x 10 = 9 + 10 = 29 (a difference of 1); 1 x 2 + 3 x 4 = 2 + 12 = 14, and 1 x 3 + 2 x 4 = 3 + 8 = 11 (a difference of 3). This helped explain with 188 and 185 were also not possible.

 But 176 — this value isn’t possible as well, but why? There doesn’t seem to be an easy explanation. Even Sol Golomb says, “Other than by an enumeration of cases, I have found no simple way to show that 176 cannot be achieved.”

4. We know the square has to have area of 121 (11×11), 144 (12×12) or 169 (13×13), but which can be created, and how? Here are solutions to the 11×11 and 13×13 squares:

(1) 1×2 4×5 3×8 7×9 6×10
2 2 2 2 2 3 3 3 3 3 3 3 3
2 2 2 2 2 3 3 3 3 3 3 3 3
2 2 2 2 2 3 3 3 3 3 3 3 3
2 2 2 2 2 1 1 5 5 5 5 5 5
4 4 4 4 4 4 4 5 5 5 5 5 5
4 4 4 4 4 4 4 5 5 5 5 5 5
4 4 4 4 4 4 4 5 5 5 5 5 5
4 4 4 4 4 4 4 5 5 5 5 5 5
4 4 4 4 4 4 4 5 5 5 5 5 5
4 4 4 4 4 4 4 5 5 5 5 5 5
4 4 4 4 4 4 4 5 5 5 5 5 5
4 4 4 4 4 4 4 5 5 5 5 5 5
4 4 4 4 4 4 4 5 5 5 5 5 5

(2) 1×2 4×6 3×7 8×9 5×10
2 2 2 2 2 2 3 3 3 3 3 3 3
2 2 2 2 2 2 3 3 3 3 3 3 3
2 2 2 2 2 2 3 3 3 3 3 3 3
2 2 2 2 2 2 1 1 5 5 5 5 5
4 4 4 4 4 4 4 4 5 5 5 5 5
4 4 4 4 4 4 4 4 5 5 5 5 5
4 4 4 4 4 4 4 4 5 5 5 5 5
4 4 4 4 4 4 4 4 5 5 5 5 5
4 4 4 4 4 4 4 4 5 5 5 5 5
4 4 4 4 4 4 4 4 5 5 5 5 5
4 4 4 4 4 4 4 4 5 5 5 5 5
4 4 4 4 4 4 4 4 5 5 5 5 5
4 4 4 4 4 4 4 4 5 5 5 5 5

(3) 1×6 4×7 5×8 3×9 2×10
1 1 1 1 1 1 3 3 3 3 3
5 5 2 2 2 2 3 3 3 3 3
5 5 2 2 2 2 3 3 3 3 3
5 5 2 2 2 2 3 3 3 3 3
5 5 2 2 2 2 3 3 3 3 3
5 5 2 2 2 2 3 3 3 3 3
5 5 2 2 2 2 3 3 3 3 3
5 5 2 2 2 2 3 3 3 3 3
5 5 4 4 4 4 4 4 4 4 4
5 5 4 4 4 4 4 4 4 4 4
5 5 4 4 4 4 4 4 4 4 4

(4) 3×6 4×7 2×8 1×9 5×10
1 1 1 1 1 1 5 5 5 5 5
1 1 1 1 1 1 5 5 5 5 5
1 1 1 1 1 1 5 5 5 5 5
3 3 2 2 2 2 5 5 5 5 5
3 3 2 2 2 2 5 5 5 5 5
3 3 2 2 2 2 5 5 5 5 5
3 3 2 2 2 2 5 5 5 5 5
3 3 2 2 2 2 5 5 5 5 5
3 3 2 2 2 2 5 5 5 5 5
3 3 2 2 2 2 5 5 5 5 5
3 3 4 4 4 4 4 4 4 4 4