HMMT 二月 2018 · 团队赛 · 第 10 题
HMMT February 2018 — Team Round — Problem 10
题目详情
英文原题
- [ 60 ] Let n and m be positive integers which are at most 10 . Let R be the rectangle with cornersat (0 , 0) , ( n, 0) , ( n, m ) , (0 , m ) in the coordinate plane. A simple non-self-intersecting quadrilateral withvertices at integer coordinates is called far-reaching if each of its vertices lie on or inside R , but each sideof R contains at least one vertex of the quadrilateral. Show that there is a far-reaching quadrilateralwith area at most 10 .6
(A side of a rectangle includes the two endpoints.)
解析
英文解析
- [ 60 ] Let n and m be positive integers which are at most 10 . Let R be the rectangle with cornersat (0 , 0) , ( n, 0) , ( n, m ) , (0 , m ) in the coordinate plane. A simple non-self-intersecting quadrilateral withvertices at integer coordinates is called far-reaching if each of its vertices lie on or inside R , but each sideof R contains at least one vertex of the quadrilateral. Show that there is a far-reaching quadrilateralwith area at most 10 .6
(A side of a rectangle includes the two endpoints.)
Proposed by: Kevin Sun
Let g = gcd( n, m ), with n = g · a and m = g · b . Note that the number of points on the diagonal of Rconnecting (0 , 0) and ( n, m ) is g + 1. We construct two far-reaching quadrilaterals and show that atleast one of them has small area.
For our first quadrilateral, let ( x , y ) and ( x , y ) be the points with the shortest nonzero distances
1 1 2 2
to the diagonal between (0 , 0) and ( n, m ) which lie above and below the diagonal, respectively. Nowconsider the quadrilateral with vertices (0 , 0), ( x , y ), ( n, m ), ( x , y ). Note that the only lattice
1 1 2 2
points which can lie on or inside this quadrilateral are ( x , y ), ( x , y ), and points on the diagonal of
1 1 2 2
R , as otherwise we could find a closer point to the diagonal than ( x , y ) and ( x , y ). Thus by Pick’s
1 1 2 2
Theorem, the area of this quadrilateral is at most g .
For our second quadrilateral, we will take as our vertices the points (0 , 0), ( n − 1 , m ), ( a, b ), anda b
( n, m − 1). This is a concave quadrilateral which can be split into two triangle of areas and , so
2 2
the area of this quadrilateral is at most ( a + b ).1
We have therefore shown that there is always a far-reaching quadrilateral with area at most min( g, ( a +12
1 1 12
10 5
b )). Since g · ( a + b ) = ( n + m ) ≤ 10 , we have that min( g, ( a + b )) ≤ 10 , so we can always find
2 2 2
a far-reaching quadrilateral with area at most 10 as desired.5