Return to Answer

You might like to check out

M. Reid, Klarner Systems and Tiling Boxes With Polyominoes, J. Combin. Theory A111 (2005)89-105.

and also

M. Reid, Asymptotically Optimal Box Packing Theorems, Elec. J. Combin. 15 (2008) #R78

These are motivated by the boxes in $\mathbb{Z}^n$ which can be tiled by a set of shapes. This informs some of the examples given, however the theory is just what you want.

For your particular problem of $6 \times 6,$ $10 \times 10,$ and $15 \times 15$ you can tile both a $30 \times 31$ (using one each of $30 \times w$ for $w=6,10,15$) and also a $31 \times 30.$ From your Theorem 3 it follows that all large enough rectangles can be tiled. LATER: From your corrected theorem $3$ one must add provided that the area is a multiple of $30.$

In the second article the author speculates that it may be much more difficult to generate the full list of tilable rectangles than results something like

"For an $m \times n$ rectangle to be tilable using the given basic rectangles, it is necessary that $14 \mid mn.$ Furthermore, there is a $C$ so that $14 \mid mn$ is sufficient provided that $m,n \gt C.$"

A final note: To simply read the desired dimensions $m,n$ of a rectangle takes $\log{m}+\log{n}=\log{mn}$ time (unless they are something like $m=2^{5^7}$) so it might be possible to improve your theorem $4$ to something like $\log{mn}+O(1).$ After some (huge but) fixed amount of work a criterion such as the above can be given (with an explicit $C$) and, if desired (increasing the huge preprocessing step manyfold), the "small" cases can be enumerated.

You might like to check out

M. Reid, Klarner Systems and Tiling Boxes With Polyominoes, J. Combin. Theory A111 (2005)89-105.

and also

M. Reid, Asymptotically Optimal Box Packing Theorems, Elec. J. Combin. 15 (2008) #R78

These are motivated by the boxes in $\mathbb{Z}^n$ which can be tiled by a set of shapes. This informs some of the examples given, however the theory is just what you want.

For your particular problem of $6 \times 6,$ $10 \times 10,$ and $15 \times 15$ you can tile both a $30 \times 31$ (using one each of $30 \times w$ for $w=6,10,15$) and also a $31 \times 30.$ From your Theorem 3 it follows that all large enough rectangles can be tiled. LATER: From your corrected theorem $3$ one must add provided that the area is a multiple of $30.$

In the second article the author speculates that it may be much more difficult to generate the full list of tilable rectangles than results something like

"For an $m \times n$ rectangle to be tilable using the given basic rectangles, it is necessary that $14 \mid mn.$ Furthermore, there is a $C$ so that $14 \mid mn$ is sufficient provided that $m,n \gt C.$"

A final note: To simply read the desired dimensions $m,n$ of a rectangle takes $\log{m}+\log{n}=\log{mn}$ time (unless they are something like $m=2^{5^7}$) so it might be possible to improve your theorem $4$ to something like $\log{mn}+O(1).$ After some (huge but) fixed amount of work a criterion such as the above can be given (with an explicit $C$) and, if desired (increasing the huge preprocessing step manyfold), the "small" cases can be enumerated.

You might like to check out

M. Reid, Klarner Systems and Tiling Boxes With Polyominoes, J. Combin. Theory A111 (2005)89-105.

and also

M. Reid, Asymptotically Optimal Box Packing Theorems, Elec. J. Combin. 15 (2008) #R78

These are motivated by the boxes in $\mathbb{Z}^n$ which can be tiled by a set of shapes. This informs some of the examples given, however the theory is just what you want.

For your particular problem of $6 \times 6,$ $10 \times 10,$ and $15 \times 15$ you can tile both a $30 \times 31$ (using one each of $30 \times w$ for $w=6,10,15$) and also a $31 \times 30.$ From your Theorem 3 it follows that all large enough rectangles can be tiled. LATER: From your corrected theorem $3$ one must add provided that the area is a multiple of $30.$

In the second article the author speculates that it may be much more difficult to generate the full list of tilable rectangles than results something like

"For an $m \times n$ rectangle to be tilable using the given basic rectangles, it is necessary that $14 \mid mn.$ Furthermore, there is a $C$ so that $14 \mid mn$ is sufficient provided that $m,n \gt C.$"

A final note: To simply read the desired dimensions $m,n$ of a rectangle takes $\log{m}+\log{n}=\log{mn}$ time (unless they are something like $m=2^{5^7}$) so it might be possible to improve your theorem $4$ to something like $\log{mn}+O(1).$ After some (huge but) fixed amount of work a criterion such as the above can be given (with an explicit $C$) and, if desired (increasing the huge preprocessing step manyfold), the "small" cases can be enumerated.

Claim: Using $6 \times 6$, $10 \times 10$ and $15 \times 15$ all large enough rectangles can be tiled.

Proof: From your corrected theorem $3$ one can get all large enough rectangles using a $3 \times 3$ and a $5 \times 5.$ It follows that one can get all large enough rectangles $2m \times 2n$ using $6 \times 6$ and $10 \times 10.$ Similarly one can get all large enough $3m \times 3n$ using $6 \times 6$ and $15 \times 15.$ So make a $2p \times 2q$ and $3s \times 3t$ for distinct (large enough) primes $p,q,s,t.$ One more application of theorem $3$ yields that all large enough rectangles can be tiled.

