0
$\begingroup$

Let $n$ be a positive integer. There are $11n$ points arranged around a circle. Each point is colored with one of $n$ colors so that each color appears exactly $11$ times. Show that we can select $n$ points, one of every color, so that no two are adjacent.

I view the problem as a graph. Each point has two edges to the adjacent points. We must select an independent set (i.e., no two selected vertices are connected by an edge) with exactly one vertex of each color. But how?

$\endgroup$
2
$\begingroup$

This is an application of Lovasz Local Lemma. Check out the following Wikipedia article. http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma#Example

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.