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

英文解析

30. 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 isat least one side of the polygon whose endpoints have these two numbers. Find the 8
    smallest possible value of n .
    Solution: 50
    Each number be paired with each of the 9 other numbers, but each vertex can be usedin at most 2 different pairs, so each number must occur on at least d 9 / 2 e = 5 differentvertices. 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
    ( )
    graph. Then each vertex has degree 9, and there are = 45 edges. If we attach extra 10
    copies of the edges 1-2, 3-4, 5-6, 7-8, and 9-10, then every vertex will have degree 10.2
    In particular, the graph has an Eulerian tour, so we can follow this tour, successivelynumbering 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 numbersoccurs at the endpoints of some edge of the polygon, and so n = 50 is the answer.