L’s on a square

Happy New Year! From the 2004 Georg Mohr Contest:

Find all positive integers n such that a 2n x 2n chessboard can be covered by non-overlapping L-pieces, each covering 4 squares. Rotations and reflections are allowed.

One half of this problem is fairly straightforward; the other half is significantly tougher.

By combining two L’s you can make a 2 x 4 rectangle. Two of these rectangles make a 4 x 4 square, and so by combining enough L’s we can actually cover any chessboard where the side length is divisible by 4, that is for any even value of n.

That wasn’t so bad, and you can convince yourself fairly quickly that n=1 won’t work. Then you play around with a 6 x 6 grid (n=3), and you just cannot make it work. And there is still 10 x 10, 14 x 14, 18 x 18 to worry about and so on… . What would be great is a simple argument that deals with all of these cases at once. Possibly wishful thinking.

It took me a while, but eventually I stumbled upon this idea: paint every odd row black and every even row white. Now each L will cover 3 black squares and 1 white (Type A), or 3 white and 1 black (Type B). Since the total number of black squares and white squares are equal, the board must be covered by an equal number of Type A and Type B L-pieces. But this requires an even number of L’s, say 2k pieces. Then the total number of squares is

4 x 2k = 8k,

which is a multiple of 8. However, none of the grids 6 x 6, 10 x 10, 14 x 14, etc. (those boards for which n is odd) has a total number of squares divisible by 8. Hence the only values of n for which the board can be covered are all even values of n.

This problem demonstrates a nice example of what is called a ‘colouring argument’. What is particularly good about this puzzle is that the obvious colouring (that of a standard chessboard) doesn’t work, and you have to think about a colouring that produces what you need.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s