10
$\begingroup$

You are asked to dissect an $N \times N$ square into polyomino pieces such that each piece shares 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.

|improve this question
$\endgroup$
  • 1
    $\begingroup$ Wasn't this proven by Gerhard in that other puzzle? $\endgroup$ – Quark Jan 26 '15 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 Jan 26 '15 at 8:39
  • $\begingroup$ @Quark - Gerhard has proven that for $D=5$ you need to dissect into at least 12 pieces. $\endgroup$ – Johannes Jan 26 '15 at 9:38
  • $\begingroup$ "and no piece has area exceeding N". Is this condition necessary? $\endgroup$ – Dmitry Kamenetsky Sep 17 at 2:32
9
$\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$
  • $\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 Jan 27 '15 at 15:05
5
$\begingroup$

It is also possible with rectangles.

square dissection or square dissection

|improve this answer
$\endgroup$
  • $\begingroup$ Nice. Didn't see those. $\endgroup$ – BmyGuest Jan 27 '15 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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