Problem of the Month (April 2008)
Given a polyomino P and a positive integer n ≥ 2, what is the largest possible shape S so that n congruent non-overlapping copies of S can be packed inside P? (If P is a rectangle, or if n is a multiple of the area of P, then this problem is too easy, so we restrict our attention to the other cases.) Can you improve any of the results below? What about other polyforms? What about other shapes?
ANSWERS
The following people sent in best-known solutions this month: Károly Hajba, Andrew Bayly, Joe DeVincentis, George Sicherman, Gabriele Carelli, Livio Zucca, Jeremy Galvagni, and Gavin Theobald. I recently heard from Dick Hess, Yoshiyuki Kotani, and Robert Wainwright that they had considered this problem a decade ago. There was much improving upon other's ideas, so all these folks deserve credit.
After Joe DeVincentis showed that (1-ε) of a particular hexomino could be covered by 3 pieces, Andrew Bayly proved that at least (1-ε) of any step polyomino could be covered by any number of pieces in this manner. His "proof by picture":
Here are the best known non-trivial solutions:
Triomino In 4 Parts
| 1
| 
|
|
Triomino In 5 Parts
Triomino In 7 Parts
Triomino In 10 Parts
| 1
| 
(Joe DeVincentis)
|
|
Triomino In 11 Parts
Triomino In 13 Parts
Triomino In 14 Parts
| 1
| 
(Joe DeVincentis)
|
|
Triomino In 16 Parts
| 1
| 
|
|
Triomino In 17 Parts
Triomino In 19 Parts
| 95⁄96
| 
|
|
Triomino In 20 Parts
| 1
| 
(Joe DeVincentis)
|
|
Tetrominoes In 3 Parts
| 15⁄16
| 
| 
|
|
Tetrominoes In 5 Parts
| 15⁄16
| 
|
|
Tetrominoes In 6 Parts
| 15⁄16
| 
(Gabriele Carelli)
|
|
Tetrominoes In 7 Parts
| 119⁄128
| 
(Joe DeVincentis)
|
|
Tetrominoes In 9 Parts
| 1
| 
|
| 63⁄64
| 
(Joe DeVincentis)
|
|
Tetrominoes In 10 Parts
| 19⁄20
| 
(Joe DeVincentis)
|
|
Tetrominoes In 11 Parts
| 275⁄288
| 
(Joe DeVincentis)
|
|
Tetrominoes In 13 Parts
| 39⁄40
| 
| 
|
|
Tetrominoes In 14 Parts
| 27⁄28
| 
|
|
Pentominoes In 2 Parts
| 9⁄10
| 
(Dick Hess)
| 
(Dick Hess)
|
|
Pentominoes In 3 Parts
| 1
| 
(Dick Hess)
|
| 1–ε
| 
(Andrew Bayly)
|
| 15⁄16
| 
(Dick Hess)
| 
(Dick Hess)
| 
(Dick Hess)
|
| 9⁄10
| 
(Dick Hess)
| 
(Dick Hess)
| 
(Dick Hess)
| 
(Dick Hess)
|
|
Pentominoes In 4 Parts
| 9⁄10
| 
(Dick Hess)
| 
(Dick Hess)
|
|
Pentominoes In 6 Parts
| 1
| 
(Dick Hess)
| 
(Dick Hess)
| 
(Dick Hess)
|
| 1–ε
| 
(Livio Zucca)
|
| 24⁄25
| 
(Dick Hess)
| 
(Dick Hess)
| 
(Livio Zucca)
| 
(Livio Zucca)
|
|
Pentominoes In 7 Parts
| 49⁄50
| 
|
|
Pentominoes In 8 Parts
| 1
| 
|
| 24⁄25
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
|
(Joe DeVincentis)
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
|
| 19⁄20
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
|
|
Pentominoes In 9 Parts
| 1
| 
(Livio Zucca)
|
| 153⁄160
| 
(Joe DeVincentis)
|
| 19⁄20
| 
(Joe DeVincentis)
|
| 117⁄125
| 
| 
|
| 45⁄49
| 
(Livio Zucca)
|
|
Pentominoes In 11 Parts
| 44⁄45
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
|
(Joe DeVincentis)
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
|
(Joe DeVincentis)
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
|
| 31⁄32
| 
(Joe DeVincentis)
|
|
Pentominoes In 12 Parts
| 1
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
|
(Joe DeVincentis)
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
|
|
Hexominoes In 2 Parts
| 1–ε
| 
(Andrew Bayly)
| 
(Andrew Bayly)
| 
(Gavin Theobald)
| 
(Gavin Theobald)
|
|
Hexominoes In 3 Parts
| 1–ε
| 
(Andrew Bayly)
| 
(Andrew Bayly)
| 
(Andrew Bayly)
| 
(Andrew Bayly)
|
| 7⁄8
| 
| 
|
| 5⁄6
| 
| 
|
| 5⁄6–ε
| 
(George Sicherman)
|
|
Hexominoes In 4 Parts
| 1–ε
| 
(Andrew Bayly)
|
| 11⁄12
| 
(Livio Zucca)
|
| 8⁄9
| 
|
| 5⁄6
| 
| 
|
|
Hexominoes In 5 Parts
| 35⁄36
| 
| 
|
| 15⁄16
| 
| 
| 
(Joe DeVincentis)
| 
(Gavin Theobald)
|
| 25⁄27
| 
| 
| 
| 
(Gavin Theobald)
| 
(Gavin Theobald)
|
| 175⁄192
| 
(Gavin Theobald)
|
| 65⁄72
| 
(Gavin Theobald)
| 
(Gavin Theobald)
|
|
This table gives the smallest known packing fraction of an n-omino in k parts:
| n \ k | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
|
|---|
| 3 | 1 | 1 | 1 | .959+ | 1 | .956+ | 1 | 1 | 1
|
|---|
| 4 | 1 | 15/16 | 1 | 15/16 | 15/16 | 133/144 | 1 | 63/64 | 19/20
|
|---|
| 5 | .862+ | .833+ | 9/10 | 1 | .908+ | .940+ | | | 1
|
|---|
| 6 | 5/6 | .784+ | 5/6 | 85/96 | 1 | | | |
|
|---|
| 7 | 6/7 - ε | 5/7 | | | | 1 | | |
|
|---|
George Sicherman found these solutions for polyiamonds:
Triangle in 5 Parts
Triangle in 7 Parts
Triamond in 5 Parts
Triamond in 7 Parts
| 14⁄15
| 
|
|
Pentiamonds in 2 Parts
| 14⁄15
| 
|
| 9⁄10
| 
|
|
Pentiamonds in 3 Parts
| 14⁄15
| 
|
| 9⁄10
| 
|
|
Pentiamonds in 4 Parts
| 1
| 
|
| 19⁄20
| 
(Joe DeVincentis)
|
|
Pentiamonds in 6 Parts
Pentiamonds in 7 Parts
Pentiamonds in 8 Parts
| 1
| 
|
|
Hexiamonds in 2 Parts
| 1–ε
| 
|
|
Hexiamonds in 3 Parts
| 1–ε
| 
| 
(Andrew Bayly)
|
| 5⁄6
| 
(Károly Hajba)
|
|
Hexiamonds in 4 Parts
Hexiamonds in 5 Parts
Hexiamonds in 7 Parts
| 7⁄8
| 
| 
|
|
Heptiamonds in 2 Parts
Heptiamonds in 3 Parts
Heptiamonds in 4 Parts
Heptiamonds in 5 Parts
| 55⁄63
| 
| 
|
|
Heptiamonds in 6 Parts
| 1
| 
|
| 41⁄42
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
|
| 20⁄21
| 
| 
|
| 19⁄21
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
| 
(Joe DeVincentis)
|
|
Heptiamonds in 8 Parts
| 1
| 
|
| 6⁄7
| 
|
|
If you can extend any of these results, please
e-mail me.
Click here to go back to Math Magic. Last updated 4/30/08.
