6
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Can we use a 1*1 rectangle ? After all, 2^0=1. $\endgroup$
    – Hemant Agarwal
    Jun 20 at 11:50
  • $\begingroup$ yes you can use 1x1 $\endgroup$
    – Dmitry Kamenetsky
    Jun 20 at 22:54

2 Answers 2

Reset to default
8
$\begingroup$

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.

enter image description here

Improve this answer
$\endgroup$
4
  • $\begingroup$ Nice! I like it. $\endgroup$
    – Graylocke
    Feb 5, 2021 at 5:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – Deusovi ♦
    Feb 5, 2021 at 5:52
  • $\begingroup$ 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/… $\endgroup$
    – Dmitry Kamenetsky
    Feb 5, 2021 at 5:53
  • 2
    $\begingroup$ 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. $\endgroup$
    – theonetruepath
    Feb 9, 2021 at 11:37
1
$\begingroup$

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.

enter image description here

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is a great start. It is possible to use fewer rectangles though. $\endgroup$
    – Dmitry Kamenetsky
    Feb 5, 2021 at 5:40
  • 2
    $\begingroup$ Intriguing... There is a smaller total that uses a more efficient packing of the area than the most efficient packing of the side lengths..? $\endgroup$
    – Graylocke
    Feb 5, 2021 at 5:43
  • 6
    $\begingroup$ That is correct. This is why I thought this would make a nice puzzle. $\endgroup$
    – Dmitry Kamenetsky
    Feb 5, 2021 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.