Given a regular $26$-gon. Prove that for any $9$ vertices of that regular $26$-gon, then there exists three vertices that forms an isosceles triangle.
Problem
Source: Indonesia National Math Olympiad 2022 Problem 4 (INAMO 2022/4)
Tags: combinatorics, Indonesia, Indonesia MO
04.10.2022 09:13
INAMO 2022/4 wrote: Given a regular $26$-gon. Prove that for any $9$ vertices of that regular $26$-gon, then there exists three vertices that forms an isosceles triangle. Hm We'll bash this problem -- mainly relying on symmetry to reduce bash as much as possible. But first, let's translate this into the following equivalent formulation: Equivalent Formulation wrote: Prove that for any $9$ numbers in $\mathbb{Z}/26\mathbb{Z}$, there exists three numbers that form an arithmetic progression. Among $9$ of these numbers; by PigeonHole Principle, $5$ of them will have the same residue modulo $2$. Therefore, it suffices to prove that for any $5$ numbers in $\mathbb{Z}/13\mathbb{Z}$, there exists three numbers that form an arithmetic progression and combining this with the fact that they are all the same residue modulo $2$, we are done. Suppose otherwise, that there exists a set $\mathcal{S}$ of $5$ numbers in $\mathbb{Z}/13\mathbb{Z}$ such that any three numbers do not form an arithmetic progression. By shifting $x \mapsto ax + b$ if necessary, we can WLOG that $\{ 6, 7 \}$ lies on our set of five numbers $\mathcal{S}$. Since $6, 0, 7$ is an arithmetic progression, we conclude that $0 \notin \mathcal{S}$. Since $5, 6, 7$ is an arithmetic progression, we conclude that $5 \notin \mathcal{S}$. Since $6, 7, 8$ is an arithmetic progression, we conclude that $8 \notin \mathcal{S}$. Case 01. $4 \in \mathcal{S}$. We then have: Since $2, 4, 6$ is an arithmetic progression, we conclude that $6 \notin \mathcal{S}$. Since $4, 7, 10$ is an arithmetic progression, we conclude that $10 \notin \mathcal{S}$. Since $1, 4, 7$ is an arithmetic progression, we conclude that $1 \notin \mathcal{S}$. Since $7, 12, 4$ is an arithmetic progression, we conclude that $12 \notin \mathcal{S}$. which leaves us with $3, 9$ and $11$ as our possible choices of the remaining two elements in $\mathcal{S}$. However, If $9, 11 \in \mathcal{S}$, then $7, 9, 11$ is an arithmetic progression. If $9, 3 \in \mathcal{S}$, then $3, 6, 9$ is an arithmetic progression. If $3, 11 \in \mathcal{S}$, then $3, 7, 11$ is an arithmetic progression. Case 02. $4 \notin \mathcal{S}$. By symmetry, $9 \notin \mathcal{S}$ as well. Then, the only possible elements for $\mathcal{S}$ are from $1, 2, 3, 10, 11, 12$. If $3 \in \mathcal{S}$, as $3, 7, 11$ and $7, 3, 12$ are arithmetic progressions then $11, 12 \notin \mathcal{S}$. Thus, the remaining elements are from $1, 2$ and $10$. If $1, 2 \in \mathcal{S}$, then $1, 2, 3$ is an arithmetic progression. If $1, 10 \in \mathcal{S}$, then $1, 10, 6$ is an arithmetic progression. If $2, 10 \in \mathcal{S}$, then $2, 6, 10$ is an arithmetic progression. Thus, $3 \notin \mathcal{S}$ and by symmetry $10 \notin \mathcal{S}$. Now, the only possible three elements for $\mathcal{S}$ are from $1, 2, 11, 12$. Pair them as $\{ 1, 11 \}$ and $\{ 2, 12 \}$. By Pigeon Hole Principle, one of these two pairs will get selected. But either of these possibilities fails as $1, 6, 11$ and $2, 7, 12$ are arithmetic progressions.
04.10.2022 09:20
IndoMathXdZ wrote: INAMO 2022/4 wrote: Given a regular $26$-gon. Prove that for any $9$ vertices of that regular $26$-gon, then there exists three vertices that forms an isosceles triangle. Hm We'll bash this problem -- mainly relying on symmetry to reduce bash as much as possible. But first, let's translate this into the following equivalent formulation: Equivalent Formulation wrote: Prove that for any $9$ numbers in $\mathbb{Z}/26\mathbb{Z}$, there exists three numbers that form an arithmetic progression. Among $9$ of these numbers; by PigeonHole Principle, $5$ of them will have the same residue modulo $2$. Therefore, it suffices to prove that for any $5$ numbers in $\mathbb{Z}/13\mathbb{Z}$, there exists three numbers that form an arithmetic progression and combining this with the fact that they are all the same residue modulo $2$, we are done. Suppose otherwise, that there exists a set $\mathcal{S}$ of $5$ numbers in $\mathbb{Z}/13\mathbb{Z}$ such that any three numbers do not form an arithmetic progression. By shifting $x \mapsto ax + b$ if necessary, we can WLOG that $\{ 6, 7 \}$ lies on our set of five numbers $\mathcal{S}$. Since $6, 0, 7$ is an arithmetic progression, we conclude that $0 \notin \mathcal{S}$. Since $5, 6, 7$ is an arithmetic progression, we conclude that $5 \notin \mathcal{S}$. Since $6, 7, 8$ is an arithmetic progression, we conclude that $8 \notin \mathcal{S}$. Case 01. $4 \in \mathcal{S}$. We then have: Since $2, 4, 6$ is an arithmetic progression, we conclude that $6 \notin \mathcal{S}$. Since $4, 7, 10$ is an arithmetic progression, we conclude that $10 \notin \mathcal{S}$. Since $1, 4, 7$ is an arithmetic progression, we conclude that $1 \notin \mathcal{S}$. Since $7, 12, 4$ is an arithmetic progression, we conclude that $12 \notin \mathcal{S}$. which leaves us with $3, 9$ and $11$ as our possible choices of the remaining two elements in $\mathcal{S}$. However, If $9, 11 \in \mathcal{S}$, then $7, 9, 11$ is an arithmetic progression. If $9, 3 \in \mathcal{S}$, then $3, 6, 9$ is an arithmetic progression. If $3, 11 \in \mathcal{S}$, then $3, 7, 11$ is an arithmetic progression. Case 02. $4 \notin \mathcal{S}$. By symmetry, $9 \notin \mathcal{S}$ as well. Then, the only possible elements for $\mathcal{S}$ are from $1, 2, 3, 10, 11, 12$. If $3 \in \mathcal{S}$, as $3, 7, 11$ and $7, 3, 12$ are arithmetic progressions then $11, 12 \notin \mathcal{S}$. Thus, the remaining elements are from $1, 2$ and $10$. If $1, 2 \in \mathcal{S}$, then $1, 2, 3$ is an arithmetic progression. If $1, 10 \in \mathcal{S}$, then $1, 10, 6$ is an arithmetic progression. If $2, 10 \in \mathcal{S}$, then $2, 6, 10$ is an arithmetic progression. Thus, $3 \notin \mathcal{S}$ and by symmetry $10 \notin \mathcal{S}$. Now, the only possible three elements for $\mathcal{S}$ are from $1, 2, 11, 12$. Pair them as $\{ 1, 11 \}$ and $\{ 2, 12 \}$. By Pigeon Hole Principle, one of these two pairs will get selected. But either of these possibilities fails as $1, 6, 11$ and $2, 7, 12$ are arithmetic progressions. good point, but remember that ${1,2,4,8,13}$ does not have any arithmetic progression so there's a bit of a flaw here though, proving that 3 out of 9 points where 5 of them contains those 5 numbers form an arithmetic progression is kinda easy edit: i just realised $13, 1, 2$ technically form one lol
04.10.2022 18:13
The original problem is: given a regular 26-gon, determine the maximal number of vertices such that any 3 of them do not form an isosceles. So it's a bit harder than the way it was phrased here. First you have to realize that the answer is 8, give a construction of 8 vertices who do not contain an arithmetic progression, and then prove that for any 9 there will be an arithmetic progression. Once you realize the answer is 8 however, proving that 9 will always contain an arithmetic progression is not hard, especially when framed in Z/13Z as above. I'm trying to generalize it to any regular $4n+2$ gon and hoping to find a pattern.
02.08.2023 08:02
are there any other solution?