17
$\begingroup$

What is the most number of distinct free polyominoes you can form by painting an 8x8 grid in two colours? Here a polyomino is a set of orthogonally adjacent cells of the same colour, so polyominoes of the same colour cannot share an edge. Two free polyominoes are considered distinct if they are not a rigid transformation (translation, rotation, reflection, glide-reflection) of each other. Polyominoes of the same shape, but different colours are not considered distinct.

$\endgroup$
3
  • 5
    $\begingroup$ Please update the description to specify that polyominoes of the same color cannot share an edge and also to clarify whether polyominoes of different colors are considered distinct. $\endgroup$
    – RobPratt
    Commented Mar 12, 2023 at 16:26
  • $\begingroup$ Added the requested clarifications. $\endgroup$ Commented Mar 13, 2023 at 10:44
  • $\begingroup$ Are zero-square polyominoes allowed? $\endgroup$ Commented Mar 13, 2023 at 14:29

3 Answers 3

21
$\begingroup$

I believe 14 15 is the best possible (but I can't quite rule out 16).
Edit: OK, I found a solution with 16. This matches the knapsack upper bound and is definitely optimal:

16:
16

15:
15

14:
14

$\endgroup$
9
  • $\begingroup$ This is very nice work! I am particularly impressed that you got some hexominoes in there. $\endgroup$ Commented Mar 12, 2023 at 5:54
  • 1
    $\begingroup$ @DmitryKamenetsky Thanks. I actually found that 15 is possible. $\endgroup$ Commented Mar 12, 2023 at 6:39
  • $\begingroup$ wow 15 is incredible! There are some big ones (including an 8), so I feel that 16 is possible... $\endgroup$ Commented Mar 12, 2023 at 7:04
  • $\begingroup$ For example a white vertical domino can fit in the bottom right without affecting the count $\endgroup$ Commented Mar 12, 2023 at 7:16
  • 3
    $\begingroup$ @justhalf Think greedy algorithm. You have 1x polyomino with 1 piece, 1 with 2, 2 with 3, 5 with 4 ... so you first take smaller and then go towards bigger ones. You can easily see that 16th will get total area to 64 already so you cannot possibly squeeze one more. $\endgroup$ Commented Mar 13, 2023 at 8:17
12
$\begingroup$

If polyominoes of the same color can share an edge and polyominoes of different colors are considered distinct, the maximum is

19, with 2 each of the 9 free polyominoes of size at most 4, and 1 free pentomino: enter image description here

Under the intended interpretation (polyominoes of the same color cannot share an edge and polyominoes of different colors are not considered distinct), the maximum is

16: enter image description here

If polyominoes of the same color cannot share an edge and polyominoes of different colors are considered distinct, the maximum is

19: enter image description here

$\endgroup$
3
  • 3
    $\begingroup$ As I read the problem I thought that two polyominoes of the same color could not share an edge. Otherwise the restriction to two colors does not matter as your solution shows. This is a good solution to another problem, so +1 $\endgroup$ Commented Mar 12, 2023 at 5:29
  • 1
    $\begingroup$ Actually Ross is correct - that was my original intention of the problem. This solution is still interesting though, so +1. $\endgroup$ Commented Mar 12, 2023 at 5:30
  • $\begingroup$ This is also a great answer, but I am accepting the other one as it was earlier. $\endgroup$ Commented Mar 13, 2023 at 11:29
-3
$\begingroup$

Controversial answer:

You can fit 17 polyominoes in an 8x8 grid actually, since (arguably) there is a polyomino with zero squares.Technically 17 tetrominoes

Credits to @RobPratt for image.

$\endgroup$
4
  • $\begingroup$ According to wikipedia, "A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge" $\endgroup$
    – ACB
    Commented Mar 13, 2023 at 16:18
  • $\begingroup$ @ACB there isn’t a citation, it might be incorrect. $\endgroup$ Commented Mar 13, 2023 at 17:48
  • $\begingroup$ Sorry I've never heard of a polyomino with zero cells $\endgroup$ Commented Mar 13, 2023 at 18:07
  • $\begingroup$ @ACB The OEIS says otherwise. $\endgroup$ Commented May 25, 2023 at 10:29

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.