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 corners at (0 , 0) , ( n, 0) , ( n, m ) , (0 , m ) in the coordinate plane. A simple non-self-intersecting quadrilateral with vertices at integer coordinates is called far-reaching if each of its vertices lie on or inside R , but each side of R contains at least one vertex of the quadrilateral. Show that there is a far-reaching quadrilateral 6 with area at most 10 . (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 corners at (0 , 0) , ( n, 0) , ( n, m ) , (0 , m ) in the coordinate plane. A simple non-self-intersecting quadrilateral with vertices at integer coordinates is called far-reaching if each of its vertices lie on or inside R , but each side of R contains at least one vertex of the quadrilateral. Show that there is a far-reaching quadrilateral 6 with area at most 10 . (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 R connecting (0 , 0) and ( n, m ) is g + 1. We construct two far-reaching quadrilaterals and show that at least 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. Now consider 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 ), and a b ( n, m − 1). This is a concave quadrilateral which can be split into two triangle of areas and , so 2 2 1 the area of this quadrilateral is at most ( a + b ). 2 1 We have therefore shown that there is always a far-reaching quadrilateral with area at most min( g, ( a + 2 1 1 1 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 5 a far-reaching quadrilateral with area at most 10 as desired.