# Covering a 15x15 grid with rectangles

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.

• Can we use a 1*1 rectangle ? After all, 2^0=1. Jun 20, 2023 at 11:50
• yes you can use 1x1 Jun 20, 2023 at 22:54
• If you don't use the 1x1 then you can't cover an odd number of squares. So you have to Feb 17 at 12:35

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
99999999XYYZZZZ

basically forming four 7x8 rectangles and a monomino at the center, and dividing each of 7x8 into 1x8, 2x8, and 4x8 strips.

• Nice! I like it. Feb 5, 2021 at 5:51
• Cool! I wonder if there's a nice way to prove this optimal... I can get a lower bound of 12 but don't quite see a nice way to show there's a 13th piece.
– Deusovi
Feb 5, 2021 at 5:52
• You got it! Well done. I thought it would take longer to find this, but you proved me wrong. The puzzle came from Mathematics StackExchange, which contains some interesting generalizations: math.stackexchange.com/questions/3173523/… Feb 5, 2021 at 5:53
• I ran a complete search, it can't be done with 12. Method: Find all sums of relevant areas that give 225, use that list to set the maximum number of rectangles of each area, simple backtracking placement of up to 12 rectangles. 16 hours 45 minutes, 16.7 billion rectangles placed. Feb 9, 2021 at 11:37
• @theonetruepath I found a proof that 13 rectangles are required by hand. Feb 16 at 0:17

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.

• Nice. It may be easier to read if you also attach a coloured image like in the accepted answer. Feb 16 at 4:04
• Nice! To really complete the proof, one should also proof your property about every rectangle. Feb 16 at 6:54
• @KrisVanBael Completed. Feb 17 at 0:50
• Let me also give credit where it is due: I got this idea from the following answer. puzzling.stackexchange.com/questions/90269/… Feb 20 at 22:20
• Feb 23 at 17:09

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.

• This is a great proof! It mixes my coloring idea with a geometric argument to create a really short and elegant proof. (The inner rectangle must be the center cell, by the way.) Feb 17 at 18:00
• @mathlander Thanks! I came up with it partly because I don't understand what makes your proof tick -- the colouring pattern and the number 13 seem to come just out of the blue -- which is cool in its own way. Feb 18 at 8:20
• This is also an elegant proof! Nice work, loopy Feb 21 at 23:48

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.

• This is a great start. It is possible to use fewer rectangles though. Feb 5, 2021 at 5:40
• Intriguing... There is a smaller total that uses a more efficient packing of the area than the most efficient packing of the side lengths..? Feb 5, 2021 at 5:43
• That is correct. This is why I thought this would make a nice puzzle. Feb 5, 2021 at 5:47