HMMT 二月 2004 · 冲刺赛 · 第 30 题

HMMT February 2004 — Guts Round — Problem 30

[10] We have an n -gon, and each of its vertices is labeled with a number from the set { 1 , . . . , 10 } . We know that for any pair of distinct numbers from this set there is at least one side of the polygon whose endpoints have these two numbers. Find the smallest possible value of n . 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, FEBRUARY 28, 2004 — GUTS ROUND

解析

We have an n -gon, and each of its vertices is labeled with a number from the set { 1 , . . . , 10 } . We know that for any pair of distinct numbers from this set there is 8 at least one side of the polygon whose endpoints have these two numbers. Find the smallest possible value of n . Solution: 50 Each number be paired with each of the 9 other numbers, but each vertex can be used in at most 2 different pairs, so each number must occur on at least d 9 / 2 e = 5 different vertices. Thus, we need at least 10 · 5 = 50 vertices, so n ≥ 50. To see that n = 50 is feasible, let the numbers 1 , . . . , 10 be the vertices of a complete ( ) 10 graph. Then each vertex has degree 9, and there are = 45 edges. If we attach extra 2 copies of the edges 1-2, 3-4, 5-6, 7-8, and 9-10, then every vertex will have degree 10. In particular, the graph has an Eulerian tour, so we can follow this tour, successively numbering vertices of the 50-gon according to the vertices of the graph we visit. Then, for each edge of the graph, there will be a corresponding edge of the polygon with the same two vertex labels on its endpoints. It follows that every pair of distinct numbers occurs at the endpoints of some edge of the polygon, and so n = 50 is the answer.