0

We have a regular polygon with $2K$ vertices that are coloured in $2K$ different colours(one vertex - one colour). There is another regular polygon with $2K$ vertices that are coloured in $2K$ different colours that overlaps the previous one (colours are the same, but vertex, that was coloured in the first polygon in red, for example, now has different color in that second polygon). Prove that we can rotate the second polygon such way, that there will be at least two places where the colour of a vertex of the first polygon will be the same as the colour of a vertex of the second polygon.

King Crimson
  • 218
  • The singular of "vertices" is "vertex". – saulspatz Aug 07 '21 at 19:28
  • How far can you get? Can you prove it when $K=2$? When $K=3$? – saulspatz Aug 07 '21 at 21:20
  • @saulspatz, Yep, that is exactly the problem, i cannot prove it for K>2. The proof for K=2 is pretty simple. Let's write down numbers instead of colours for the sake of comfort. There can be exactly n!/2n different variants of renumbering the vertices, where n is the total number of our vertices. We take each variant and look into it. But that is obviously just brute forcing. But it might somehow be connected with the problem of renumbering the cycle Cn, pretty simple problem in graph theory, formula n!/2n comes from that problem – King Crimson Aug 10 '21 at 13:54
  • 1
    The statement is false when the polygon has an odd number of sides, so the parity must play some role in the proof. The first thing that leaps to mind is that we can partition the vertices into pairs of opposite vertices, but I don't see how to exploit that. It may be a blind alley. – saulspatz Aug 10 '21 at 14:49

1 Answers1

1

I will number the vertices rather than coloring them.

Let $n=2K$. Number the vertices of one polygon $0,1,2\dots,n-1$ in clockwise order. Number the vertices of the other polygon according to some permutation $\pi$ of $\{0,1,2,\dots,n-1\}$. If we rotate the second polygon $d$ spaces, and two pairs of corresponding vertices are colored the same, this mean that for some $k\neq m$, $$\pi(k+d)=k\\ \pi(m+d)=m$$ All operations are modulo $n$.

If the theorem is false, then for every $d,i,j$ if $\pi(i+d)=i$ and $i\neq j$ then $\pi(j+d)\neq j$. If we write $k=i+d,\ m=j+d$ we have $$\pi(k)-k=-d\neq \pi(m)-m$$ That is, $f:\mathbb Z_m\to\mathbb Z_n$ given by $$f(i)=\pi(i)-i$$ is an injection, hence a bijection.

This cannot be so if $n$ is even. $$\sum_{i\in\mathbb Z_n}\pi(i)-i=\sum_{i\in\mathbb Z_n}\pi(i)-\sum_{i\in\mathbb Z_n}i=0$$ because $\pi$ is a bijection so that $$\sum_{i\in\mathbb Z_n}\pi(i)=\sum_{i\in\mathbb Z_n}i$$

On the other hand, since $f$ is a bijection, $$\sum_{i\in\mathbb Z_n}\pi(i)-i=\sum_{i\in\mathbb Z_n}i=K$$ This is so because every element of $\mathbb Z_n$ other than $0$ and $K$ cancels with its additive inverse.

This contradiction proves the theorem.

saulspatz
  • 53,131