12
$\begingroup$

My teacher gave us a riddle that goes like this:

You have a $7\times 7$ square and $16$ $3\times 1$ tiles. Of the $16$ tiles, $15$ are straight and $1$ is crocked ("L" shaped). When you tile the square with these tiles you should get that one unit is left un-tiled (because $7 \times 7=49$ and $16\times (3\times1)=48$).

The question is in what locations can the un-tiled square be?

Keep in mind that you can rotate the pieces.

I've never saw this kind of questions before so I'm not sure how to go about solving something like this. I tried to check some positions and it seems that the "L" shaped tile cannot be placed in the corners, but I don't know how to continue...

Any help will be appreciated because this is driving me crazy. Thanks.

|cite|improve this question
$\endgroup$
  • $\begingroup$ The solution might be something along the lines of that of the mutilated chessboard problem, except that in this case you need three colours. With that strategy I got a couple of necessary conditions, but I'm not sure that they're sufficient. $\endgroup$ – Rahul May 7 '11 at 22:43
11
$\begingroup$

I think this coloring works. Color each row 0 1 2 0 1 2 0 (so the 1st column is all 0, the 2nd is all 1, etc.). This gives you 21 zeros, 14 ones, 14 twos. A straight tile covers three the same (if it's vertical) or one of each (if it's horizontal). If we say it covers $a$ zeros, $b$ ones, and $c$ twos, then in either case $a\equiv b\equiv c$, modulo 3. It follows that the four spaces left after you place the 15 straight tiles are 4 0 0 (that is, 4 zeros, no ones, no twos), or 2 1 1 or 0 2 2. Now the L has to cover some permutation of 2 1 0, and the uncovered square has to be some permutation of 1 0 0. Some of these work, e.g., 2 1 0 plus 0 0 1 gives 2 1 1. But there is no way to add 1 0 0 to any permutation of 2 1 0 to get any of 4 0 0, 2 1 1, or 0 2 2, so the uncovered square can't be a zero, that is, it can't be in the 1st, 4th, or 7th column.

Applying the transpose, it can't be in the 1st, 4th, or 7th row, either. That leaves only 12 places where it can be. By symmetries of the square, these 12 places are of only three types, so if you can find a tiling leaving each of these three types uncovered, you're done. Ross has found a tiling leaving what I'd call $(2,2)$ uncovered; now it remains to do $(2,3)$ and $(3,3)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I liked your idea because it does eliminate a lot of options, but I didn't understand what you meant when you wrote: "these 12 places are of only three types". What three types? And the coordinates you use when you said " Ross has found a tiling leaving what I'd call (2,2)". How did you arrive to this coordinates? Thanks. $\endgroup$ – Maayan May 8 '11 at 2:06
  • $\begingroup$ @Maayan: Gerry is arguing from symmetry here. I think he meant $16$ places, not $12$. These are the $16$ squares that are in neither row nor column $1$, $4$ or $7$. If you draw this out and think about which of these $16$ are "really different", i.e. which of them you can transform into each other by symmetry operations of the board (reflections and rotations that leave it invariant), you'll find there are only three types, of which $(2,2)$, $(2,3)$ and $(3,3)$ are representatives. We could just as well choose $(2,6)$, $(3,6)$ and $(3,5)$ as representatives. Ross' X is at $(2,6)$. $\endgroup$ – joriki May 8 '11 at 4:42
  • $\begingroup$ Great answer! I've added an answer that shows that all three positions are achievable. $\endgroup$ – Rahul May 8 '11 at 5:28
  • $\begingroup$ Yes, I meant 16. By the way, it's not hard to settle the other two cases. Have horizontals extending right from 1,1; 1,4; 2,4; 3,3; 4,3; verticals going down from 1,7; 2,1; 2,2; 5,$a$ for $1\le a\le7$. This leaves 2,3 uncovered, and there's space for an L. Have horizontals from 1,1; 1,4; 2,1; 2,4; 3,4; 6,1; 7,1; 7,5; verticals from 1,7; 3,1; 3,2; 4,5; 4,6; 4,7; 5,4. This leaves 3,3 uncovered, with space for an L. $\endgroup$ – Gerry Myerson May 8 '11 at 5:32
7
$\begingroup$

Here is a basic 4×4 arrangement of 4 straight tiles and one crooked tile:

| | r--
| | | |
| | X |
----- |

Divide the 7×7 square into four blocks of size 4×4, 4×3, 3×4, and 3×3. The latter three are easily tiled by 11 straight tiles. Rotations of the above arrangement in the 4×4 block yields four different possible positions of the hole. Thanks to Gerry Myerson's answer, these are the only possible positions, up to rotation of the whole square.

|cite|improve this answer
$\endgroup$
3
$\begingroup$

This was written in response to the old version of the question, which asked where the L could go and remarking that it could not go in a corner. The coloring is still valid for the new on about where the 1x1 goes. As Rahul Narain points out, a first line of attack is coloring. If you number the columns $0$ to $6$ and the rows $0-6$ as well you can put a number in each square by summing the row and column modulo $3$. This is like coloring a chess board with three colors. You have $17$ squares marked $0$ and $16$ with $1$ and $2$. Each straight tromino covers one square of each number, but the L may not. If the L covers two $1$ cells or $2$ cells you are sunk. This has to be true for a given placement no matter how you rotate or reflect the numbers. This prevents you from putting the corner of the L in a corner, but it doesn't prevent you from putting one end in a corner, and there is a solution:

ABBBCCC
AADDDXE
FFFGGGE
HHHIIIE
JJJKKKL
MMMNNNL
OOOPPPL

where the X is the empty square.

A full solution would show what other positions are allowed and how they are possible.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Apologies for the non-fixed width font in the diagram. I don't know how to get fixed width. $\endgroup$ – Ross Millikan May 7 '11 at 23:16
  • $\begingroup$ @Ross: fixed :-) $\endgroup$ – joriki May 7 '11 at 23:17
  • $\begingroup$ @joriki: Thanks much. Is there a simple recipe? Also to not have blank lines-I had to put in two returns to get the line break. $\endgroup$ – Ross Millikan May 7 '11 at 23:20
  • $\begingroup$ @Ross: Everything you enclose in accent graves (`) or precede by four spaces at the start of the line is printed verbatim (including line breaks) in fixed width. You can also select text and click on the "binary" icon ("101/010") to apply this. $\endgroup$ – joriki May 7 '11 at 23:27
  • $\begingroup$ @joriki: Thanks again. I'll try it. $\endgroup$ – Ross Millikan May 7 '11 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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