Maths Olympiad Prep

Track / Stage 6 / 331 of 400 #1811 of 2444

Problem 1811

National Olympiad, first round
Geometry Difficulty 6.7 Prove it Mongolian Mathematical Olympiad · Mongolia

Let mm and nn be positive integers. Consider an m×nm \times n grid in a standard rectangular coordinate system. A segment is called good if it is parallel to a side of the grid. We partition the grid into triangles with vertices at integer coordinates such that each triangle has at least one side that is good, and the height of the good sides is 1. Find the minimum number of triangles that have exactly two good sides.
(Bilegdemberel Bat-Amgalan)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Without loss of generality, we can assume that 1mn1 \leq m \leq n. We define an "excellent" triangle in the partition as one that has exactly two good sides. An excellent triangle thus has two sides of length 1 and forms a right triangle. When n2n \geq 2, a partition of the 2×n2 \times n grid contains no excellent triangles, whereas a 1×n1 \times n grid partition contains 2 excellent triangles. Therefore, if m,n2m, n \geq 2 and mnmn is even, there exists a partition without any excellent triangles. Additionally, if m=1m = 1 or mnmn is odd, there exists a partition with 2 excellent triangles.

Now we show that if m=1m = 1 or the product mnmn is odd, then there exists a partition with at least 2 excellent triangles. We define a side as "bad" if it is not good, and a triangle as "bad" if it is not excellent. A bad triangle has two bad sides, and we refer to the segment connecting the midpoints of these bad sides as the "main" segment. Note that bad sides do not pass through integer vertex coordinates, except within their corresponding triangles.

The main segments of two neighboring bad triangles are connected, forming a chain. These main segments are good and change direction only at the center of unit grids. Therefore, any closed chain formed passes through an even number of unit grids. At the end of any non-closed chain, there must exist two excellent triangles.

If m=1m = 1, there is no closed chain, and if mnmn is odd, a closed chain exists. Therefore, there are at least 2 excellent triangles.

Remark. Alternatively, one can consider areas of good triangles.

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