Maths Olympiad Prep

Library / CIS /15 of 19

CIS

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 (2M−1)(2N−1)(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 90∘90^{\circ} or 270∘270^{\circ}. So they have at most 22 gnomon vertices each, or 2(2M−1)(2N−1)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(M−1)+4(N−1)4(M - 1) + 4(N - 1) in total, giving a grand total of ≤2(2M−1)(2N−1)+4(M−1)+4(N−1)+4=8MN−2<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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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