Avoiding Rectangles – 2
The X’s in a grid can become the corners of rectangles with horizontal and vertical sides. The X’s in this first grid form two rectangles. However, the goal is to avoid creating rectangles. The X’s in the second grid are placed to avoid forming any rectangles.
THE CHALLENGE
Place as many X’s as you can in this 4 by 4 grid and avoid creating any rectangles.
EXPLORATION
What is the most you can have for other sizes of grids? Do you see any patterns in your answers?
Notes
THE CHALLENGE
To solve this in general is a very hard, unsolved problem in mathematics. However, that should not keep a student from playing around with it and learning a lot of interesting things along the way.
Suppose the grid has m rows and n columns. In Avoiding Rectangles – 1, we found the following results for the best answers.
1 and 2 rows: We had m + n – 1 X’s
3 rows: We had m + n X’s using a starting diagram for a 3 by 3 grid that looked like the following diagram. Using that diagram, if we had 3 rows with more columns, we can just add a single X in each new column.
The 3 by 3 case required a different look from the 1 and 2 row strategy, and it is tempting to think that the examples with 4 or more rows will also require some new thinking. To state the obvious, we want to create a collection of columns that never share a pair of rows with X’s in them.
One strategy is to fill in everything in the leftmost column except the bottom square, and then the rest of the columns have one X in the bottom row and one X in another row. This will always work and produces (m – 1) + 2 x (m – 1) = 3 x (m – 1) X’s for an m by m square grid. This method for filling in the square can then be extended (by adding a single X in each new column) to anything with m rows to give 3 x (m – 1) + (n – m) = n + 2m – 3 X’s, when m < n. This formula works for all the answers for any size grid (with more than 1 row) so far.
EXPLORATION
Looking for the best answers online shows you can do 12 X’s for the 5 by 5 case (which you can get using the pattern), and then 16 X’s for the 6 by 6 case (shown here).
After that, the numbers starting at 7 by 7 in order are: 21, 24, 29, 34, 39, 45, 52, 56, 61, 67, 74, 81, 88, 96, 105, 108, 115, and 122. Mathematicians have done a lot of interesting explorations for how these work, and your mathematicians can have a lot of fun with it too!
