[math-fun] Loose dissection with pentominos
Here's a new type of polyomino problem that came up as a practical problem. Fit the twelve pentominoes, each made of 1" squares, on a standard 8.5" by 11" sheet, so there is at least a 1/4" border between every pentomino and its neighbors, and the edge of the paper. In other words, pentominoes never touch each other, or the border of the paper. Note that given the spacing constraint, no pentomino is allowed to be inside the concave space of the U pentomino. It's easy to fit 11 pieces, but 12 is challenging. It should be fairly straightforward to write a solver, but the loose fitting constraint does make things trickier. I did a find a solution by hand...which cannot be compressed to fit on a smaller sheet. The next question is what is the smallest area that can fit all 12 pentominoes with quarter inch spacing?
How is that different from a tight packing on a slightly smaller paper with slightly larger squares? On Tue, May 21, 2019 at 12:17 PM Scott Kim <scottekim1@gmail.com> wrote:
Here's a new type of polyomino problem that came up as a practical problem.
Fit the twelve pentominoes, each made of 1" squares, on a standard 8.5" by 11" sheet, so there is at least a 1/4" border between every pentomino and its neighbors, and the edge of the paper. In other words, pentominoes never touch each other, or the border of the paper. Note that given the spacing constraint, no pentomino is allowed to be inside the concave space of the U pentomino.
It's easy to fit 11 pieces, but 12 is challenging. It should be fairly straightforward to write a solver, but the loose fitting constraint does make things trickier. I did a find a solution by hand...which cannot be compressed to fit on a smaller sheet. The next question is what is the smallest area that can fit all 12 pentominoes with quarter inch spacing? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
On 2019-05-21 11:20, Mike Stay wrote:
How is that different from a tight packing on a slightly smaller paper with slightly larger squares?
In at least one way: In the "quarter inch spacing" model, two adjacent squares in a single pentomino don't have the larger distance.
On Tue, May 21, 2019 at 12:17 PM Scott Kim <scottekim1@gmail.com> wrote:
Here's a new type of polyomino problem that came up as a practical problem.
Fit the twelve pentominoes, each made of 1" squares, on a standard 8.5" by 11" sheet, so there is at least a 1/4" border between every pentomino and its neighbors, and the edge of the paper. In other words, pentominoes never touch each other, or the border of the paper. Note that given the spacing constraint, no pentomino is allowed to be inside the concave space of the U pentomino.
It's easy to fit 11 pieces, but 12 is challenging. It should be fairly straightforward to write a solver, but the loose fitting constraint does make things trickier. I did a find a solution by hand...which cannot be compressed to fit on a smaller sheet. The next question is what is the smallest area that can fit all 12 pentominoes with quarter inch spacing? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Can they be rotated by angles other than 90-degree multiples? Tom Mike Stay writes:
How is that different from a tight packing on a slightly smaller paper with slightly larger squares?
On Tue, May 21, 2019 at 12:17 PM Scott Kim <scottekim1@gmail.com> wrote:
Here's a new type of polyomino problem that came up as a practical problem.
Fit the twelve pentominoes, each made of 1" squares, on a standard 8.5" by 11" sheet, so there is at least a 1/4" border between every pentomino and its neighbors, and the edge of the paper. In other words, pentominoes never touch each other, or the border of the paper. Note that given the spacing constraint, no pentomino is allowed to be inside the concave space of the U pentomino.
It's easy to fit 11 pieces, but 12 is challenging. It should be fairly straightforward to write a solver, but the loose fitting constraint does make things trickier. I did a find a solution by hand...which cannot be compressed to fit on a smaller sheet. The next question is what is the smallest area that can fit all 12 pentominoes with quarter inch spacing? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Nice problem! I tackled this by adding 3 1x1 pieces, one of them allocated to fill the U into a 2x3 hexomino. Then a search for ways to fill a 7x9 rectangle (no spacing); there are 1092100 ways, distinct w.r.t. rotation, reflection, and swapping the two 1x1 squares. For each of these candidates, a routine calculated how much spacing is needed to separate all pieces by at least 1/4 inch. If it takes more than four 1/4 inch spaces horizontally, or more than six vertically, it is discarded. That left 23959 with spacing within limits. Of those: 22572 permit no additional spacing 55 permit 1/4 inch more horizontally 1325 permit 1/4 inch more vertically 7 permit 1/2 inch more vertically (The above counts can be doubled for the 2 ways to convert the 2x3 back into a U pentomino.) Here is one of the 7 that permit 1/2 inch more vertically. Another is the same but with the T,Z unit flipped. Best viewed in a monospace font. V V V V V V V V V V V V . . . L L L L L L L L L L L L L L L L . V V V V V V V V V V V V . . . L L L L L L L L L L L L L L L L . V V V V V V V V V V V V . . . L L L L L L L L L L L L L L L L . V V V V V V V V V V V V . . . L L L L L L L L L L L L L L L L . V V V V . . . . . . . . . . . L L L L . . . . . . . . . . . . . V V V V . . W W W W W W W W . L L L L . P P P P P P P P P P P P V V V V . . W W W W W W W W . L L L L . P P P P P P P P P P P P V V V V . . W W W W W W W W . L L L L . P P P P P P P P P P P P V V V V . . W W W W W W W W . . . . . . P P P P P P P P P P P P V V V V . . . . . . W W W W W W W W . . . . . . P P P P P P P P V V V V . X X X X . W W W W W W W W . N N N N . P P P P P P P P V V V V . X X X X . W W W W W W W W . N N N N . P P P P P P P P . . . . . X X X X . W W W W W W W W . N N N N . P P P P P P P P . . . . . X X X X . . . . . W W W W . N N N N . . . . . . . . . . X X X X X X X X X X X X . W W W W . N N N N N N N N . I I I I . X X X X X X X X X X X X . W W W W . N N N N N N N N . I I I I . X X X X X X X X X X X X . W W W W . N N N N N N N N . I I I I . X X X X X X X X X X X X . . . . . . N N N N N N N N . I I I I . . . . . X X X X . . . . . . . . . . . . . . N N N N . I I I I Y Y Y Y . X X X X . U U U U U U U U U U U U . N N N N . I I I I Y Y Y Y . X X X X . U U U U U U U U U U U U . N N N N . I I I I Y Y Y Y . X X X X . U U U U U U U U U U U U . N N N N . I I I I Y Y Y Y . . . . . . U U U U U U U U U U U U . N N N N . I I I I Y Y Y Y Y Y Y Y . . U U U U U U U U U U U U . N N N N . I I I I Y Y Y Y Y Y Y Y . . U U U U U U U U U U U U . N N N N . I I I I Y Y Y Y Y Y Y Y . . U U U U U U U U U U U U . N N N N . I I I I Y Y Y Y Y Y Y Y . . U U U U U U U U U U U U . . . . . . I I I I Y Y Y Y . . . . . . . . . . . . . . . . . . . F F F F . I I I I Y Y Y Y . T T T T . Z Z Z Z Z Z Z Z . . . . . F F F F . I I I I Y Y Y Y . T T T T . Z Z Z Z Z Z Z Z . . . . . F F F F . I I I I Y Y Y Y . T T T T . Z Z Z Z Z Z Z Z . . . . . F F F F . I I I I Y Y Y Y . T T T T . Z Z Z Z Z Z Z Z . F F F F F F F F . I I I I Y Y Y Y . T T T T . . . . . Z Z Z Z . F F F F F F F F . I I I I Y Y Y Y . T T T T . . . . . Z Z Z Z . F F F F F F F F . I I I I Y Y Y Y . T T T T . . . . . Z Z Z Z . F F F F F F F F . . . . . . . . . . T T T T . . . . . Z Z Z Z . . . . . F F F F F F F F . . T T T T T T T T T T T T . Z Z Z Z Z Z Z Z . F F F F F F F F . . T T T T T T T T T T T T . Z Z Z Z Z Z Z Z . F F F F F F F F . . T T T T T T T T T T T T . Z Z Z Z Z Z Z Z . F F F F F F F F . . T T T T T T T T T T T T . Z Z Z Z Z Z Z Z . . . . . . . . . . — Mike
On May 21, 2019, at 2:16 PM, Scott Kim <scottekim1@gmail.com> wrote:
Here's a new type of polyomino problem that came up as a practical problem.
Fit the twelve pentominoes, each made of 1" squares, on a standard 8.5" by 11" sheet, so there is at least a 1/4" border between every pentomino and its neighbors, and the edge of the paper. In other words, pentominoes never touch each other, or the border of the paper. Note that given the spacing constraint, no pentomino is allowed to be inside the concave space of the U pentomino.
It's easy to fit 11 pieces, but 12 is challenging. It should be fairly straightforward to write a solver, but the loose fitting constraint does make things trickier. I did a find a solution by hand...which cannot be compressed to fit on a smaller sheet. The next question is what is the smallest area that can fit all 12 pentominoes with quarter inch spacing? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Michael Greenwald -
Mike Beeler -
Mike Stay -
Scott Kim -
Tom Karzes