10
$\begingroup$

What is the smallest positive number of polyominoes P, such that

  • You can place grid aligned copies of P without any overlap; and
  • Each polyomino is adjacent to exactly 3 other polyominoes.

Polyominoes must be the same shape, but can be rotated or flipped. Two polyominoes are considered adjacent if they touch at one of their sides (not vertices).

$\endgroup$
3
  • 2
    $\begingroup$ See also this question. $\endgroup$ Jul 24, 2023 at 6:45
  • $\begingroup$ perhaps this is duplicate then? $\endgroup$ Jul 24, 2023 at 8:08
  • 3
    $\begingroup$ It has the same answer, though it is a different question. Theoretically that makes it a duplicate, but I wouldn't insist on it. $\endgroup$ Jul 24, 2023 at 8:33

3 Answers 3

13
$\begingroup$

The minimum number of polyominoes needed is

4

Proof:

enter image description here
This nonomino is the smallest I could find that would work.

$\endgroup$
4
  • $\begingroup$ Lovely construction. Four is the definitely the minimum because each polyomino needs three neighbours. $\endgroup$ Jul 24, 2023 at 2:22
  • 1
    $\begingroup$ I wonder if we can find a smaller polyomino? $\endgroup$ Jul 24, 2023 at 3:14
  • 1
    $\begingroup$ @DmitryKamenetsky There is an octomino here. $\endgroup$ Jul 24, 2023 at 6:46
  • $\begingroup$ oh cool! That must be optimal $\endgroup$ Jul 24, 2023 at 6:59
4
$\begingroup$

Here is an example of 4 octominoes, which I believe is the smallest, and also the most compact:

enter image description here

Here Bass has another octomino, as pointed by @Jaap Scherphuis. The shape of his octomino is easier, however, it takes up more space than this one, according to the number of inner white squares.

$\endgroup$
5
  • $\begingroup$ Very nice! Are there solutions without any inner space? What about smaller polyominoes? $\endgroup$ Jul 24, 2023 at 22:27
  • 1
    $\begingroup$ I dont think it's possible to achieve this with smaller polyominoes or without any white space. $\endgroup$
    – Lezzup
    Jul 25, 2023 at 4:42
  • $\begingroup$ If these were physical pieces, would they hold together without falling apart? $\endgroup$ Jul 25, 2023 at 5:09
  • $\begingroup$ Less white space is possible, see my answer $\endgroup$ Jul 25, 2023 at 5:20
  • 1
    $\begingroup$ If you focus on just the whitespace, you're right. But the overall shape will be bigger, as well as each polyomino. I like your thinking :) $\endgroup$
    – Lezzup
    Jul 25, 2023 at 7:01
1
$\begingroup$

I can reduce the number of inner spaces by 3, by adding 3 cells to each piece in @Lezzup's answer:

enter image description here

$\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.