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 drawndiagonal intersects every other drawn diagonal either in the interior of the n -gon or at a vertex? Proveyour answer.
解析
英文解析
- [25] Given a convex n -gon, n ≥ 4, at most how many diagonals can be drawn suchthat each drawn diagonal intersects every other drawn diagonal either in the interiorof 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 aspecial 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 verticesapart. 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 onediagonal and draw it.
To see that these constructions work, note that two diagonals, each connecting pairsof vertices at least n/ 2 − 1 vertices apart, can fail to intersect or share a vertex only ifthey are parallel.
The previous problem shows that these constructions are optimal.