HMMT 十一月 2015 · 冲刺赛 · 第 30 题
HMMT November 2015 — Guts Round — Problem 30
题目详情
- [ 15 ] Find the largest integer n such that the following holds: there exists a set of n points in the plane such that, for any choice of three of them, some two are unit distance apart. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2015, November 14, 2015 — GUTS ROUND Organization Team Team ID#
解析
- [ 15 ] Find the largest integer n such that the following holds: there exists a set of n points in the plane such 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 , D satisfy 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 are at distance 1 apart. Assume for the sake of contradiction that this graph has no three points, no two of which are at distance 1 apart (in terms of graph theory, this means the graph has no independent set of size 3). First, note that this graph cannot contain a complete graph of size 4 (it’s clear that there can’t exist four 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 there exists an independent set of size 3 among its neighbors, contradiction (one can see this by drawing the 5 neighbors on a circle of radius 1 centered at our initial vertex and considering their pairwise distances). Moreover, if a vertex has degree 3 or lower then there are at least four vertices that are not at distance 1 from that vertex, and since not all four of these vertices can be at distance 1 from one 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 our observations, contains no independent set of size 4. Moreover, by assumption this graph contains no triangle (a complete graph on three vertices). But we can check by hand that there are only six distinct graphs on eight vertices with each vertex having degree 3 (up to isomorphism), and five of these graphs contain a triangle, and the remaining graph contains an independent set of size 4, contradiction! Hence the answer is n = 7