27
$\begingroup$

Can you tile a $25 \times 25$ square (no overlaps, no gaps) with a mixture of $2 \times 2$ squares and $3 \times 3$ squares?

This puzzle is by David A. Klarner.

Clarification: The number of $2 \times 2$ squares and $3 \times 3$ squares can be the same or different.

Improve this question
$\endgroup$
7
  • 8
    $\begingroup$ Congrats on 10k! $\endgroup$
    – Beastly Gerbil
    Commented Apr 18 at 16:58
  • $\begingroup$ What is the definition of 'mixture'? Evenly spread out? Or is any pattern acceptable? $\endgroup$
    – Michael Richardson
    Commented Apr 18 at 17:26
  • $\begingroup$ Thanks @BeastlyGerbil! $\endgroup$
    – Will.Octagon.Gibson
    Commented Apr 18 at 18:33
  • $\begingroup$ @MichaelRichardson I have updated my question to answer your question. The number of 2x2 squares and the number of 3x3 squares could be the same or different. $\endgroup$
    – Will.Octagon.Gibson
    Commented Apr 18 at 19:00
  • $\begingroup$ What patterns are permitted? I've come up with a couple of simple patterns that cover the entire area without gaps or overlaps, so I'm unsure if I've understood the basis of the puzzle. $\endgroup$
    – Michael Richardson
    Commented Apr 18 at 19:31

5 Answers 5

Reset to default
39
$\begingroup$

I think the answer is

Impossible.

Consider the following image:

In this striped coloring, $17 \times 25$ cells are colored in total, which is odd. On the other hand, every placement of a $3 \times 3$ square covers exactly $6$ colored cells, and that of a $2 \times 2$ square covers either $2$ or $4$ colored cells. This means any nonoverlapping placement of $2 \times 2$ and $3 \times 3$ squares can only cover an even number of colored cells, and therefore cannot cover all colored cells on the grid.

Generalizing this result, the question "For which $n$ can an $n \times n$ square be tiled with $2 \times 2$ and $3 \times 3$ squares?" can be fully answered:

  • If $n$ is even, it can be fully tiled with $2 \times 2$ squares.
  • If $n$ is a multiple of $3$, it can be fully tiled with $3 \times 3$ squares.
  • If $n$ is $1 \bmod 6$, the even-odd argument on the same coloring pattern applies, and therefore a tiling does not exist.
  • If $n$ is $5 \bmod 6$, the same argument can be made using the same pattern but shifted right by one column (so that the leftmost column is not colored). This creates a coloring with the exact same property. Therefore a tiling does not exist in this case either.

Improve this answer
$\endgroup$
4
  • $\begingroup$ If you reflected the pattern (or right-aligned it), would it then work for both cases? $\endgroup$
    – Neil
    Commented Apr 19 at 23:29
  • 1
    $\begingroup$ if I read that right, would that last part mean that there's no $n\times n$ square that could be tiled using both $2 \times 2$ and $3 \times 3$ tiles, but that could not be tiled with just one of the tile sizes? Or in other words, you always need a particular size, which ever it is, and adding the other never helps. $\endgroup$
    – ilkkachu
    Commented Apr 20 at 8:45
  • $\begingroup$ @Neil Yes, nice find. $\endgroup$
    – Bubbler
    Commented Apr 22 at 2:27
  • $\begingroup$ @ilkkachu Yes, that is correct. $\endgroup$
    – Bubbler
    Commented Apr 22 at 2:27
39
$\begingroup$

Very similar to @Bubbler's solution but perhaps a bit simpler:

Label each square in row r with (-1)r. Then the sum over all labels is 25 (if you count rows from 0). The sum over all labels covered by a tile 0,-3 or 3. In any case it is divisible by 3. Therefore a tiling cannot exist.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I like both of these, but the artistic merit has to go to Bubbler. (You get the points for the simpler colouring.) $\endgroup$
    – Bass
    Commented Apr 18 at 11:54
  • $\begingroup$ Aren't you skipping over the 2x2 tiles in this argument? $\endgroup$
    – Jacob is on Codidact
    Commented Apr 19 at 6:47
  • 5
    $\begingroup$ 2x2 sum to 0. 3x3 sum to ±3. $\endgroup$
    – magnesium
    Commented Apr 19 at 7:36
  • 2
    $\begingroup$ This also straightforwardly works for any $n$ that is odd and not divisible by $3$ (like Bubbler's extension but again simpler). $\endgroup$
    – Especially Lime
    Commented Apr 19 at 12:20
  • 3
    $\begingroup$ This can be rephrased as a coloring argument: color alternate rows black and white. There are 25 more black cells than white cells. Each tile has either the same number of black and white cells, or an imbalance of 3. $\endgroup$
    – Michael Lugo
    Commented Apr 19 at 18:57
0
$\begingroup$

A classic problem of:

invariants!

Consider the coloring where the 3rd, 6th, 9th... until 24th column are shaded. Then 2x2 and 3x3 squares both cover an even number of unshaded squares. This is an invariant! Since there are an odd number of unshaded squares in a 25x25 grid, we are done.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ This is the same as the accepted answer. Please do not post duplicate answers. $\endgroup$
    – Daniel Mathias
    Commented Apr 29 at 12:30
  • $\begingroup$ Welcome to PSE (Puzzling Stack Exchange)! $\endgroup$
    – Will.Octagon.Gibson
    Commented Apr 29 at 19:45
-1
$\begingroup$

Since the tiles to use are squares they can only fill in a rectangular space. 25x25 is square so the obvious problem isn't an issue.

I can only think of 3 ways that these tiles can fill in a square area:

  1. using only 2x2 tiles

  2. using only 3x3 tiles

  3. or combining them into effective 6x6 tiles like so: cc

Next we need to look at the factors of the length of the square space. For example a 24 square space has factors including 2, 3, and 6 which means

that all 3 methods can fill in that space.

However the question's area to fill is 25x25 which only has a factor of 5 which means

that 2, 3, and 6 can never fill in the space.

Therefore the answer is:

impossible.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ How do you know there are no alternatives to your three proposed patterns? $\endgroup$
    – Zomulgustar
    Commented Apr 27 at 22:18
  • $\begingroup$ @Zomulgustar my answer could be off but I think the only way to arrange a combination of 2x2 and 3x3 into a square area would require the least common multiple of 6. If that's true then a different pattern would result in the same outcome. $\endgroup$
    – SkySpiral7
    Commented Apr 29 at 0:57
-4
$\begingroup$

Yes this is possible.

The board is 25x25... A ring of 2x2 tiles round the exterior would leave an internal space of 21x21. This internal space would allow exactly 7x7 of the 3x3 tiles (3x7)x(3x7).

Improve this answer
$\endgroup$
3
  • 8
    $\begingroup$ I had a similar initial thought! Unfortunately because the side length is odd, you can't make a ring of 2x2 tiles around the perimeter. $\endgroup$
    – user2390246
    Commented Apr 19 at 11:40
  • 2
    $\begingroup$ @user2390246 yes! Very good point. I'll put it down to a long week.... $\endgroup$
    – VariableSquid
    Commented Apr 19 at 12:36
  • 1
    $\begingroup$ Welcome to PSE (Puzzling Stack Exchange)! Try again. $\endgroup$
    – Will.Octagon.Gibson
    Commented Apr 19 at 20:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.