Find the smallest $n \in \mathbb{N}$ such that if any 5 vertices of a regular $n$-gon are colored red, there exists a line of symmetry $l$ of the $n$-gon such that every red point is reflected across $l$ to a non-red point.
Problem
Source: China TST 1994, problem 3
Tags: symmetry, geometry, geometric transformation, reflection, trapezoid, combinatorics unsolved, combinatorics
24.05.2005 21:32
Call "sequence" the way the colored points appear, reverse the sequence, if we put the reversed sequence over the points of the n_agon starting anywhere, and it doesnt overlap the colored points, then we may reflect the n-agon by the line perpendicular to the midpoint of the line joining the starting points of the original sequence and the reversed one. So what we have is that there is a starting position for the reversed sequence that doesnt overlap our original sequence. Every point of our original sequence overlaps with $5$ reversed sequences, so we have at most $25$ overlaps, more over, every pair of points of the original sequence have a common overlap, so we have at most $25-10=15$ overlaped reversed sequences, so we get for $n>15$ a non overlaping reversed sequence! Now, number the vertices from $0$ to $14$ clockwise, and put colored points in vertex: $0,1,3,6,10$ it is easy to see the overlaping arguments gives equality here.
26.11.2007 07:24
your example for $ n=15$ is wrong. take the symmetry line that passes from the vertex $ 7$. i can't find an example for $ n=15$. i think there isn't any. if somebody with a full solution please write it.
27.11.2007 10:34
Two different red points "eliminate" one line from the candidates to be the line of symmetry (the one that reflects one of them to another) and every point eliminates one line (the one that the point lies on). So the number of eliminated lines is $ \binom{5}{2}+5=15$. So if we had the solution for $ n=15$ we must have chosen each line once. Now consider the "sequence" of points and the sequence of the distances between them (the distance is the minimum of the number of points we have to go though going clockwise or counterclockwise). If any two pairs of different (in a pair) points have the same distance we have a trapezoid (or a triangle) and we choose a line twice, so no two distances can be equal. We have $ \binom{5}{2}=15$ distances and the maximal distance is 7, the minimal is 0, so we have 2 equal distances. Therefore we choose a line twice, thus we do not choose some line and this line is the line of the symmetry.
27.11.2007 14:26
my answer is $ 17$ but i can't prove it, i tried it a few times and i saw it is not valid for 15, nor 16. And could you please give a full solution to this problem, folks?
27.11.2007 14:37
Pascual2005 wrote: Call "sequence" the way the colored points appear, reverse the sequence, if we put the reversed sequence over the points of the n_agon starting anywhere, and it doesnt overlap the colored points, then we may reflect the n-agon by the line perpendicular to the midpoint of the line joining the starting points of the original sequence and the reversed one. So what we have is that there is a starting position for the reversed sequence that doesnt overlap our original sequence. Every point of our original sequence overlaps with $ 5$ reversed sequences, so we have at most $ 25$ overlaps, more over, every pair of points of the original sequence have a common overlap, so we have at most $ 25 - 10 = 15$ overlaped reversed sequences, so we get for $ n > 15$ a non overlaping reversed sequence! Now, number the vertices from $ 0$ to $ 14$ clockwise, and put colored points in vertex: $ 0,1,3,6,10$ it is easy to see the overlaping arguments gives equality here. I don't think so. Please examine.
29.11.2007 13:33
Please read my previous post before reading this. Number the points in the clockwise direction. Now I will write the 5 points for with the thesis is false. For n=10, numbers are 0,1,4,7,8. For n=11, numbers are 0,1,3,4,9. For n=12, numbers are 0,1,3,5,6. For n=13, numbers are 0,1,5,8,12. For n=14 we have 14 symmetry lines. We take the distances between adjoining points and the points having a common adjoining point. There are 10 distances such and the maximal distance is 7 and minimal is 1. So there are 3 pairs of the distances of the same length, so there at least 2 lines are eliminated twice. As we eliminate 15 lines and we eliminate 2 lines twice, so we really eliminate $ 15-2=13$ lines, so we don't eliminate some line and this line is the line of the symmetry which we were looking for. If you have any questions please write.
29.11.2007 13:43
polarb1 wrote: Two different red points "eliminate" one line from the candidates to be the line of symmetry (the one that reflects one of them to another) and every point eliminates one line (the one that the point lies on). So the number of eliminated lines is $ \binom{5}{2} + 5 = 15$. So if we had the solution for $ n = 15$ we must have chosen each line once. Now consider the "sequence" of points and the sequence of the distances between them (the distance is the minimum of the number of points we have to go though going clockwise or counterclockwise). If any two pairs of different (in a pair) points have the same distance we have a trapezoid (or a triangle) and we choose a line twice, so no two distances can be equal. We have $ \binom{5}{2} = 15$ distances and the maximal distance is 7, the minimal is 0, so we have 2 equal distances. Therefore we choose a line twice, thus we do not choose some line and this line is the line of the symmetry. Sorry. Actually we have only 10 distances (we consider only distances between adjoining points and points having a common adjoining point), but it doesn't matter.
29.11.2007 13:55
This problem seems much easier if you think about it in terms of numbers rather than reflections. If you identify the vertices of an $ n-$gon with the residues mod $ n$, then the reflections of the $ n-$gon take the form $ f_a(x)=a-x$ for some $ a$. A reflection maps the red point $ x$ to the red point $ y$ iff $ x+y=a$. So we can recast the question as follows: "What is the smallest $ n$ such that there is not a subset $ S$ of 5 residues modulo $ n$ such that every $ a$ can be written as the sum of two residues in $ S$? The example above shows that $ S$ exists for $ n=13$. If $ n=14$, then there must be 7 odd residues, each of which must be the sum of an odd residue in $ S$ and an even residue in $ S$. But there are at most 6 choices of an odd and an even residue, so this is impossible and we are done.
07.08.2018 18:59
For all $n$ up to $13$ examples are possible and they are trivial to find.For $n=14$ we number points with $1, 2 ... 14$ in clockwise order.We call line of symmetry l good if it sends one of red points to one of red points and bad otherwise.For every pair of red points there can exist exactly one good line.In case $n=14$ we have $7$ lines of symmetry and if we have at most $6$ good lines so there exist one bad line and we are done.Now if two red points have numbers with same parity then there does not exist good line for these two points(trivial).Number of good lines(that can exist) is $10- (aC2)-((a-5)C2)$ where a is number of red points on with even number and $aC2$ is "from $a$ we chose $2$ "(idk how these goes in latex).Now $10- (aC2)-((a-5)C2)<=6$ (min when $a=2$ or $a=3$) so there is a bad line and we are done .