HMMT 十一月 2015 · 冲刺赛 · 第 30 题

英文解析

30. [ 15 ] Find the largest integer n such that the following holds: there exists a set of n points in the planesuch that, for any choice of three of them, some two are unit distance apart.
    Proposed by: Alexander Katz
    Answer: 7
    We can obtain n = 7 in the following way: Consider a rhombus ABCD made up of two equilateral
    °
    triangles of side length 1, where ∠ DAB = 60 . Rotate the rhombus clockwise about A to obtain a new
    ′ ′ ′ ′ ′ ′ ′
    rhombus AB C D such that DD = 1. Then one can verify that the seven points A, B, C, D, B , C , Dsatisfy the problem condition.
    To prove that n = 8 points is unobtainable, one interprets the problem in terms of graph theory.
    Consider a graph on 8 vertices, with an edge drawn between two vertices if and only if the vertices areat distance 1 apart. Assume for the sake of contradiction that this graph has no three points, no twoof which are at distance 1 apart (in terms of graph theory, this means the graph has no independentset of size 3).
    First, note that this graph cannot contain a complete graph of size 4 (it’s clear that there can’t existfour points in the plane with any two having the same pairwise distance).
    I claim that every vertex has degree 4. It is easy to see that if a vertex has degree 5 or higher, then thereexists an independent set of size 3 among its neighbors, contradiction (one can see this by drawingthe 5 neighbors on a circle of radius 1 centered at our initial vertex and considering their pairwisedistances). Moreover, if a vertex has degree 3 or lower then there are at least four vertices that arenot at distance 1 from that vertex, and since not all four of these vertices can be at distance 1 fromone another, there exists an independent set of of size 3, contradiction.
    Now, we consider the complement of our graph. Every vertex of this new graph has degree 3 and by ourobservations, contains no independent set of size 4. Moreover, by assumption this graph contains notriangle (a complete graph on three vertices). But we can check by hand that there are only six distinctgraphs on eight vertices with each vertex having degree 3 (up to isomorphism), and five of these graphscontain a triangle, and the remaining graph contains an independent set of size 4, contradiction!
    Hence the answer is n = 7