It would suffice to get two specific suitable rectangles. The end result would be the same.

You might like to check out

M. Reid, Klarner Systems and Tiling Boxes With Polyominoes, J. Combin. Theory A111 (2005)89-105.

and also

M. Reid, Asymptotically Optimal Box Packing Theorems, Elec. J. Combin. 15 (2008) #R78

These are motivated by the boxes in $\mathbb{Z}^n$ which can be tiled by a set of shapes. This informs some of the examples given, however the theory is just what you want.

For your particular problem of $6 \times 6,$ $10 \times 10,$ and $15 \times 15$ you can tile both a $30 \times 31$ (using one each of $30 \times w$ for $w=6,10,15$) and also a $31 \times 30.$ From your Theorem 3 it follows that all large enough rectangles can be tiled. LATER: From your corrected theorem $3$ one must add provided that the area is a multiple of $30.$

In the second article the author speculates that it may be much more difficult to generate the full list of tilable rectangles than results something like

"For an $m \times n$ rectangle to be tilable using the given basic rectangles, it is necessary that $14 \mid mn.$ Furthermore, there is a $C$ so that $14 \mid mn$ is sufficient provided that $m,n \gt C.$"

A final note: To simply read the desired dimensions $m,n$ of a rectangle takes $\log{m}+\log{n}=\log{mn}$ time (unless they are something like $m=2^{5^7}$) so it might be possible to improve your theorem $4$ to something like $\log{mn}+O(1).$ After some (huge but) fixed amount of work a criterion such as the above can be given (with an explicit $C$) and, if desired (increasing the huge preprocessing step manyfold), the "small" cases can be enumerated.

You might like to check out

M. Reid, Klarner Systems and Tiling Boxes With Polyominoes, J. Combin. Theory A111 (2005)89-105.

and also

M. Reid, Asymptotically Optimal Box Packing Theorems, Elec. J. Combin. 15 (2008) #R78

These are motivated by the boxes in $\mathbb{Z}^n$ which can be tiled by a set of shapes. This informs some of the examples given, however the theory is just what you want.

For your particular problem of $6 \times 6,$ $10 \times 10,$ and $15 \times 15$ you can tile both a $30 \times 31$ (using one each of $30 \times w$ for $w=6,10,15$) and also a $31 \times 30.$ From your Theorem 3 it follows that all large enough rectangles can be tiled.

In the second article the author speculates that it may be much more difficult to generate the full list of tilable rectangles than results something like

"For an $m \times n$ rectangle to be tilable using the given basic rectangles, it is necessary that $14 \mid mn.$ Furthermore, there is a $C$ so that $14 \mid mn$ is sufficient provided that $m,n \gt C.$"

A final note: To simply read the desired dimensions $m,n$ of a rectangle takes $\log{m}+\log{n}=\log{mn}$ time (unless they are something like $m=2^{5^7}$) so it might be possible to improve your theorem $4$ to something like $\log{mn}+O(1).$ After some (huge but) fixed amount of work a criterion such as the above can be given (with an explicit $C$) and, if desired (increasing the huge preprocessing step manyfold), the "small" cases can be enumerated.

You might like to check out

M. Reid, Klarner Systems and Tiling Boxes With Polyominoes, J. Combin. Theory A111 (2005)89-105.

and also

M. Reid, Asymptotically Optimal Box Packing Theorems, Elec. J. Combin. 15 (2008) #R78

These are motivated by the boxes in $\mathbb{Z}^n$ which can be tiled by a set of shapes. This informs some of the examples given, however the theory is just what you want.

For your particular problem of $6 \times 6,$ $10 \times 10,$ and $15 \times 15$ you can tile both a $30 \times 31$ (using one each of $30 \times w$ for $w=6,10,15$) and also a $31 \times 30.$ From your Theorem 3 it follows that all large enough rectangles can be tiled. LATER: From your corrected theorem $3$ one must add provided that the area is a multiple of $30.$

In the second article the author speculates that it may be much more difficult to generate the full list of tilable rectangles than results something like

"For an $m \times n$ rectangle to be tilable using the given basic rectangles, it is necessary that $14 \mid mn.$ Furthermore, there is a $C$ so that $14 \mid mn$ is sufficient provided that $m,n \gt C.$"

A final note: To simply read the desired dimensions $m,n$ of a rectangle takes $\log{m}+\log{n}=\log{mn}$ time (unless they are something like $m=2^{5^7}$) so it might be possible to improve your theorem $4$ to something like $\log{mn}+O(1).$ After some (huge but) fixed amount of work a criterion such as the above can be given (with an explicit $C$) and, if desired (increasing the huge preprocessing step manyfold), the "small" cases can be enumerated.

Claim: Using $6 \times 6$, $10 \times 10$ and $15 \times 15$ all large enough rectangles can be tiled.

Proof: From your corrected theorem $3$ one can get all large enough rectangles using a $3 \times 3$ and a $5 \times 5.$ It follows that one can get all large enough rectangles $2m \times 2n$ using $6 \times 6$ and $10 \times 10.$ Similarly one can get all large enough $3m \times 3n$ using $6 \times 6$ and $15 \times 15.$ So make a $2p \times 2q$ and $3s \times 3t$ for distinct (large enough) primes $p,q,s,t.$ One more application of theorem $3$ yields that all large enough rectangles can be tiled.

It would suffice to get two specific suitable rectangles. The end result would be the same.