|
|
 |
Условие
Дано n фишек нескольких цветов, причём фишек каждого цвета неРешение
Первое решение. Будем считать, что если рядом стоят две фишки одинакового цвета, то они соединены дугой. Тогда нам нужно доказать, что существует такая расстановка фишек на окружности, в которой нет дуг.
Пусть имеется какая-то расстановка фишек по кругу; докажем, что фишки
можно переставить таким образом, что в новой расстановке число дуг уменьшится.
В самом деле, пусть, например, в расстановке две черные фишки соединены дугой.
Тогда на окружности обязательно найдутся две нечерные фишки, стоящие рядом.
Действительно, если бы рядом с каждой нечерной фишкой стояли черные, да еще
две черные стояли рядом, то черных фишек было бы больше половины, а это
противоречит условию.
Возьмем теперь одну из упомянутых нечерных фишек и поставим ее между двумя
черными. При этом число дуг в новой расстановке, очевидно, уменьшится. Так
как число дуг в расстановке не может оказаться меньше нуля, то в конце концов
мы получим расстановку фишек на окружности без дуг.
Второе решение. Будем доказывать утверждение задачи индукцией по
числу k различных цветов. Когда k=2 , утверждение очевидно: в этом случае
фишек каждого цвета должно быть , и их можно расставить
в чередующемся порядке. Если у нас имеются фишки k=3 цветов, скажем,
красного, черного и зеленого, будем действовать так. Начнем расставлять те фишки,
которых больше всего, например красные, через одну на нечетные места. Когда
красные фишки кончатся, будем продолжать расставлять на нечетные места черные
фишки. Ясно, что фишками двух цветов мы исчерпаем все нечетные места, остаток
черных фишек сможем поставить между красными, а на свободные (четные) места
сможем поставить зеленые фишки (рис.1).
Если число фишек k 4 , то найдутся два цвета таких, что фишек этих обоих
цветов будет не больше n/2 . Перекрасив эти фишки в один цвет, получим набор
фишек (k-1) цветов, для которого предположение индукции выполнено. Расставив
их по окружности так, чтобы выполнялось условие, и вернувшись к первоначальной
окраске, получим нужную расстановку фишек k цветов.
Третье решение. Возьмем n рыцарей, дадим каждому по фишке и объявим двух рыцарей врагами, если им достались фишки одного цвета, и друзьями– если разного. Тогда выполнены условия задачи M250 а); поэтому рыцарей с фишками можно рассадить за круглым столом.
