Задача М251‍‍

Первое решение. Будем считать, что если рядом стоят две фишки одинакового цвета, то они соединены дугой. Тогда нам нужно доказать, что существует такая расстановка фишек на окружности, в которой нет дуг.

Пусть имеется какая‑то расстановка фишек по кругу; докажем, что фишки можно переставить таким образом, что в новой расстановке число дуг уменьшится.

В самом деле, пусть, например, в расстановке две чёрные фишки соединены дугой. Тогда на окружности обязательно найдутся две нечёрные фишки, стоящие рядом. Действительно, если бы рядом с каждой нечёрной фишкой стояли чёрные, да ещё две чёрные стояли рядом, то чёрных фишек было бы больше половины, а это противоречит условию.

Возьмём теперь одну из упомянутых нечёрных фишек и поставим её между двумя чёрными. При этом число дуг в новой расстановке, очевидно, уменьшится. Так как число дуг в расстановке не может оказаться меньше нуля, то в конце концов мы получим расстановку фишек на окружности без дуг.

Второе решение. Будем доказывать утверждение задачи индукцией по числу $k$‍‍ различных цветов. Когда $k=2$‍,‍ утверждение очевидно: в этом случае фишек каждого цвета должно быть $\dfrac{n}{2}$‍,‍ и их можно расставить в чередующемся порядке. Если у нас имеются фишки $k=3$‍‍ цветов, скажем, красного, чёрного и зелёного, будем действовать так. Начнём расставлять те фишки, которых больше всего, например красные, — через одну на нечётные места. Когда красные фишки кончатся, будем продолжать расставлять на нечётные места чёрные фишки. Ясно, что фишками двух цветов мы исчерпаем все нечётные места, остаток чёрных фишек сможем поставить между красными, а на свободные (чётные) места сможем поставить зелёные фишки (рис. 1).

Если число цветов $k\ge4$‍,‍ то найдутся два цвета таких, что фишек этих обоих цветов будет не больше $\dfrac{n}{2}$‍.‍ Перекрасив эти фишки в один цвет, получим набор фишек $k-1$‍‍ цветов, для которого предположение индукции выполнено. Расставив их по окружности так, чтобы выполнялось условие, и вернувшись к первоначальной окраске, получим нужную расстановку фишек $k$‍‍ цветов.

Третье решение. Возьмём $n$‍‍ рыцарей, дадим каждому по фишке и объявим двух рыцарей врагами, если им достались фишки одного цвета, и друзьями — если разного. Тогда выполнены условия задачи М250; поэтому рыцарей с фишками можно рассадить за круглым столом.