Prove that it in a regular 100-gon where each vertices is colored in one of 10 colors, there exists a rectangle colored in at most 2 colors.

Question

All vertices of a regular 100-gon are colored in 10 colors. Prove that there exist 4 vertices of the given 100-gon which are the vertices of a rectangle and which are colored in at most 2 colors.

Tried finding the proof using pigeon-hole principle, but I’m not getting it.

Answer 1

There are 50 pairs of opposite points. A rectangle will select two of these pairs.

Some pairs might be a single color. If so, pick one: for there to be no two-color rectangle including this pair, there must be 1. no other points in the entire circle with this color and 2. no other pairs of points that are both the same color. -- but there's only $8\times9\div2 = 36$ remaining and $49$ pairs to pick, so by pigeonhole we're stuck and have to have two pairs that have matching colors.

If not, and every opposite pair has two different colors represented, there are only $9\times10\div2 = 45$ such pairs of colors and $50$ pairs to pick, so by pigeonhole we're again stuck and have to have two pairs that have matching colors.