9
$\begingroup$

Consider a 16x16 square subdivided by grid lines into unit squares. It is easy to completely tile (no overlaps, no gaps) this square with 64 1x4 rectangles. Each 1x4 rectangle in the tiling (no matter whether horizontally or vertically oriented), will be split into two non-empty regions by exactly three grid lines.

For example, see the diagram below where there are three bolded grid lines which each split the red 1x4 rectangle into two non-empty regions. The leftmost and rightmost bolded grid lines each split the 1x4 rectangle into two regions (a unit square and a 1x3 rectangle). The middle bolded grid line splits the 1x4 rectangle into two 1x2 rectangles.

The goal of this puzzle is to completely tile (no overlaps, no gaps) this 16x16 square with 64 1x4 rectangles to maximize the number of grid lines that split at least one 1x4 rectangle into two non-empty regions.

Clarification: You may position a 1x4 rectangle in the position shown in the diagram BUT that is not a requirement.

16x16 grid with one 1x4 tile with three grid lines each splitting the tile into two non-empty regions

$\endgroup$

3 Answers 3

18
$\begingroup$

Below a solution in which every gridline splits at least one 1x4 rectangle into 2 regions:

grid

Edit

Actually, I found an easy pattern that will work on bigger squares as well:

  • white: expandible corner piece.
  • green: default center piece.
  • red area could be filled up however you want, it doesn't matter.

16x16

grid16

20x20

grid20

24x24

grid24

$\endgroup$
2
  • $\begingroup$ +1 Excellent answer; clearly explained and illustrated. $\endgroup$ Commented Apr 28 at 5:02
  • $\begingroup$ Ha! I called it! $\endgroup$
    – PDT
    Commented Apr 29 at 10:35
4
$\begingroup$

Unless I've misunderstood the requirements, the following is optimal:

Every gridline splits at least one rectangle.
A single split is highlighted for each horizontal and vertical gridline:
enter image description here

$\endgroup$
2
$\begingroup$

Via integer linear programming, the maximum is...

30:

  1  1  1  1  2  2  2  2 37 38  3  3  3  3 39 40 
  4  4  4  4  5  5  5  5 37 38  6  6  6  6 39 40 
  7  7  7  7  8  8  8  8 37 38 41 42 43 44 39 40 
  9  9  9  9 10 10 10 10 37 38 41 42 43 44 39 40 
 45 11 11 11 11 12 12 12 12 46 41 42 43 44 47 48 
 45 13 13 13 13 14 14 14 14 46 41 42 43 44 47 48 
 45 15 15 15 15 49 50 51 52 46 16 16 16 16 47 48 
 45 17 17 17 17 49 50 51 52 46 18 18 18 18 47 48 
 19 19 19 19 53 49 50 51 52 54 20 20 20 20 55 56 
 57 58 59 60 53 49 50 51 52 54 21 21 21 21 55 56 
 57 58 59 60 53 22 22 22 22 54 23 23 23 23 55 56 
 57 58 59 60 53 24 24 24 24 54 25 25 25 25 55 56 
 57 58 59 60 61 62 63 64 26 26 26 26 27 27 27 27 
 28 28 28 28 61 62 63 64 29 29 29 29 30 30 30 30 
 31 31 31 31 61 62 63 64 32 32 32 32 33 33 33 33 
 34 34 34 34 61 62 63 64 35 35 35 35 36 36 36 36 
$\endgroup$

Your Answer

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

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