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).

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ See also this question. $\endgroup$
    – Jaap Scherphuis
    Commented Jul 24, 2023 at 6:45
  • $\begingroup$ perhaps this is duplicate then? $\endgroup$
    – Dmitry Kamenetsky
    Commented 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$
    – Jaap Scherphuis
    Commented Jul 24, 2023 at 8:33

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Lovely construction. Four is the definitely the minimum because each polyomino needs three neighbours. $\endgroup$
    – Will.Octagon.Gibson
    Commented Jul 24, 2023 at 2:22
  • 1
    $\begingroup$ I wonder if we can find a smaller polyomino? $\endgroup$
    – Dmitry Kamenetsky
    Commented Jul 24, 2023 at 3:14
  • 1
    $\begingroup$ @DmitryKamenetsky There is an octomino here. $\endgroup$
    – Jaap Scherphuis
    Commented Jul 24, 2023 at 6:46
  • $\begingroup$ oh cool! That must be optimal $\endgroup$
    – Dmitry Kamenetsky
    Commented 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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Very nice! Are there solutions without any inner space? What about smaller polyominoes? $\endgroup$
    – Dmitry Kamenetsky
    Commented 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
    Commented Jul 25, 2023 at 4:42
  • $\begingroup$ If these were physical pieces, would they hold together without falling apart? $\endgroup$
    – Dmitry Kamenetsky
    Commented Jul 25, 2023 at 5:09
  • $\begingroup$ Less white space is possible, see my answer $\endgroup$
    – Dmitry Kamenetsky
    Commented 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
    Commented 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

Improve this answer
$\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.