Problem

Source: Kazakhstan NMO 2019, Problem 5

Tags: combinatorics proposed, combinatorics



Given a checkered rectangle of size n × m. Is it always possible to mark $3$ or $4$ nodes of a rectangle so that at least one of the marked nodes lay on each straight line containing the side of the rectangle, and the non-self-intersecting polygon with vertices at these nodes has an area equal to $$\dfrac{1}{2}\min \left ( \text{gcd}(n, m), \dfrac{n+m}{\text{gcd}(n, m)} \right)$$?