2
$\begingroup$

I think this is impossible, but I don't know how to prove an integer solution doesn't exist for a given equation. Here's my approach:

First, observations: The removed tile will be of the same color. (as on a nxn checkboard, color goes diagonally)
Each 2x1 piece will cover 1 black tile and 2 white tiles, or the opposite

Therefore, WLOG, assume two black tiles have been removed on a nxn chessboard. We must find a integer solution to the following system:

$j(2b+w)+k(2w+b)=\lfloor\frac{n^2}{2}\rfloor w+(\lceil\frac{n^2}{2}\rceil-2)b$, where j,k are the number of respective piece used, and w,b are the number of respectively colored tiles.

Multiply by 2 to get rid of the ceil & floor, and equating coeff of b,w, we get:

w: $n^2=2(j+2k)$

b: $n^2-4=2(2j+k)$

Sub $k=\frac{n^2-4k}{2}-2j$ into equation b

We obtain the constraint: $n^2-6j-8=0$ must have integer solutions.

Wolfram says this is unsatisfiable, but how does one prove this?

$\endgroup$
2
  • 2
    $\begingroup$ Surely a 2x1 piece covers two tiles? $\endgroup$ Nov 22, 2012 at 20:53
  • $\begingroup$ Ah... I meant a tile with 2 tiles on the first row and 1 tile on the second row. How shall I express this? $\endgroup$
    – Sam
    Nov 22, 2012 at 20:55

2 Answers 2

4
$\begingroup$

EDIT If you mean a $L$ shaped piece covering $3$ squares, then note that the number of squares on a $n \times n$ chess board is $n^2$. Once you remove any two squares, there are only $n^2-2$ squares. This need to be a multiple of $3$ if we want to cover with the $L$ shaped pieces, since if we use $k$ $L$ shaped tiles, the number of squares it will cover is $3k$. Hence, we need $n^2 -2 =3k$. However, $n^2 \equiv 0,1 \pmod{3}$. Hence, not possible.


Old question:

If the chessboard is of the form $(2n+1) \times (2n+1)$, the number of squares is odd. Once you remove the diagonally opposite squares, the number of squares left is again odd. Every tile covers $2$ squares. Hence, if we place $k$ tiles it will cover even number of squares $2k$, whereas we want to cover an odd number of squares. Hence not possible,

If you remove the diagonally opposite squares from a $2n \times 2n$ chess board and say both are black. You then have $2n^2$ white squares and $2n^2-2$ black squares. Every $2 \times 1$ tile covers a black and white square. If we use $k$ tiles, then we need $k = 2n^2$ to cover the white squares but to cover the black squares, we get $k=2n^2-2$. Hence, no solution.

$\endgroup$
2
  • $\begingroup$ Apologies, 2x1 means a L shaped piece. Hence my formulae. What happens in this case? $\endgroup$
    – Sam
    Nov 22, 2012 at 20:58
  • $\begingroup$ Thank you very much, I've over complicated things. $\endgroup$
    – Sam
    Nov 22, 2012 at 21:04
4
$\begingroup$

Each piece covers three squares of the chessboard. There are $n^2-2$ squares to cover. But $n^2-2$ is never a multiple of $3$.

$\endgroup$
4
  • $\begingroup$ This is so much simplier! I've totally over complicated it. $\endgroup$
    – Sam
    Nov 22, 2012 at 21:02
  • $\begingroup$ @Sam: You can read more about L-tromino tiling of these sorts of chessboards here: public.coe.edu/~jwhite/f09/math%20cult%20tromino.f09.pdf $\endgroup$ Nov 22, 2012 at 21:02
  • $\begingroup$ Wish I can accept both answers... but Marvis was here first so I will go with his. Thanks! $\endgroup$
    – Sam
    Nov 22, 2012 at 21:03
  • $\begingroup$ @Sam You can of-course up-vote other answers. Accepting an answer is different from up-voting an answer. $\endgroup$
    – user17762
    Nov 22, 2012 at 21:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .