Silvia Heubach has some recursion formulae http://www.calstatela.edu/sites/default/files/users/u1231/Papers/cgtc30.pdf ------------------------------ Message: 3 Date: Fri, 18 Aug 2017 22:06:47 -0400 From: James Propp <jamespropp@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Mrs. Perkin's Quilt variation Message-ID: <CA+G9J-fDQ1aSb6biODvqCQ9DzFeTDBxkaAq9mZ8J5O1vx9iAww@mail.gmail.com> Content-Type: text/plain; charset="UTF-8" As a warm-up we might consider allowing only 1-by-1 and 2-by-2 tiles. In that case, minimizing the number of tiles is equivalent to maximizing the number of 2-by-2 tiles; that is, we're trying to disjointly pack as many 2-by-2 squares as possible into an n-by-n square. It's obvious that a(2k) = k^2. Can anyone prove that a(2k+1) = k^2+4k+1? Equivalently, can anyone prove that you can't pack more than k^2 2-by-2 squares inside a (2k+1)-by-(2k+1) square? Jim Propp On Friday, August 18, 2017, Allan Wechsler <acwacw@gmail.com> wrote:

Suppose you are asked to tile an integer square of side n with smaller squares, but the tiles are all of side 1, 2, or 3. What is the smallest number of tiles, a(n), that you can get away with?

For n = 1, 2, 3, 4, 5, 6 the answers are fairly easily seen to be 1, 1, 1, 4, 8, 4; I'm not quite as sure that my value a(7) = 13 is correct.

If these values are right, then a(n) is not in OEIS.

It's obvious that a(3k) = k^2. I would expect that big squares can be optimally tiled by filling most of the space with 3's, with a "fringe" of some sort around two sides if n is not a multiple of 3. But I maintain a small hope that there will be "weird" solutions that don't look like this. Can anybody provide more values? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

------------------------------ Message: 4 Date: Fri, 18 Aug 2017 19:30:21 -0700 From: Tom Karzes <karzes@sonic.net> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Mrs. Perkin's Quilt variation Message-ID: <22935.41661.920082.734260@gargle.gargle.HOWL> Content-Type: text/plain; charset=us-ascii When n = 2k+1: Color the square with a 4-color checkerboard, with colors a, b, c, and d, as follows: Color the first row ababab..., color the second row cdcdcd..., then repeat after that, so for a 5x5 square (k=2) you get: ababa cdcdc ababa cdcdc ababa Observe that a given 2x2 tile will always cover exactly one of each of the 4 colors. Also observe that there are exactly k^2 cells with color d. Therefore k^2 is an upper bound on the number of 2x2 tiles that can be placed. Tom James Propp writes:

As a warm-up we might consider allowing only 1-by-1 and 2-by-2 tiles. In that case, minimizing the number of tiles is equivalent to maximizing the number of 2-by-2 tiles; that is, we're trying to disjointly pack as many 2-by-2 squares as possible into an n-by-n square. It's obvious that a(2k) = k^2. Can anyone prove that a(2k+1) = k^2+4k+1? Equivalently, can anyone prove that you can't pack more than k^2 2-by-2 squares inside a (2k+1)-by-(2k+1) square?

Jim Propp

On Friday, August 18, 2017, Allan Wechsler <acwacw@gmail.com> wrote:

...

Suppose you are asked to tile an integer square of side n with smaller squares, but the tiles are all of side 1, 2, or 3. What is the smallest number of tiles, a(n), that you can get away with?

For n = 1, 2, 3, 4, 5, 6 the answers are fairly easily seen to be 1, 1, 1, 4, 8, 4; I'm not quite as sure that my value a(7) = 13 is correct.

If these values are right, then a(n) is not in OEIS.

It's obvious that a(3k) = k^2. I would expect that big squares can be optimally tiled by filling most of the space with 3's, with a "fringe" of some sort around two sides if n is not a multiple of 3. But I maintain a small hope that there will be "weird" solutions that don't look like this. Can anybody provide more values?

------------------------------ Subject: Digest Footer _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun ------------------------------ End of math-fun Digest, Vol 174, Issue 38 *****************************************