2
$\begingroup$

I'm asked to find whether a certain partition exists. The set which I am partitioning is the set of vertices of a regular n-gon. There are to be two sets in the partition and no three vertices in either can form an isosceles triangle.

I can partition for n=3, 4, 6 and 8. I think that's it.

Thanks in advance.

  • 0
    It sounds like you're doing Ramsey theory. Have you covered [Van der Waerden's theorem](http://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem)? (Not that I'd suggest using it if you haven't, but the easy case does finish off the problem pretty quickly).2011-05-09

1 Answers 1

2

Consider the vertices of the $n$-gon as members of the cyclic group $C_n$ of order $n$, which I'll write additively. Say $A$ and $B$ form your partition. For any distinct $a_1$, $a_2$ in $A$, $2 a_2 - a_1$ must be in $B$. Similarly, for any distinct $b_1$, $b_2$ in $B$, $2 b_2 - b_1$ must be in $A$. So you'd be in trouble if the sets $\{2 a_2 - a_1: a_1 \ne a_2 \in A\}$ and $\{2 b_1 - b_2: b_1 \ne b_2 \in B\}$ overlapped. So count the number of elements in these sets, noting that if $n$ is odd the map $x \to 2 x$ is one-to-one, while if $n$ is even that map is two-to-one. If the total is more than $n$, the partition can't exist.