Maths Olympiad Prep

Library / /505 of 520

Combinatorics Difficulty 7.6 National olympiad, round 2 Prove it

Let V\mathcal{V} be a finite set of points in the plane. We say that V\mathcal{V} is balanced if for any two distinct points A,BVA, B \in \mathcal{V}, there exists a point CVC \in \mathcal{V} such that AC=BCA C=B C. We say that V\mathcal{V} is center-free if for any distinct points A,B,CVA, B, C \in \mathcal{V}, there does not exist a point PVP \in \mathcal{V} such that PA=PB=PCP A=P B=P C. (a) Show that for all n3n \geqslant 3, there exists a balanced set consisting of nn points. (b) For which n3n \geqslant 3 does there exist a balanced, center-free set consisting of nn points? (Netherlands) Answer for part (b). All odd integers n3n \geqslant 3.

Solution

Part ( a\boldsymbol{a} ). Assume that nn is odd. Consider a regular nn-gon. Label the vertices of the nn-gon as A1,A2,,AnA_{1}, A_{2}, \ldots, A_{n} in counter-clockwise order, and set V={A1,,An}\mathcal{V}=\left\{A_{1}, \ldots, A_{n}\right\}. We check that V\mathcal{V} is balanced. For any two distinct vertices AiA_{i} and AjA_{j}, let k{1,2,,n}k \in\{1,2, \ldots, n\} be the solution of 2ki+j(modn)2 k \equiv i+j(\bmod n). Then, since kijk(modn)k-i \equiv j-k(\bmod n), we have AiAk=AjAkA_{i} A_{k}=A_{j} A_{k}, as required. Now assume that nn is even. Consider a regular (3n6)(3 n-6)-gon, and let OO be its circumcenter. Again, label its vertices as A1,,A3n6A_{1}, \ldots, A_{3 n-6} in counter-clockwise order, and choose V=\mathcal{V}= {O,A1,A2,,An1}\left\{O, A_{1}, A_{2}, \ldots, A_{n-1}\right\}. We check that V\mathcal{V} is balanced. For any two distinct vertices AiA_{i} and AjA_{j}, we always have OAi=OAjO A_{i}=O A_{j}. We now consider the vertices OO and AiA_{i}. First note that the triangle OAiAn/21+iO A_{i} A_{n / 2-1+i} is equilateral for all in2i \leqslant \frac{n}{2}. Hence, if in2i \leqslant \frac{n}{2}, then we have OAn/21+i=AiAn/21+iO A_{n / 2-1+i}=A_{i} A_{n / 2-1+i}; otherwise, if i>n2i>\frac{n}{2}, then we have OAin/2+1=AiAin/2+1O A_{i-n / 2+1}=A_{i} A_{i-n / 2+1}. This completes the proof. An example of such a construction when n=10n=10 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 OO be the center of a circle and let A1,B1,,Ak,BkA_{1}, B_{1}, \ldots, A_{k}, B_{k} be distinct points on the circle such that the triangle OAiBiO A_{i} B_{i} is equilateral for each ii. Then V={O,A1,B1,,Ak,Bk}\mathcal{V}=\left\{O, A_{1}, B_{1}, \ldots, A_{k}, B_{k}\right\} is balanced. To construct a set of even cardinality, put extra points C,D,EC, D, E on the circle such that triangles OCDO C D and ODEO D E are equilateral (see Figure 2). Then V={O,A1,B1,,Ak,Bk,C,D,E}\mathcal{V}=\left\{O, A_{1}, B_{1}, \ldots, A_{k}, B_{k}, C, D, E\right\} is balanced. Part (b). We now show that there exists a balanced, center-free set containing nn points for all odd n3n \geqslant 3, and that one does not exist for any even n3n \geqslant 3. If nn is odd, then let V\mathcal{V} be the set of vertices of a regular nn-gon. We have shown in part ( aa ) that V\mathcal{V} is balanced. We claim that V\mathcal{V} is also center-free. Indeed, if PP is a point such that PA=PB=PCP A=P B=P C for some three distinct vertices A,BA, B and CC, then PP is the circumcenter of the nn-gon, which is not contained in V\mathcal{V}. Now suppose that V\mathcal{V} is a balanced, center-free set of even cardinality nn. We will derive a contradiction. For a pair of distinct points A,BVA, B \in \mathcal{V}, we say that a point CVC \in \mathcal{V} is associated with the pair {A,B}\{A, B\} if AC=BCA C=B C. Since there are n(n1)2\frac{n(n-1)}{2} pairs of points, there exists a point PVP \in \mathcal{V} which is associated with at least n(n1)2/n=n2\left\lceil\frac{n(n-1)}{2} / n\right\rceil=\frac{n}{2} pairs. Note that none of these n2\frac{n}{2} pairs can contain PP, so that the union of these n2\frac{n}{2} pairs consists of at most n1n-1 points. Hence there exist two such pairs that share a point. Let these two pairs be {A,B}\{A, B\} and {A,C}\{A, C\}. Then PA=PB=PCP A=P B=P C, which is a contradiction. Comment (b). We can rephrase the argument in graph theoretic terms as follows. Let V\mathcal{V} be a balanced, center-free set consisting of nn points. For any pair of distinct vertices A,BVA, B \in \mathcal{V} and for any CVC \in \mathcal{V} such that AC=BCA C=B C, draw directed edges ACA \rightarrow C and BCB \rightarrow C. Then all pairs of vertices generate altogether at least n(n1)n(n-1) 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 n1n-1 incoming edges, which means that n1n-1 is even. Hence nn is odd.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.