HMMT 二月 2006 · TEAM2 赛 · 第 10 题
HMMT February 2006 — TEAM2 Round — Problem 10
题目详情
英文原题
- [40] Given a convex n -gon, n ≥ 4, at most how many diagonals can be drawn such that each drawndiagonal intersects every other drawn diagonal strictly in the interior of the n -gon? Prove that youranswer is correct.
What do the following problems have in common? [135]1
解析
英文解析
- [40] Given a convex n -gon, n ≥ 4, at most how many diagonals can be drawn suchthat each drawn diagonal intersects every other drawn diagonal strictly in the interiorof the n -gon? Prove that your answer is correct.
Answer: b n/ 2 c
Solution: If n is even, simply draw all n/ 2 diagonals connecting a vertex to the onen/ 2 vertices away. If n is odd, pretend one of the vertices does not exist, and do theabove for the ( n − 1)-gon remaining.
To show this is optimal, consider any given drawn diagonal: it divides the remainingn − 2 vertices into two camps, one of which therefore has size at most b n/ 2 c − 1, andone cannot draw two diagonals sharing a vertex.
What do the following problems have in common? [135]