This week’s Occupy Math looks at a type of puzzle where you want to fill a rectangle with a shape. We will be using the L-shaped 3-square polyomino, used to fill a 5×9 rectangle below, as our example shape. The goal is to figure out every possible size of rectangle that can be filled with this shape. If you are constructing puzzles for other people — e.g., your students — knowing which problems can be solved gives you an edge. The post will not only solve the problem for our example shape, but also give you tools for doing this for other shapes. The answers, and the tools, are at the bottom if you don’t feel like working through the reasoning.
Begin with something simple.
The first trick for figuring out if a rectangle can be filled with our shape is really simple and a bit clever. The shape has an area of 3 (it is made of 3 1×1 squares). This means any rectangle that is filled with this shape has an area that is a multiple of 3 and so, since 3 is prime, must have one side length that is divisible by 3. Here is the smallest rectangle you can fill with the shape.
Notice that a rectangle with a size of length 1 is too thin to hold copies of the shape so 1×3 (or 1-by-anything) is impossible. That proves that 2×3 is the smallest possible rectangle that can be filled — since 2 is the minimum side length and at least one side length divisible by 3 is required.
Getting 2×3 buys us many other rectangles!
The example below shows how to fill a 6×6 rectangle by stacking different copies of the 2×3 solution.
We can push this a long way to showing that we can fill any rectangle with one side of even length and the other a multiple of 3. First of all, we can use multiple copies of the 2×3 solution to get any even-by-3 rectangle, like this:
Then, those even-by-3 rectangles can be repeated to make even-by-any-multiple-of-3 rectangles, like this:
This leaves only 3×odd rectangles to be considered.
The smallest 3×odd that is not obviously too short is 3×3 — which the picture below shows is impossible for the way the blue shape is placed: the only way to cover the lower left position is with a placement of the red shape that leaves an impossible 3×1 area to fill. There are a couple of other ways to place the first shape, but they all lead to something impossible.
Now consider a rectangle that is 3 by any odd number. Every way of placing the shape in the upper left corner does one of three things (i) do something impossible right away, (ii) shorten the rectangle into a 3-by-two shorter rectangle (this can happen two ways), or (iii) create a 3×1 space that cannot be filled. The picture shows all three cases for a 5×3 rectangle.
The first and last placements of the blue shape can never work — the one that creates an isolated square and the one that creates an unfillable 3×1. The other placement reduces the problem to one that is two shorter. That means that, since 3×3 is impossible, so is 5×3. The fact that 5×3 is impossible means 7×3 is impossible, and so on forever. No 3×odd rectangle can be filled with the shape.
Every other multiple of 3-by-odd can be filled!
The example at the top of the post is 5×9. The picture below is 5× 6.
Now, since we have 5 high by 6 or 9 wide, we can build 5 by any multiple of 3 that is bigger than 3. We already have 6 and 9. The multiples of 6 are all even multiples of 3, and every odd multiple of 3 (bigger than 9) is an even multiple of 3 plus 9. This gives us 5-by-any-multiple-of-3 (except 3 itself) by laying our 6 and 9 wide solutions beside each other.
We already know how to build a 2-by-any multiple-of-3 rectangle. That means that, once we have 5-by-any-multiple-of-3, we can add two more to make 7, then 9, then 11 and so on, by adding the 2×any-multiple-of-3 we already built to the top or bottom of a rectangle we already have. That finishes our logical demonstration. We now know all the dimensions of rectangles that can be filled. DONE!
The answer: which rectangles can be filled?
The pile of logic and pictures above are an example of a proof. What was proved is this: a rectangle can be filled if it is a multiple of 3 on one side and (i) an even number or (ii) any odd number greater than or equal to 5 on the other side. So a 117×125 rectangle can be filled with the shape (do not assign this problem!)
What were the tools we used in the proof?
- The rectangle’s area is a multiple of the piece’s area. This eliminates a lot of possibilities.
- Once we have one solution, we can put copies of it together to make others. This works best with the smallest available solutions.
- Break the problem into different cases or groups. The groups here are multiples of three by even and by odd.
- The trick where we showed 3×3 was impossible and then extended that to 3 by any odd number is a classical method called mathematical induction. This is the hardest part of the reasoning.
- To clean up, we again put together small solutions to get the rest. It’s interesting and convenient that 6 and 9 can be added to make any odd multiple of 3 bigger than 3 itself.
The process of starting with small examples and then, once you sort of see what is going on, breaking the problem into different cases (e.g., odd, even) is a standard approach. It also masks the real difficulty of solving a problem like this: how do you think of the steps? Except maybe for the induction, every step is not hard to follow. The mathematical talent is the imagination to figure out an effective collection of steps.
This raises another important point. Occupy Math is trying hard to write something that is not too hard to follow; his proof is far from the only way to figure out which rectangles can be filled with the 3-square elbow. If you want a simpler version of this problem, ask your students to figure out which rectangles can be filled with copies of a domino (a 2×1 rectangle). The answer is any rectangle where at least one side is of even length; this can be done with a simplified version of the proof used in this post.
Other problems and final comments
While this post shows you how to figure out which rectangles can be filled with a particular shape, there are far more solutions than the ones that arise from the proof. In general, once there is one solution, there are a whole bunch. Even the 3×2 solution has two forms. A earlier Occupy Math showed an interesting variation of this type of puzzle — find examples that cannot be divided into smaller rectangles without breaking one of the pieces.
Look at the two pieces, below. The one on the left can fill rectangles, but in ways that are very different from our example piece, while the one on the right cannot fill rectangles at all (why?)
The proof used to settle exactly which rectangles can be filled is the kind of thing that upper-level math is built on. The problem of filling a rectangle with a shape is from the kind of math called combinatorics, which is one of Occupy Math’s specialties. Even if the proof was a bit too much for you, notice that you now know exactly which rectangles can and cannot be filled with our example shape. This gives you a large number of puzzles for your students or children. Do you have other sorts of puzzles you would like Occupy Math to look at? Please comment or tweet!
I hope to see you here again,
Daniel Ashlock,
University of Guelph,
Department of Mathematics and Statistics
Occupy Math 