Maths Olympiad Prep

Library / /15 of 19

Combinatorics Difficulty 6.4 National Olympiad Prove it Soviet Union

Problem:

An m×nm \times n rectangle is divided into mnmn unit squares by lines parallel to its sides. A gnomon is the figure of three unit squares formed by deleting one unit square from a 2×22 \times 2 square. For what m,nm, n can we divide the rectangle into gnomons so that no two gnomons form a rectangle and no vertex is in four gnomons?

Answer None

Solution

Solution:

Suppose an m×nm \times n rectangle could be tiled as described. We will establish a contradiction by counting gnomon vertices.

A gnomon cannot touch a side of the rectangle along a length 11, because then the gnomon that fitted under the overhang would form a rectangle with the first. So each gnomon along a side of the rectangle touches it along a length 22. So mm and nn must be even. Put m=2Mm = 2M, n=2Nn = 2N. There are (2M1)(2N1)(2M - 1)(2N - 1) gridpoints inside the rectangle. None of these points can have 44 gnomon vertices. But it is easy to see that they cannot have 33, because the angle inside a gnomon at a vertex is either 9090^{\circ} or 270270^{\circ}. So they have at most 22 gnomon vertices each, or 2(2M1)(2N1)2(2M - 1)(2N - 1) in total. There is only one gnomon at each of the 44 corners, or 44 gnomon vertices in total. Along the sides there are alternately 22 and 00, so at most 4(M1)+4(N1)4(M - 1) + 4(N - 1) in total, giving a grand total of 2(2M1)(2N1)+4(M1)+4(N1)+4=8MN2<8MN\leq 2(2M - 1)(2N - 1) + 4(M - 1) + 4(N - 1) + 4 = 8MN - 2 < 8MN.

On the other hand, there are 4MN/34MN / 3 gnomons each with 66 vertices, a total of 8MN8MN. Contradiction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.