Maths Olympiad Prep

Library / /55 of 69

Geometry Difficulty 6.7 National olympiad Prove it 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)

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.

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 and solution reproduced as published; topic and difficulty added by this site.