Yes, I had thought of that as well. Note that it also generalizes to higher dimensions (as does the original question). But things get more complicated once you have more than one non-unit tile size. Tom rcs@xmission.com writes:
Tom's argument extends to bigger squares: For example, show that a (3K+2)^2 can contain at most K^2 3x3s. Numbering coordinates from 0 to 3K+1. Mark all the cells (3A+2,3B+2) with A & B in the range 0 to K-1. There are K^2 marked cells. Every 3x3 tile must cover a mark. This doesn't solve Jim's problem, since he's also concerned with the number of 2x2 and 1x1 tiles.
Rich
--------- Quoting Tom Karzes <karzes@sonic.net>:
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?