8
$\begingroup$

Suppose a 'Fillomino tiling', much like a completed Fillomino puzzle, consists of a set of polyominoes covering a region without gaps nor overlaps, with no two n-ominoes of the same size touching along an edge. (touching at a finite number of points, e.g. corner-to-corner, is OK)

Most Fillomino puzzles concern tiling a bounded rectangular region, but what about tilings of the infinite square lattice? In such a tiling, what is the largest possible fraction of the plane that can be legally covered with singlet squares ('monominoes')?

Improve this question
$\endgroup$
2
  • $\begingroup$ hexomino's and SE's answers indicate that there's some other constraint making patterns denser than theirs illegal. What is this constraint? $\endgroup$
    – Rosie F
    Commented Jun 11, 2020 at 6:00
  • 1
    $\begingroup$ Both are using the blue squares for singlet monominoes, and yellow for the other component of the tiling. 'Type A' squares are 'illegal' because they have the yellow regions forming monominoes also, touching the surrounding blue monominoes along full edges. In a Fillomino puzzle, this would be equivalent to putting two (or in this case five) 1's adjacent to each other, and is also directly forbidden by the rules above. $\endgroup$
    – Zomulgustar
    Commented Jun 12, 2020 at 19:52

3 Answers 3

Reset to default
11
$\begingroup$

If I've calculated correctly, I think the best fraction that can be achieved is

$\frac{3}{8}$ of the plane

Diagram

We can adopt the following pattern
enter image description here

Reasoning

The shape with the fewest number of tiles which may legally be surrounded by monominoes is the cross. It makes sense then to fill in any intermediary gaps with cross shapes. The resulting figure arises from constructing a checkerboard pattern an converting the colour of every second square on every second row (this is where the counting comes in). Obviously, not a full proof but a reasoned argument.

Proof that $F < \frac{3}{7}$

Let $F$ be the fraction of the plane covered by monominoes and let $G$ be the fraction of the plane covered by tiles which are adjacent to monominoes.
Then each monomino is adjacent to four non-monomino tiles but each non-monomino tile is adjacent to at most three monominoes.
Overall, this means that $G \geq \frac{4F}{3}$ and since $F + G \leq 1$, we must have $$F + \frac{4F}{3} \leq 1 \Rightarrow F \leq \frac{3}{7}$$ A fraction of $\frac{3}{7}$ would mean that almost all non-monomino tiles must be adjacent to three monimonoes which is easily seen to be impossible so this bound cannot be achieved.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I am convinced this is the best pattern, but I'm not so convinced by the reasoning. If there is only one shape other than the monominos, then it can't touch itself so must be fully surrounded by monominos. But as crcrobert's answer shows, why would there need to be only one other shape? If not, it would have to be a combination of dominos and trominos, but it is not immediately obvious to me why that can't possibly give an equal or better solution. $\endgroup$
    – Jaap Scherphuis
    Commented Jun 10, 2020 at 9:47
  • 1
    $\begingroup$ @JaapScherphuis Yes, I keep circling the answer but can't quite pin it down. My thinking is that if you have a connected region composed of multiple polyominoes then it has to be bigger than the cross-shape and you will lose out on your monomino count. I was also wondering if an adjacency count argument would work. You know that each monomino has to be adjacent to four non-monomino tiles and each non-monomino tile must be adjacent to at least one other non-monomino tile. This just about satisfies that. $\endgroup$
    – hexomino
    Commented Jun 10, 2020 at 10:22
  • 1
    $\begingroup$ @JaapScherphuis I've added an argument to show that $F < \frac{3}{7}$. Perhaps a modification of this could get the bound all the way down? $\endgroup$
    – hexomino
    Commented Jun 10, 2020 at 11:17
  • $\begingroup$ Wish I could split the checkmark, as both of your approaches are appealing...will at least hold off until humn can make good on his bounty offer. ^_^ $\endgroup$
    – Zomulgustar
    Commented Jun 11, 2020 at 3:15
  • 1
    $\begingroup$ @humn Yes, I understand, the approach is a lot more involved than I would have suspected. $\endgroup$
    – hexomino
    Commented Jun 11, 2020 at 8:53
9
+100
$\begingroup$

Proof that the pattern found by @hexomino is optimal

Using that colour scheme, polyminos can have the following kind of internal "nodes" (up to symmetry)

polymino nodes

We can immediately notice that:

The "A" node is illegal. illegal A node

Let's make an assumption:

The optimal pattern doesn't use the "B" node.

But then, the highest density that can be achieved is:

1/3, as the "C" and "D" nodes cover 1/2 of the sides of a monomino at the cost of 1 non-monomino node, and "E" and "F" obviously less. at most 1/3 density

As an aside, such a pattern actually exists as well:

A staircase made out of "D"s. staircase infinimono, although the diagonal strips must be terminated at some point to avoid them being "infinimonos".

Since we already know that there's a better density possible, the assumption is false by contradiction.

That means:

The optimal pattern must contain the "B" node.

Every "B" node must be connected to some other node, but it's only legal to connect it to "F" node, or a single place on the "E" node.

all possible connections

The best density we can get when we connect a "B" to an "E" is:

1/3, since no other "B"s can be connected to the same "E", making them together cover all of the sides of a monomino in total, at the cost of two nodes. B connected to E This still holds even if you try to connect other nodes, since we have already shown that they can't contribute to a density above 1/3

Thus, we must connect "B" nodes to "F" nodes. We know already that we can connect up to 4 "B" nodes to a "F". Since no other node can be connected to more than one "B", it's useless to connect one of them to a "F" to get more "B"s, since we would still have at most 4 "B" nodes per "F".

(This point is a bit important, because if any other node could act like a "outlet splitter" to fit more "B" nodes, we could perhaps increase the density. But only the "F" node can fit more than one "B")

This still leaves the possibility of perhaps fitting in a few extra "C", "D", "E" or "F" nodes, but since they can't contribute to a density above 1/3 without fitting in more "B"s (which we have shown is not possible), that would only make the density worse.

Since the case of connecting 4 "B" to an "F" actually is geometrically possible (it tiles), it's the optimum solution.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Wish I could split the checkmark, as both of your approaches are appealing...will at least hold off until humn can make good on his bounty offer. ^_^ One question, though...does your demonstration above account for the possibility that there could be more than one non-monomino* component to the tiling? (*youtube.com/watch?v=8N_tupPBtWQ) $\endgroup$
    – Zomulgustar
    Commented Jun 11, 2020 at 3:15
  • $\begingroup$ @Zomulgustar Yes it does, as it shows that using any non-cross non-monomino makes the density worse. That only holds if the cross tiles though. If the cross didn't tile, most parts of the proof will fall apart. ("If this pattern is possible, it's the best one. And we are lucky that it exists"). Note also that the cross non-monomino can be tiled in many different ways. $\endgroup$
    – SE - stop firing the good guys
    Commented Jun 14, 2020 at 10:31
5
$\begingroup$

As a bound, at least 1/4, based on:

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.