Let be a finite set of points in the plane. We say that is balanced if for any two distinct points , there exists a point such that . We say that is center-free if for any distinct points , there does not exist a point such that . (a) Show that for all , there exists a balanced set consisting of points. (b) For which does there exist a balanced, center-free set consisting of points? (Netherlands) Answer for part (b). All odd integers .
Solution
Part ( ). Assume that is odd. Consider a regular -gon. Label the vertices of the -gon as in counter-clockwise order, and set . We check that is balanced. For any two distinct vertices and , let be the solution of . Then, since , we have , as required. Now assume that is even. Consider a regular -gon, and let be its circumcenter. Again, label its vertices as in counter-clockwise order, and choose . We check that is balanced. For any two distinct vertices and , we always have . We now consider the vertices and . First note that the triangle is equilateral for all . Hence, if , then we have ; otherwise, if , then we have . This completes the proof. An example of such a construction when is shown in Figure 1. ! Figure 1 ! Figure 2 Comment (a). There are many ways to construct an example by placing equilateral triangles in a circle. Here we present one general method. Let be the center of a circle and let be distinct points on the circle such that the triangle is equilateral for each . Then is balanced. To construct a set of even cardinality, put extra points on the circle such that triangles and are equilateral (see Figure 2). Then is balanced. Part (b). We now show that there exists a balanced, center-free set containing points for all odd , and that one does not exist for any even . If is odd, then let be the set of vertices of a regular -gon. We have shown in part ( ) that is balanced. We claim that is also center-free. Indeed, if is a point such that for some three distinct vertices and , then is the circumcenter of the -gon, which is not contained in . Now suppose that is a balanced, center-free set of even cardinality . We will derive a contradiction. For a pair of distinct points , we say that a point is associated with the pair if . Since there are pairs of points, there exists a point which is associated with at least pairs. Note that none of these pairs can contain , so that the union of these pairs consists of at most points. Hence there exist two such pairs that share a point. Let these two pairs be and . Then , which is a contradiction. Comment (b). We can rephrase the argument in graph theoretic terms as follows. Let be a balanced, center-free set consisting of points. For any pair of distinct vertices and for any such that , draw directed edges and . Then all pairs of vertices generate altogether at least directed edges; since the set is center-free, these edges are distinct. So we must obtain a graph in which any two vertices are connected in both directions. Now, each vertex has exactly incoming edges, which means that is even. Hence is odd.