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:
Find the smallest square for $D=5$.
Credit: inspired by this puzzle.
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:
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.
- 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:
- 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:
- 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.
It is also possible with rectangles.
or
