The set $ S$ consists of $ n > 2$ points in the plane. The set $ P$ consists of $ m$ lines in the plane such that every line in $ P$ is an axis of symmetry for $ S$. Prove that $ m\leq n$, and determine when equality holds.
Problem
Source: CGMO 2007 P4
Tags: symmetry, combinatorial geometry, combinatorics unsolved, combinatorics
30.12.2007 12:15
Let $ C$ be the convex hull of the $ n$ points. Assume that $ C$ is a $ c$-gon. 1) If one of the lines in $ P$ contains none of the vertices of $ C$ : Then, $ c=2x$ is even (there are the same number of vertices of $ C$ in the two sides of the line). Now : - Each of the lines which goes through a vertex, say $ A$, has to go through another one vertex, say $ B$, and there are exactly $ x-1$ vertices of $ C$ between $ A$ and $ B$ along the boundary of $ C$. It follows that there is at most one of the $ m$ lines through $ A$ and this line is the same as the one through $ B$. Thus, there are at most $ x$ lines which go through the vertices of $ C$. - Each of the $ m$ lines, say $ \Delta$, which does not contain a vertex of $ C$ must go through the interior of two opposite sides of $ C$, say $ [AB]$ and $ [MP]$, and $ \Delta$ is their common perpendicular bissector. It follows that there are at most $ x$ such lines. Moreover, using the axis of symmetry, the other vertices of $ C$ can be paired as $ [XY]$ such that $ \Delta$ is the perpendicular bissector of $ [XY]$. Thus, there are at most $ 2x \leq n$ lines in $ P$. If the equality occurs then $ S = C$ (since $ 2x =n$) and it is easy to verify that we are in the conditions of IMO 199 pb#1, which forces the $ n$ points to be the vertices of a regular $ n$-gon. Note that in that case, the equality is clear (if $ P$ is chosen to be the set of all the axis of symmetry of $ S$). 2) If each of the $ m$ lines contains at least one vertex of $ C$ : Then, since each of the lines divides the $ n$ points into two set with the same number of points, it follows that each vertex of $ C$ belongs to at most one of the lines. Thus, there are at most $ c \leq n$ lines in $ P$. If equality occurs then $ S=C$ and each of the lines contains exactly one of the points (otherwise two points would define the same axis, and there would be less than $ n$ lines). Thus $ n$ is odd. Now, for each pair, say $ A,B$, of vertices, there is exactly one of the vertices, say $ M$, such that the arcs $ AM$ and $ BM$ along the boundary of $ C$ contain the same number of vertices. Using the axis of symmetry through $ M$, we deduce that this line is the perpendicular bissector of $ [AB]$, so that we are again in the statement of IMO 1999 pb#1. This forces the $ n$ points to be the vertices of a regular $ n$-gon. And, in that case, the equality is clear . Thus, in each case, we have $ m \leq n$ and equality occurs if and only if the $ n$ points are the vertices of a regular $ n$-gon, and that $ P$ is the set of all the axis of symmetry of $ S$. Pierre.
08.10.2015 20:47
Note that if $\ell,e\in P$, then reflecting $S$ on $\ell$, we get $S$ back, and hence the reflection of $e$ upon $\ell$ is also in $P$. If there were three lines in $P$ forming a triangle, then reflecting this triangle on one of its sides, the sides of its image are also axes of symmetry in $P$. We can show from here that there are infinitely many lines in $P$ (see here), so this case is impossible, and all lines in $P$ pass through one point. But if all lines in $P$ are concurrent at a point $X$, then these lines divide $360^\circ$ into $m$ parts. If we take a point $Y$ in $S\setminus\{X\}$, then reflecting it on these lines cyclically one after the other, we either obtain a cycle of $2m$ points (this is when $Y$ is not in any of the lines in $P$; we can just keep reflecting the $\frac{180^\circ}{m}$ angle containing it), or we get a cycle of $m$ points (here, every second reflection leaves $Y$ in its place). It immediately follows that $m\le n$, and that the equality case is a regular $n$-gon.