Show that among any $n\geq 3$ vertices of a regular $(2n-1)$-gon we can find $3$ of them forming an isosceles triangle.
Problem
Source: CWMO 2012 Q2
Tags: geometry, geometric transformation, reflection
02.10.2012 09:48
Suppose it's not true. Call polygon as $A_1A_2.....A_{2n-1}$ and points are in anticlockwise order. Now call each of pair of points $(A_kA_{2n+1-k}),k>2$ good pair and inverse one of another, means $A_k$ is inverse point of $A_{2n+1-k}$ or opposite also . Now Let $A_1$ is chosen, as there are $n-1$ distinct good pair so we can take exactly one point from each of the good pairs. Now WLOG let $A_1$ is chosen so clearly we can't take $A_{n+1}$ implies we've to take $A_{n}$. As $A_1,A_2$ are consecutive vertices so one of $A_1A_n$ or $A_2A_n$ has odd points at RHS. Consider that pair , so for that we'll get $m>n$ such that we can't take $A_m$, so we've take it's inverse point which is at LHS of $A_n$ call $A_x$ with $x<n$ similarly again we'll get $A_y$ with $y<x<n$ so going on we must have to take $A_3$ (because that sequence won't go to $A_2$ or $A_1$ before going to $A_3$) but then $A_1A_2A_3$ is Isosceles. Hence a contradiction.
02.10.2012 17:32
For choice of a set $S$ of $n$ vertices, call one of the other $n - 1$ vertices bad if it would form an isosceles triangle with some pair of elements in $S$. Since the polygon has an odd number of sides, for each pair of vertices there is a unique vertex which would form an isosceles triangle with the pair we chose; we will say the pair forbids this vertex. For the sake of contradiction, suppose no three vertices in $S$ form an isosceles triangle. Then each of the $n$ vertices cannot be forbidden by any pair of vertices in $S$. There are \[\binom{n}{2} = \frac{n(n - 1)}{2}\] pairs of elements in $S$ so the total number of times some vertex is forbidden is just that. But since no vertex in $S$ is forbidden, the remaining $n - 1$ vertices must together be forbidden a total of $\frac{n(n - 1)}{2}$ times, meaning some vertex must be forbidden at least $\frac{n}{2}$ times. It is quite easy to see that given a forbidden vertex and one of the two vertices that forbids it, the other is uniquely determined. Then a single vertex is forbidden at most $\frac{n}{2}$ times by a set of $n$ vertices. Thus equality must hold throughout meaning for each of the $n - 1$ vertices $v$ not in $S$ (a set we will denote by $S'$), $S$ is symmetric with respect to $v$. No two vertices in $S'$ can be consecutive, since some vertex in $S'$ would have an element of $S$ and an element of $S'$ adjacent to it, contradiction. Then vertices must alternate $S$, $S'$, $S$, $\dots$ with exactly one pair of vertices $(v_1, v_2)$ in $S$ adjacent. But then we can choose a vertex $v$ in $S'$ so that both these vertices are on the same side of the dividing line through $v$, contradiction.
04.10.2012 14:45
Is this correct ? Assume that it is not true Assume that $A_1,A_2,...,A_{2n-1}$ are the vertices of our polygon , $A_{2n+k}=A_{k+1}$ , $k$ is positive Define : $l_i$ is the line throw $A_1$ and perpendicular to $A_{n-1+i}A_{n+i}$ Clearly $A_{i-k}$ is the reflection of $A_{i+k}$ across $l_i$ and clearly there is no three consecutive points. Assume we chose $A_i$ , we have$ 2(n-1) $ points without $A_i$ If we chose $A_{i+k}$ then we can't choose $A_{i-k}$ because of symmetry , so atmost we can choose $n-1$ points but in fact we'll choose $n-1$ points . Assume we choose $A_1$ , then we must choose one of $A_2$ or $A_{2n-1}$ , WLOG assume we chose $A_{2n-1}$ , we can't choose $A_{2n-2}$ , because can't choose three consecutive points , then we must choose $A_{3}$ draw $l_3$ so we must choose $A_4$ since we can't choose $A_2$ , draw $l_{2n-1}$, we must choose $A_{2n-3}$ since we can't choose $A_2$ , but this implies that we chose $A_1,A_4,A_{2n-3}$ . Contradiction !!
Attachments:
24.07.2014 18:27
If all of chosen $n$ points are distanced exactly $2$ from each other it is trivial.Suposse they are not.That means that there are $2$ points that are next to each other.Now suposse contrary,that we can choose $n$ points in such maner and let those points be: $A_1,A_2, \cdots , A_n$ and such that $A_1$ is next to $A_2$.Now we see that we can divide any $2n-2$ points in pairs such that points from the same pair are equaly distanced from 2n-1-th point.Note that in every pair one point will be chosen and the other won't.That means that points $A_2,A_3, \cdots , A_n$ all belong to different pairs with respect to $A_1$.That also hold for $A_2$.Because points $A_3,A_4, \cdots , A_n$ are the same in both cases they form different pairs wrt different points.Now we just draw it and see what happens because of conditions(condition that one point in a pair determines the other and all points belong to $2$ pairs).We then trivialy get a contradiction so it is proven.
24.09.2014 07:34
09.01.2015 10:05
Ignore wrong solution
09.01.2015 10:33
Not that, as you say, it is "difficult to understand" (its intention is in fact quite easy to grasp), but it's incorrect. You try to create $n-2$ "pigeonholes" (pairs of vertices), where to place $n-1$ "pigeons" (the remaining vertices), but of course you only account for $2(n-2)+1 = 2n-3$ vertices. In fact there are $n-1$ "pigeonholes"; the last is not your $\{A_{k+n-2}, A_{k+n-1}\}$, which is not valid, but $\{A_{k+n-1}, A_{k+n}\}$.
09.01.2015 16:00
SmartClown wrote: If all of chosen $n$ points are distanced exactly $2$ from each other it is trivial. Suposse they are not. That means that there are $2$ points that are next to each other. The preamble is unnecessary; any choice of $n$ points among $2n-1$ on a circle always contains two neighbouring points. But the idea is good, and allows a quick finish. Let us index the $2n-1$ points modulo $2n-1$. Say $A$ is the set of indices of the chosen $n$ points. For an arbitrary fixed $i\in A$ let us consider the $n-1$ doubletons $\{i-k, i+k\}$, for $1\leq k \leq n-1$. If any other two indices from $A$, distinct from $i$, belong to a same doubleton, an isosceles triangle is created. So assume this never happens, for any $i\in A$, thus the $n-1$ indices from $A\setminus \{i\}$ each belongs to a different doubleton. WLOG assume $A$ contains $0$ and $1$, as argued above. For any $i\in A$ and $0\leq j\neq i \leq 2n-2$ denote by $j \in A \stackrel{(i)}{\longrightarrow} 2i-j \not \in A$ or $j \not \in A \stackrel{(i)}{\longrightarrow} 2i-j \in A$ the fact that exactly one of $j,2i-j$ belongs to $A$. Then $1 \in A \stackrel{(0)}{\longrightarrow} -1 \not \in A \stackrel{(1)}{\longrightarrow} 3 \in A \stackrel{(0)}{\longrightarrow} -3 \not \in A \stackrel{(1)}{\longrightarrow} 5 \in A$, and so $\{1,3,5\} \subseteq A$, contradiction with $1 \stackrel{(3)}{\longrightarrow} 5$. Therefore the assumption was false, and an isosceles triangle is always created.
10.01.2015 06:21
As a matter of fact, working with $0,1 \in A$ is not instrumental. Let us do the same for any $i,j \in A$ with $i\neq j$ (under the notations of above; the idea is reminiscent of one in the proof that a finite set cannot have two centres of symmetry, alternately taking symmetrics with respect to them). Then \[j \in A \stackrel{(i)}{\longrightarrow} 2i-j \not \in A \stackrel{(j)}{\longrightarrow} 3j-2i \in A \stackrel{(i)}{\longrightarrow} 4i-3j \not \in A \stackrel{(j)}{\longrightarrow} 5j-4i \in A,\] and so $\{j,3j-2i,5j-4i\} \subseteq A$, contradiction with $j \stackrel{(3j-2i)}{\longrightarrow} 5j-4i$. For the record, the indices $j$, $3j-2i = j + 2(j-i)$, $5j-4i = j + 4(j-i)$ are distinct, since $2n-1 \nmid 2^k(j-i)$ for any $k\geq 0$, because $2n-1 \nmid j-i$. Therefore the assumption was false, and an isosceles triangle is always created.
25.05.2024 10:18
Label the points $-n+1, -n+2, ..., -1, 0, 1, 2, ..., n-1$, let $V$ be the set of the $n$ points. WLOG, suppose $0 \in V$. Then, we make the following observations: 1. At most one of $k, -k \in V$. Suppose otherwise, then the points $-k, 0, k$ form an isosceles triangle. 2. Exactly one of $k, -k \in V$. There are $n-1$ pairs of $k, -k$, but a total of $n-1$ remaining terms in $V$. Using the first observation, we can conclude that exactly one of $k, -k \in V$. It is safe to assume $1 \in V$. If $1 \in S$, $-1, 2 \not\in V$. $2 \not \in V \implies -2 \in V$. $0, -2 \in V \implies -4 \not\in V$. $-2, 1 \in V \implies 4 \not\in V$. But this contradicts observation 2, hence a contradiction for $n \geq 5$. For $n = 3$ or $4$, one can easily check that an isosceles triangle will always be formed.