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 '12 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 '12 at 20:55
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 '12 at 20:58
  • $\begingroup$ Thank you very much, I've over complicated things. $\endgroup$
    – Sam
    Nov 22 '12 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 '12 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 '12 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 '12 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 '12 at 21:07

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.