Choose arbitrarily $n$ vertices of a regular $2n-$gon and colour them red. The remaining vertices are coloured blue. We arrange all red-red distances into a nondecreasing sequence and do the same with the blue-blue distances. Prove that the two sequences thus obtained are identical.
Problem
Source: Indian Postal Coaching 2012 Set 1 #4
Tags: geometry, combinatorics unsolved, combinatorics
AnonymousBunny
09.09.2015 23:06
I am not sure if my solution is correct, can anyone check this please? (Also, sorry to revive )
Let $f_1(k)$ denote the number of red pairs of points with distance $k$. Similarly define $f_2(k)$. We basically want to show that $f_1(k)= f_2(k)$ for all $k$. For now I assume $k \mid 2n$. Let $2n= mk$. Decompose the original polygon into $m$ smaller regular polygons, each with size $2k$, where the distance between any two consecutive points in a small polygon is equal to $k$ in the original polygon. For each point $P$, let its neighbors be the points just left and right to it in the smaller polygon it is in. Let $g(P)$ denote the number of neighbors of $P$ with the same color as $P$. We basically need to show that $\displaystyle \sum_{P \text{ is red}} g(P) = \displaystyle \sum_{P \text{ is blue}} g(P)$. Note that $g(P)= 2-h(P)$, where $h(P)$ is the number of neighbors of $P$ with a different color than $P$. So, we'll be done if we can show that $\displaystyle \sum_{P \text{ is red}} h(P) = \displaystyle \sum_{P \text{ is blue}} h(P)$. But this is true-- both sides count the number of consecutive pairs with different colors.
The case where $k \nmid 2n$ is dealt with similarly. Let the vertices be labeled $1, 2, \cdots , n$. The first small polygon will be the set $\{1, k+1 \pmod{2n}, \cdots , tk+1 \pmod{2n}\}$ (where $(t+1)k \equiv 0 \pmod{2n}$); the second small polygon will be the set $\{2, k+1 \pmod{2n}, \cdots , tk+2 \pmod{2n} \}$ and so on.
Chandrachur
12.09.2015 07:09
I think it is OK save some little typo-es like $2k$ in place of $k$. But the situation is way simpler and here is my solution. The idea is just Symmetry. . My solution Call any such arrangement of $n$ red and other blue points [where the sequences are as required] "Valid". We have to prove all such arrangements are valid. . Firstly we show that if we swap the colors of one red and one blue vertices with each other in a Valid arrangement the remaining arrangement is also Valid. For this we draw an axis of symmetry of the polygon for which the swapped points are symmetrical points. For a regular polygon we will always find such - join the midpoints of the arcs between these $2$ points.For $n$ odd that axis passes through $2$ vertex and for even $n$ it may pass through a vertex or the mid-point of a side[draw it and see]. The change in the distances between points, if occurs , involves the swapped vertices only as distances between others are unchanged as they are where they were. Now if symmetrical pairs about the axis are $(R,R)$ or $(B,B)$ then the previous sequences of red-red distances or blue-blue distances do not change. If some symmetrical pair is $(R,B)$ or $(B,R)$ then notice that it merely swaps two entries of distance in the red-red sequence and does the same swapping in the blue-blue sequence. So nothing is altered. When the axis passes through vertices the these vertex don't have a symmetrical pair but as the swapped points are swapped to symmetrical positions w.r.t these vertices so distance between them is unaltered. . Next we show such a Valid arrangement exists. This is trivial and take it to your convenience. I take the simplest arrangement where there are $n$ consecutive $Red$ points and other $n$ are blue. Clearly this is Valid. For rigor, reflect each point about an axis of symmetry which separates the blue from the red. So we get an arrangement where red and blue are all swapped with each and so there is clearly a bijection between the red and blue distances. . Lastly we show that we can reach any arrangement by swapping some red and blue from this arrangement. For visual clarity place this consecutive-colored arrangement with the axis of symmetry at the middle, red points on right and blue on left of it. Now similarly draw an axis of symmetry of the required arrangement. So to reach from here to there, we have to make some points on the right blue and some on the left red. By a trivial counting we see that the number of such blue and red points are same. [Else contradict in the otherwise case, simpler] So we just pair these $(R,B)$ points in any way and swap them with each other. As we attain the required arrangement from a Valid arrangement by swapping only so this arrangement is also Valid. . Phew done!!!