Skip to main content
OlympiadHQ

Browse · MathNet

Print

Mongolian Mathematical Olympiad

Mongolia geometry

Problem

Let and be positive integers. Consider an 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)
Solution
Without loss of generality, we can assume that . 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 , a partition of the grid contains no excellent triangles, whereas a grid partition contains 2 excellent triangles. Therefore, if and is even, there exists a partition without any excellent triangles. Additionally, if or is odd, there exists a partition with 2 excellent triangles.

Now we show that if or the product 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 , there is no closed chain, and if is odd, a closed chain exists. Therefore, there are at least 2 excellent triangles.

Remark. Alternatively, one can consider areas of good triangles.
Final answer
Minimum equals 0 if both dimensions are at least two and their product is even; otherwise the minimum equals 2.

Techniques

Combinatorial GeometryInvariants / monovariants