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
    Mar 12, 2023 at 16:26
  • $\begingroup$ Added the requested clarifications. $\endgroup$ Mar 13, 2023 at 10:44
  • $\begingroup$ Are zero-square polyominoes allowed? $\endgroup$ 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$ Mar 12, 2023 at 5:54
  • 1
    $\begingroup$ @DmitryKamenetsky Thanks. I actually found that 15 is possible. $\endgroup$ 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$ Mar 12, 2023 at 7:04
  • $\begingroup$ For example a white vertical domino can fit in the bottom right without affecting the count $\endgroup$ 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$ 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$ 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$ 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$ 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
    Mar 13, 2023 at 16:18
  • $\begingroup$ @ACB there isn’t a citation, it might be incorrect. $\endgroup$ Mar 13, 2023 at 17:48
  • $\begingroup$ Sorry I've never heard of a polyomino with zero cells $\endgroup$ Mar 13, 2023 at 18:07
  • $\begingroup$ @ACB The OEIS says otherwise. $\endgroup$ May 25, 2023 at 10:29

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .