Suppose we have board, of size (16x16)

And 31 (1x4) + 33 (2x2) pieces.

Is it possible to cover up board with those pieces, if so - how?

If not - why?

So far I was unable to think of anything better, then bruteforcing setting by python script, and didnt get result. So I assume it is impossible, or then I made mistake with algorithm.

Any tips welcome

  • 2
    $\begingroup$ The answer to these is always no. The usual way to prove it is to find a coloring of the board. You might find a two color one that has the $2 \times 2$ tile covering two of each color and the $4 \times 1$ tile covering $3$ of one color and $1$ of the other. If the board has the same number of squares of each color you are done. You also might find one that the $4 \times 1$ covers four of the same color. No, I don't have one, or I would make an answer. Usually the pattern of colors matches the shape of the pieces. You might also find a pattern using four colors. $\endgroup$ – Ross Millikan Feb 11 '16 at 17:23

It is impossible. Consider the colouring of the board below.

enter image description here

Suppose it is possible. Then each $2 \times 2$ piece covers exactly one black square and each $1 \times 4$ piece covers either zero or two black squares. But there are $64$ black squares and $64 - 33$ is odd, contradiction.


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.