Famous Problem: Remembered

Discrete Mathematics Level pending

Consider a \(2^{n}\times 2^{n}\) chequerboard divided into unit squares (i.e. a square board of \(4^n\) unit squares), where \(n \in Natural\) \(numbers \). Suppose, it must be covered by "L" shaped tiles of thrice the area of a unit square: A single tile covers exactly three unit squares that all share a common corner.

Of course since: \(4^n \equiv 1\) \(mod\) \(3\) : \(\forall n \in Natural\) \(numbers\)

This cannot be done unless we relax the condition on one particular square to not getting tiled. Say. some black square can be left untiled. So, exempting this square we have \(4^n -1\) squares, which are divisible by three: So, now it is no more impossible to tile them. But is it possible now to tile them irrespective of the choice of the exempted square?

Example: Consider a \(4 \times 4\) tiling: the exempted square is the corner one: One tiled it as shown: and got stuck! Actually this case can still be tiled (Can you figure out how?): if done properly, i.e. the corner square is strategic. The above is not the correct way however! The problem is which squares are strategic?

A square will be called "strategic" if on exempting it from tiling, the rest of the board can be successfully tiled.

How many strategic squares are there on a \(2^{4} \times 2^{4}\) chequerboard?


Problem Loading...

Note Loading...

Set Loading...