2
$\begingroup$

What is the smallest polyomino P in number of cells, such that

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

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

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 4 polyominoes, all touching seems a trivial possibility even for P=1. Do you mean an infinite amount filling a 2d plane? $\endgroup$
    – Retudin
    Commented Jul 23, 2023 at 14:09
  • $\begingroup$ Sorry I don't understand how 4 monominoes can be all touching. You cant use diagonal touches, only at edges $\endgroup$
    – Dmitry Kamenetsky
    Commented Jul 23, 2023 at 14:30
  • $\begingroup$ Can we extend our polyominoes across an infinite line; can we place an infinite amount of polyominoes? Because then we could just have a $2$x$\infty$ strip of monominoes. $\endgroup$
    – new Q Open Wid
    Commented Jul 23, 2023 at 14:42
  • 1
    $\begingroup$ Can you find a polyomino that doesn't have these features? $\endgroup$
    – Bass
    Commented Jul 23, 2023 at 20:15
  • 1
    $\begingroup$ Can you make the question more clear and understandable? So far your rules are rather vague, and there are many questions about them left waiting to be answered. $\endgroup$
    – new Q Open Wid
    Commented Jul 23, 2023 at 22:01

3 Answers 3

Reset to default
13
$\begingroup$

Assuming (like Retudin's answer) that smallest P means smallest polyomino, and that placements of polyominoes have to be perfectly grid-aligned:

The optimal solution is P=2, with dominoes.

by

domino solution

With monominoes

The reason why a domino solution is optimal is that a finite solution with grid-aligned monominoes is impossible (thanks to @AxiomaticSystem for giving me the idea). Note that if the solution is allowed to be infinite, there are a lot of trivial solutions.

Why? Consider that for every monomino solution, there must be a top row of the solution (that contains at least one monomino). Then we consider one of the monominoes in the top row. Since it must be adjacent to three other monominoes and there cannot be any monominoes above it, both the left and right cells must have a monomino.

Both of these cells are still on the top row, so we can repeat the same argument ad infinitum, getting that every cell in the top row must have a monomino in it. However, this contradicts the premise of the solution being finite. Therefore, a monomino solution is impossible.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ rot13(Jung jbhyq gur gbc ebj bs n zbabzvab fbyhgvba ybbx yvxr?) $\endgroup$
    – AxiomaticSystem
    Commented Jul 23, 2023 at 21:18
  • $\begingroup$ This is a brilliant answer! I didn't even know that was possible. $\endgroup$
    – Dmitry Kamenetsky
    Commented Jul 23, 2023 at 22:48
  • $\begingroup$ I am now wondering if there is a P that only requires 4 copies? Maybe I'll make another puzzle for it $\endgroup$
    – Dmitry Kamenetsky
    Commented Jul 23, 2023 at 22:51
  • $\begingroup$ @DmitryKamenetsky I'm not sure... $K_4$ appears to have some edges that cross each other; it would be akin to forcing diagonal meetings on one diagonal and then the other being blocked off. $\endgroup$
    – new Q Open Wid
    Commented Jul 23, 2023 at 23:00
  • $\begingroup$ made a new puzzle for the new question $\endgroup$
    – Dmitry Kamenetsky
    Commented Jul 23, 2023 at 23:06
7
$\begingroup$

Probably not the intended answer but assuming smallest P means smallest polyomino (not smallest number of polyominos.)

P=1 is possible enter image description here

Improve this answer
$\endgroup$
3
  • $\begingroup$ What if each polyomino has a preconstrained size: for example, monominoes have a size of 1? I have a solution for dominoes, though... $\endgroup$
    – new Q Open Wid
    Commented Jul 23, 2023 at 14:58
  • 1
    $\begingroup$ Even if only grid-aligned placements are considered to be valid, this arrangement could obviously be done using p=4. $\endgroup$
    – Jaap Scherphuis
    Commented Jul 23, 2023 at 15:36
  • $\begingroup$ Great answer. This is a P=4. $\endgroup$
    – Dmitry Kamenetsky
    Commented Jul 23, 2023 at 22:49
7
$\begingroup$

Based on the idea of the answer of new Q Open Wid, here is a much smaller solution with dominoes I have found, using 16 dominoes:

dominoes

It has a very nice symetry to it.

And because I like the idea, here the smallest I get with triominoes (both use 8 triominoes):

triominoes

Edit: Just for fun: below is a figure with monominoes. Every monomino is ajacent to three others. However, as you may noticed, the grid is rolled up a bit :)

monomino

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice work! I had not considered ditching the 'rails' in my answer. $\endgroup$
    – new Q Open Wid
    Commented Jul 24, 2023 at 17:47

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.