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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.