12
$\begingroup$

You are asked to dissect an $N \times N$ square into polyomino pieces such that each piece shares a portion of its boundary with exactly $D$ other pieces, and no piece has area exceeding $N$. This can be achieved for $D \le 5$.

For $D=2, 3, 4$ the smallest such squares are of size $2 \times 2$, $3 \times 3$, $4 \times 4$, respectively:
enter image description here

Find the smallest square for $D=5$.

Credit: inspired by this puzzle.

EDIT / Bounty offer by Will Octagon Gibson:

Two answers have already been posted using 8x8 squares and 16 polyominoes.

I plan to award a bounty of 100 if a correct answer is posted using a smaller square or fewer polyominoes.

I plan to increase the bounty to 200 if a correct answer is posted using a smaller square AND fewer polyominoes.

These offers will expire on November 30, 2023 at approximately 11:59 p.m. (my time).

Good luck!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Wasn't this proven by Gerhard in that other puzzle? $\endgroup$
    – Quark
    Commented Jan 26, 2015 at 7:31
  • 2
    $\begingroup$ That answer is not a square, and it can't be trivially extended to a square, because you will have pieces with an area larger than N. $\endgroup$
    – dmg
    Commented Jan 26, 2015 at 8:39
  • $\begingroup$ @Quark - Gerhard has proven that for $D=5$ you need to dissect into at least 12 pieces. $\endgroup$
    – Johannes
    Commented Jan 26, 2015 at 9:38
  • $\begingroup$ "and no piece has area exceeding N". Is this condition necessary? $\endgroup$
    – Dmitry Kamenetsky
    Commented Sep 17, 2019 at 2:32

3 Answers 3

Reset to default
11
$\begingroup$

I think I've found a solution for an 8x8 square. I do not know if it is the minimum solution or how to prove that:

8x8

It was definitely fun to try and find this! Took me a while. Excellent puzzle.

Some comments on how I got to the solution (Rather a chronology than a full deduction):

- It has been proven in the other puzzle that at least 12 tiles would be needed.
- It was clear, that each piece has to have at least 2 squares.
- I was intuitively convinced that the solution would have a 4-fold rotational symmetry. (No proof for that whatsoever. More a 'feeling'.) So I set out with trying patterns in this symmetry. If I get 1/4th of the pieces in place, the other 3/4th would be correct automatically.
- I figured the rim would be the difficult part, as long-stretched tiles are needed, and their length is limited by the square-size.
- So I first tried to create a 7x7 square with fitting tiles to the border and leaving room for 5 connections.
stp
- This did not work out (because of the symmetry centre being 'left out'). So I then retried the same with a 8x8 grid, ending up with:
Step
- Trying to extend the colours towards the centre (always using 4-fold rotational symmetry on the extensions) I soon ran into obstacles, which forced me to 'shift' the outer rim to:
step
- And then it was just a matter of extending inwards and realizing that the number of tiles is not yet enough. Adding 4 colours did the trick.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Well done. This 16 pieces solution is almost certainly the minimum. There are alternative solutions with fewer pieces, but they typically have a 3-fold symmetry and require 3 pieces to cover the full boundary, thereby violating the requirement of the area not exceeding the linear dimension. Not a proof, but makes it pretty plausible smaller squares won't allow for a solution. $\endgroup$
    – Johannes
    Commented Jan 27, 2015 at 15:05
6
$\begingroup$

It is also possible with rectangles.

square dissection or square dissection

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice. Didn't see those. $\endgroup$
    – BmyGuest
    Commented Jan 27, 2015 at 22:52
2
$\begingroup$

A near miss for $D=5$ and $N=7$, with $12$ polyominoes and largest area $8$ instead of $\le 7$:

enter image description here

The underlying $5$-regular connected planar graph is the icosahedral graph.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 So close! Nice! $\endgroup$
    – Will.Octagon.Gibson
    Commented Nov 25, 2023 at 18:39

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