HMMT 二月 2021 · 冲刺赛 · 第 27 题
HMMT February 2021 — Guts Round — Problem 27
题目详情
- [16] Let P be the set of points { ( x, y ) | 0 ≤ x, y ≤ 25 , x, y ∈ Z } , and let T be the set of triangles formed by picking three distinct points in P (rotations, reflections, and translations count as distinct triangles). Compute the number of triangles in T that have area larger than
解析
- [16] Let P be the set of points { ( x, y ) | 0 ≤ x, y ≤ 25 , x, y ∈ Z } , and let T be the set of triangles formed by picking three distinct points in P (rotations, reflections, and translations count as distinct triangles). Compute the number of triangles in T that have area larger than 300. Proposed by: Andrew Lin, Haneul Shin Answer: 436 ab Solution: Lemma : The area of any triangle inscribed in an a by b rectangle is at most . (Any 2 triangle’s area can be increased by moving one of its sides to a side of the rectangle). Given this, because any triangle in T is inscribed in a 25 × 25 square, we know that the largest possible area of 2 25 a triangle is , and any triangle which does not use the full range of x or y -values will have area no 2 25 · 24 more than = 300. 2 There are 4 · 25 = 100 triangles of maximal area: pick a side of the square and pick one of the 26 vertices on the other side of our region; each triangle with three vertices at the corners of the square 25 · 24 25 · 25 is double-counted once. To get areas between and , we need to pick a vertex of the square 2 2 2 25 − xy ((0 , 0) without loss of generality), as well as (25 , y ) and ( x, 25). By Shoelace, this has area , and 2 2 25 − n since x and y must both be integers, there are d ( n ) ways to get an area of in this configuration, 2 where d ( n ) denotes the number of divisors of n . 2 25 − n Since we can pick any of the four vertices to be our corner, there are then 4 d ( n ) triangles of area 2 for 1 ≤ n ≤ 25. So, we compute the answer to be | P | = 100 + 4( d (1) + . . . + d (24)) ⌊ ⌋ ∑ 24 = 4 k k ≤ 24 = 100 + 4(24 + 12 + 8 + 6 + 4 + 4 + 3 + 3 + 2 · 4 + 1 · 12) = 436 .