返回题库

HMMT 二月 2018 · 团队赛 · 第 10 题

HMMT February 2018 — Team Round — Problem 10

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 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.)
解析

英文解析

  1. [ 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