In this post, Occupy Math is going to answer a trick question that we tweeted a while ago. (Williem: thanks for trying so hard.) The trick is that there is no possible answer to the question, sort of a low thing for Occupy Math to do, but it raises a really important point.
You should always include the possibility that a problem cannot be solved.
In math at least, the response to an insoluble problem is to prove, beyond a shadow of a doubt, that no solution exists. While doing this, Occupy Math will also demonstrate the technique of finding a viewpoint from which the problem becomes easier.
Consider the six-wide five-tall arrangement of bricks (well, shaded
rectangles, but we pretend they are bricks) below:
There is no vertical or horizontal line through the configuration that splits it into two smaller rectangles – this means that if these were real bricks there would be no shear lines and so we would get a stronger, more stable array of bricks. We call this property indecomposability and say a configuration like this is indecomposable.
The trick question was to find a six-wide, six-tall arrangement of bricks that is indecomposable.
Our new goal is to show that no such 6×6 arrangement of bricks exists – but let’s work up to it. Consider an arrangement of bricks that is only one high:
If there is more than one brick then it is trivial to find a vertical line that splits the arrangement into two rectangles. Now consider configurations of height two:
If the first brick is vertical, there is a vertical line that splits the arrangement into two rectangles. If we don’t start with a vertical brick then we have to start with two horizontal bricks. These, however, form a square – a type of rectangle – and again a vertical line can divide the arrangement into two rectangles. So, with the exception of “one brick” there are no one-high or two-high indecomposable configurations.
Consider three-high configurations like the one below.
If we start with three horizontal bricks, we can split off the initial 2×3 rectangle so there must be one vertical brick in the first column. This forces a horizontal brick spanning the first two columns (this is shown above). If there is a vertical brick in the second column it completes a rectangle that can be split off – and that rectangle can itself be split. This forces the two horizontal rectangles spanning the second and third column but that forces the second horizontal brick in the bottom row. This situation, two horizontal, one horizontal, and so on, continues until we end with a vertical brick. This, however, causes the entire last row to be a rectangle that can be split off. We conclude that no indecomposable arrangement of bricks can be three-high.
To make a long story short, almost the same thing happens with arrangements that are four bricks high. The only difference is that you get more choices about how to put in the last vertical brick, but avoiding a vertical splitting line forces a horizontal one. So there are also no indecomposable arrangements of height four. This makes the indecomposable arrangement of height five seem really nifty, doesn’t it?
Now for the special point of view that makes things easier
The picture below is the 6×5 indecomposable arrangement, but this time I’ve put the number of bricks that prevent the arrangement from splitting up, in line with each of the potential vertical and horizontal lines where a split might be possible. If you compute these numbers for a configuration that splits, then one of them is zero. Notice also that, since every brick stops one possible split, these numbers add up to the number of bricks. We will call these numbers split prevention numbers. Clear?
Now consider a 6×6 arrangement. Since the space taken up by vertical bricks in the first column must be even, the number of horizontal bricks starting in the first column and going right must also be even. This means the split prevention number for the first two columns is even. The same reasoning, applied to the space remaining in the second column, forces the split prevention number between the second and third column to be even. This continues, and the same logic can be applied to pairs of rows. We can conclude that, for a 6×6 arrangement, all the split prevention numbers are even.
The smallest even number bigger than zero is two – if there were any zeros then the configuration could be split. There are five pairs of rows and five pairs of columns in a 6×6 arrangement where we need to prevent a split. That means that the numbers must be (at least) 2,2,2,2,2,2,2,2,2,2 – ten twos. This means there are 20 bricks, each taking up two squares. That is a total of 40 squares, but a 6×6 arrangement has only 36 squares. We conclude that a 6×6 configuration cannot be indecomposable. So sad!
The take home lesson is that there are problems that don’t have solutions. Your best course of action in this case, is to notice.
To finish the story, for any size bigger than 6×6, in either direction, there is an indecomposable configuration and five-by-anything-even arrangements can all be made indecomposable.
The key to solving this problem was to think of looking at the split prevention numbers – these create the point of view from which the problem is not too hard to solve. This suggests that imagination is a critical skill for mathematics.
Occupy Math will state frankly that resolving today’s trick question is an example of the kind of thing you do as a mathematical researcher. Finding which sizes of arrangements can be made indecomposable is called finding the spectrum of the problem. Please tweet or comment to let us know if you would like more puzzle-posts or if our social justice and numeracy topics are more to your taste.
I hope to see you here again
University of Guelph
Department of Mathematics and Statistics