There is a stone at each vertex of a given regular $13$-gon, and the color of each stone is black or white. Prove that we may exchange the position of two stones such that the coloring of these stones are symmetric with respect to some symmetric axis of the $13$-gon.
Problem
Source: 2012 China Girl's Mathematical Olympiad
Tags: geometry, trapezoid, pigeonhole principle, inequalities, combinatorics unsolved, combinatorics
v_Enhance
13.08.2012 22:07
Let $b$ be the number of black rocks; without loss of generality, $b \le 6$ (otherwise we may reverse the colors of all the rocks.) We will do cases on $b$.
Define the midpoint of two black rocks $A$ and $B$ to be the unique vertex/rock $C$ such that $AC = BC$.
Case 1: $b \in \{0,1,2,3,4\}$. The first three are trivial; $b=3$ follows by moving one rock to the midpoint of the other two, and $b=4$ is immediate by constructing an isosceles trapezoid.
Case 2: $b=5$. If we can find either an isosceles trapezoid or an isosceles triangle, we are done. Suppose there are no isosceles triangles. For each of the $\binom{5}{2} = 10$ pairs of rocks, draw an $X$ (in black marker) on the midpoint of that pair. Since there are no isosceles triangles, all black ink is visible. Since $10 > 13 - 5$, there must be a white rock with at least two $X$'s on it. This produces the required isosceles trapezoid.
Case 3: $b=6$. It suffices to find an isosceles trapezoid. Draw $X$'s as above for each of the $\binom{6}{2} = 15 > 13$ pairs of rocks, but this time in red marker (since it's possible, even probable, that we'll be drawing on black rocks). Again, two $X$'s coincide, producing the required isosceles trapezoid.
Cyclicduck
15.08.2012 22:17
I practically did it the same way, except for when b=5 I considered the 8 white rocks. There are a total of $\dbinom{8}{2}=28$ pairs, and a total of 13 lines of symmetry. By pigeonhole, 3 of them coincide so we can simply move the other pair to coincide.
cadiTM
18.08.2012 09:02
I found a nice one..
Let 13 stones $a_1 ,a_2 , \cdots , a_{13}$ and define $x_i$ as the number of pairs, which is symmetric to the symmetric axis passing $a_i$, with same colors. For example, if $a_1 , \cdots,a_6$ is black and $a_7 , \cdots,a_{13}$ is white, $x_3 =5 ((a_2 , a_4 ), (a_1 , a_5 ) , (a_{12} , a_7 ) , (a_{11} , a_8 ) , (a_{10} , a_9 ))$
We can easily show that if there exists an $i$ such that $x_i \ge 4$, then we can change one or no pairs of stones to satisfy the condition.
Now assume that for all $i$, $x_i \le 3$. Then $\sum x_i \le 39$.
However, each pair of stones with same color appears only once in this summation(because 13 is odd!), so $\sum x_i = \binom{b}{2} + \binom{w}{2} \ge 36$ ($b$ and $w$ means the number of black and white stones, respectively)
From these two inequalities, we obtain that there are at least 10 $i$'s such that $x_i = 3$. From the following claim, we can get there are at least 10 stones with same color, then $\sum x_i \ge \binom {10}{2}+\binom{3}{2}>39$. Contradiction.
(Claim) If $x_i = x_j $, then $a_i $ and $a_j $ have the same color. (Indeed, It is sufficient that $x_i $ and $x_j $ have the same parity)
Proof of claim. Let $x_i = x_j =y$. Then 12 stones, where $a_i$ is excluded, are consist of $y$ pairs with same color, and $6-y$ pairs with different colors, white and black. So these 12 stones are consist of $6-y+2k$ white stones and $6-y+2l$ black stones. Similarly, 12 stones, where $a_j$ is excluded, are consist of $6-y+2p$ white stones and $6-y+2q$ black stones. Considering the parity, we can conclude that $a_i$ and $a_j$ have the same color.
john0512
16.12.2023 06:48
Suppose not, we will use a global approach. Let the polygon be $P_1P_2\dots P_{13}$, and label each vertex with either 0 or 1. Consider an orientation of the polygon with $P_i$ as the tip, and consider pairs of points at the same height. If each of these pairs have two of the same label, we are already done as it is already symmetric so we just make a swap that does nothing. If exactly one of these pairs have different labels, then we swap out the one that is different from $P_i$ with $P_i$ to fix it. If exactly two of these pairs are mismatched, we swap them with each other. Therefore, since we are assuming the contrary, each orientation must have at least 3 differing pairs. Summing over all orientations, there are at least 39 pairs of points of different labels. WLOG there are more 1 labels than 0 labels. Then, the product of the number of 0 labels and number of 1 labels is at least 39, so there are either 5 or 6 0 labels. Case 1: there are 5 labels of $0$ and 8 labels of $1$. Orient the polygon so that a 0 is at the top. Since there are 4 0s remaining, which is even, there must be an even number of pairs with exactly one 0. However, since we know that there are at least 3 such pairs, there are also at least 4. This is true of all of the orientations with 0 at the top, so there are at least $5\cdot 4+8\cdot 3=44$ pairs of different labeled points, contradiction. Case 2: there are 6 labels of $0$ and 7 labels of $1$. This time, orient it so that 1 is at the top. Again there are 6 1s left, so there are an even number of different pairs, so there are at least 4. This is true for any of these 7 orientations, so there are at least $4\cdot 7+3\cdot 6=46$ pairs of different labels, contradiction.
HamstPan38825
07.01.2024 00:01
I found this fairly straightforward. WLOG the number of white stones is even. Label the vertices of the regular $13$-gon $0, 1, 2, 3, \dots, 12$, and let $S$ be the set of positions of all the white stones. The configuration will be symmetric if there exists a residue $k$ such that $S$ can be partitioned into pairs summing to $k$. In particular, let $|S| = 2n$. Consider the set of all ${2n \choose 2}$ sums of pairs of elements in $S$. Notice that for $n \geq 2$, we have ${2n \choose 2} \geq 13(n-2)$, which implies by Pigeonhole that there exist $n-1$ pairs in $S$ that sum to the same residue modulo $13$. If all $n$ pairs sum to that residue, then we may arbitrarily exchange some two white stones; otherwise, we may swap the white stone located at one of the locations in the remaining pair to the position for which that pair also sums to $k$. (This new position is guaranteed to not already be in $S$.) This finishes the problem.