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.
$\begingroup$
$\endgroup$
3
asked Mar 12 at 0:22
-
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$– RobPrattMar 12 at 16:26
-
$\begingroup$ Added the requested clarifications. $\endgroup$– Dmitry KamenetskyMar 13 at 10:44
-
$\begingroup$ Are zero-square polyominoes allowed? $\endgroup$– The Empty String PhotographerMar 13 at 14:29
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
9
I believe
1415 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:
15:
14:
-
$\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
$\begingroup$
$\endgroup$
3
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:
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:
If polyominoes of the same color cannot share an edge and polyominoes of different colors are considered distinct, the maximum is
19:
-
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
$\begingroup$
$\endgroup$
4
Controversial answer:
You can fit 17 polyominoes in an 8x8 grid actually, since (arguably) there is a polyomino with zero squares.
Credits to @RobPratt for image.
answered Mar 13 at 14:12
-
$\begingroup$ According to wikipedia, "A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge" $\endgroup$– ACBMar 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
-