You are given a 15x15 grid and asked to cover it with rectangles whose dimensions are a power of 2. For example you can use rectangles 8x1 and 4x4, but not 2x3. The rectangles must cover every cell of the grid, cannot overlap or be outside the grid. What is the least number of rectangles needed to achieve this covering? Good luck!
This puzzle came from Mathematics Stack Exchange. Note this link contains the answer.
I can cover it with
13 pieces
which can be done like this:
AAAABBC11111111 AAAABBC11111111 AAAABBC11111111 AAAABBC11111111 AAAABBC22222222 AAAABBC22222222 AAAABBC33333333 AAAABBC.XYYZZZZ 77777777XYYZZZZ 88888888XYYZZZZ 88888888XYYZZZZ 99999999XYYZZZZ 99999999XYYZZZZ 99999999XYYZZZZ 99999999XYYZZZZbasically forming four 7x8 rectangles and a monomino at the center, and dividing each of 7x8 into 1x8, 2x8, and 4x8 strips.
Here is a proof of the lower bound of 13:
There are thirteen more red cells than blue cells (69 red and 56 blue), but each rectangle with sides that are powers of two can contain at most one more red cell than blue cell. Therefore, it would take 13 rectangles to tile the whole grid.
Why it works (and how I found it):
First, I started with a simple 1x15 array of numbers:
. This array sums to 4. Every rectangle of numbers with power-of-2 sides sums to at most 1, and negative sums arise with a rectangle consisting of a single negative cell or a rectangle with two cells containing the -2.
I then multiplied the array by itself, creating this array:
.
This new array sums to 16, and the only problematic rectangles with a sum of more than 1 are those created by multiplying a negative-summing rectangle with the square containing -2.
To fix the two-cell rectangles, I reduced the 4 in the middle to a 2. The sum became 14. All the multi-cell rectangles containing the center have a non-positive sum.
I then colored the squares like a checkerboard with white corners, reduced all the white squares by 1, and increased all the black squares by 1. This dealt with all the problematic single-cell rectangles while not affecting the sums of the rectangles with an even number of cells. The sum of the whole array became 13.
Once this array contained only 1s, 0s, and -1s, I removed the numbers and added colors.
Because all the multi-cell rectangles containing the center have a nonpositive sum, the only way to cover the center in a 13-rectangle tiling is with a 1x1 square.
Another proof for the lower bound:
1. There is at least one rectangle that doesn't touch the boundary.
Proof: Colour the central 3x3 (note: 7x7 or 11x11 also work) square with a checker board pattern and observe that any rectangle touching the boundary (of the full 15x15 square) will cover the same number (possibly zero) of black and white squares.
2. There are at least 12 rectangles touching the boundary.
Proof: Any rectangle can cover 0,1,2,4 or 8 squares of any side of the 15x15 square. Therefore each side is touched by at least 4 distinct rectangles. The only rectangles touching more than one side are in the four corners and each of those touches exactly two sides. Therefore to cover the boundary at least 4x4-4 = 12 rectangles are required.
Well... Just using my knowledge of binary... I think the answer is:
16
Because:
Wouldn't 15 be only able to be made up of 8 + 4 + 2 + 1?
And to fit these in, this needs to be in both directions... which makes kind of tartan layers.
