返回题库

HMMT 十一月 2019 · 团队赛 · 第 10 题

HMMT November 2019 — Team Round — Problem 10

专题
Discrete Math / 离散数学
难度
L3
来源
HMMT

题目详情

  1. [70] A convex 2019-gon A A . . . A is cut into smaller pieces along its 2019 diagonals of the form 1 2 2019 A A for 1 ≤ i ≤ 2019, where A = A , A = A , and A = A . What is the least possible i i +3 2020 1 2021 2 2022 3 number of resulting pieces?
解析
  1. [70] A convex 2019-gon A A . . . A is cut into smaller pieces along its 2019 diagonals of the form 1 2 2019 A A for 1 ≤ i ≤ 2019, where A = A , A = A , and A = A . What is the least possible i i +3 2020 1 2021 2 2022 3 number of resulting pieces? Proposed by: Krit Boonsiriseth Answer: 5049 Each time we draw in a diagonal, we create one new region, plus one new region for each intersection on that diagonal. So, the number of regions will be 1 + (number of diagonals) + (number of intersections) , where (number of intersections) counts an intersection of three diagonals twice. Since no four diagonals can pass through a point, the only nonconstant term in our expression is the last one. To minimize this term, we want to maximize the number of triples of diagonals passing through the same point. Consider the set S of triples of diagonals A A that intersect at a single point. Each triple in S must come from n n +3 three consecutive diagonals, and two different triples can only have one diagonal in common, so S has at ⌊ ⌋ 2019 most = 1009 triples. Hence the number of resulting pieces is at least 2 1 + (2019) + (2 · 2019 − 1009) = 5049 . To show that 5049 is attainable, we use the following construction. Let B . . . B be a regular 1010- 1 1010 ← − − − − − − → ← − − → gon, and let denote the external angle bisector of ∠ B B B . Let A = B B ∩ B B , n n − 1 n n +1 1 1009 1010 1 2 ← − − − − − − → ← − − − − → ← − − − − → A = B B ∩ B B , A = ` ∩ ` , and for n = 1 , . . . , 1008, define A = ∩ B B 2018 1008 1009 1010 1 2019 1 1009 2 n n +1 n − 1 n ← − − − − − − → and A = ` ∩ B B . It follows that, for all n = 0 , . . . , 1008, A A , A A , and 2 n +1 n n +1 n +2 2 n − 1 2 n +2 2 n 2 n +3 A A intersect at B . 2 n +1 2 n +4 n +1 4