5
$\begingroup$

Pete's room has a rectangular floor with dimensions $15 \times 20$. He wants to tile the floor of his room with black and white coloured tiles. Each tile is an unit square (ie. $1 \times 1$ square).

When it comes to these type of things Pete is simply a bit picky. He happens to prefer even numbers to odd ones and demands that if he places a O tetromino on the floor, it must contain an even number of black tiles. (In other words, every 2x2 square contains an even number of black tiles). The task itself is rather easy. Indeed a checkerboard coloring (alternating black and white) suffices.

The checkerboard colouring. Each 2x2 squares contains exactly 2 black squares which is even.

However, the tiler has managed to goof up and has coloured three of the corner cells white and the other black. Pete is furious and has threatened to fire the tiler if he can't tile the place properly maintaining the above condition?

Can the tiler save himself from being fired?

$\endgroup$
11
$\begingroup$

I claim that the tiler cannot save himself.

Let black be +1 and white be 0. Assume that somehow the tiler fixed the floor tiling so that it worked out. We'll count the same sum in two different ways.

  1. The sum, over every possible O tetromino, of the sum of its $4$ squares. Because in any O tetromino there should be an even number of +1s, there should also be an even sum. The entire count is a sum of even numbers, and thus is also even.

  2. The sum, over every tile, of its color (as 1 or 0) multiplied by the number of O tetrominoes that it can be a part of. The four corners can be a part of 1 O tetromino, the edges 2, and everything else 4. Thus the parity of the entire count is equal to the parity of the number of black tiles in the corners

By 1 and 2 together, the parity of the number of black tiles in the corners should be even. This is a contradiction.

$\endgroup$

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.