HMMT 二月 2006 · TEAM1 赛 · 第 7 题

HMMT February 2006 — TEAM1 Round — Problem 7

[25] 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 either in the interior of the n -gon or at a vertex? Prove your answer.

解析

[25] 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 either in the interior of the n -gon or at a vertex? Prove your answer. Answer: If n = 4, then 2; otherwise, n . Solution: First of all, assume without loss of generality that the n -gon is regular (this has no effect as far as diagonal intersection is concerned). Also, treat n = 4 as a special case; obviously the answer is 2 here. If n is odd, simply draw n diagonals, connecting each vertex to the ones ( n − 1) / 2 vertices away (in either direction). If n is even, first draw the n/ 2 diagonals connecting pairs of vertices n/ 2 vertices apart. Then, there are n diagonals connecting pairs of vertices n/ 2 − 1 vertices apart; they come in n/ 2 pairs of parallel diagonals; from each such pair, randomly pick one diagonal and draw it. To see that these constructions work, note that two diagonals, each connecting pairs of vertices at least n/ 2 − 1 vertices apart, can fail to intersect or share a vertex only if they are parallel. The previous problem shows that these constructions are optimal.