Maths Olympiad Prep

Library / /306 of 348

Combinatorics Difficulty 5.1 AIME, harder Find the answer

Find the largest integer nn such that the following holds: there exists a set of nn points in the plane such that, for any choice of three of them, some two are unit distance apart.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We can obtain n=7n=7 in the following way: Consider a rhombus ABCDA B C D made up of two equilateral triangles of side length 1 , where DAB=60\angle D A B=60^{\circ}. Rotate the rhombus clockwise about AA to obtain a new rhombus ABCDA B^{\prime} C^{\prime} D^{\prime} such that DD=1D D^{\prime}=1. Then one can verify that the seven points A,B,C,D,B,C,DA, B, C, D, B^{\prime}, C^{\prime}, D^{\prime} satisfy the problem condition. To prove that n=8n=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=7n=7

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.