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 drawn diagonal intersects every other drawn diagonal strictly in the interior of the n -gon? Prove that your answer is correct. 1 What do the following problems have in common? [135]

解析

[40] Given a convex n -gon, n ≥ 4, at most how many diagonals can be drawn such that each drawn diagonal intersects every other drawn diagonal strictly in the interior of 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 one n/ 2 vertices away. If n is odd, pretend one of the vertices does not exist, and do the above for the ( n − 1)-gon remaining. To show this is optimal, consider any given drawn diagonal: it divides the remaining n − 2 vertices into two camps, one of which therefore has size at most b n/ 2 c − 1, and one cannot draw two diagonals sharing a vertex. What do the following problems have in common? [135]