358
471
всего разделов:
активных пользователей:
30 мартра 2005
Форумы снова функционируют.
21 декабря 2004
Видимо в связи с обнаруженными дырами в phpBB, форум был взломан, а через него взломано и всё остальное содержимое ceemat.ru. Всё кроме форума восстановлено, ведется дискуссия по поводу его сохранения.
Приносим извинения за неудобства.
29 сентября 2004
Форум обновился до версии 2.0.10
15 мая 2004
Новый раздел: "Программирование"
16 апреля 2004 года
Задачи Ярославского турнира математических боев — 124 задачи с решениями.
29 марта 2004
Таллинская викторина: занимательные вопросы и задачи для увлеченных химией.
Вторая лига (8)
Имеется 2002 точки, никакие три из которых не лежат на одной прямой. Каждая пара точек соединена отрезком. Можно ли окрасить каждый отрезок в один из шести заданных цветов так, чтобы не оказалось ни одного треугольника, все стороны которого имеют одинаковые цвета? |
Ответ: нельзя. Пусть отрезки удалось раскрасить указанным образом. Выберем произвольную точку и рассмотрим отрезки, соединяющие ее с остальными 2001 точками. По принципу Дирихле при окраске 2001-го отрезка в шесть цветов найдутся, по крайней мере, 334 точки, которые соединены с этой точкой отрезками одного и того же цвета (пусть это цвет № 1). Тогда никакие две из этих 334 точек не могут быть соединены между собой отрезком цвета № 1, иначе найдется треугольник с одноцветными сторонами. Для соединения между собой выбранных 334-х точек допустимо использование только пяти цветов. Опять же выберем одну из них и рассмотрим соединение с ней оставшихся 333 точек. По принципу Дирихле имеется 67 точек, которые соединены с ней отрезками одного цвета (пусть это цвет № 2). Отрезки, соединяющие указанные 67 точек, не могут быть окрашены ни в цвет № 1, ни в цвет № 2. Аналогично выберем из этих 67 точек одну точку и рассмотрим соединение с ней оставшихся 66 точек. Имеется не меньше 17-ти точек, которые соединены с ней отрезками одного цвета (цвет № 3). Из этих 17 точек выберем одну точку и рассмотрим соединение с ней оставшихся 16 точек. Имеется не меньше 6 точек, которые соединены с ней отрезками одного цвета (цвет № 4). Из этих 6 точек выберем одну точку и рассмотрим соединение с ней оставшихся пяти точек. Найдутся три точки, которые соединены с ней отрезками одного цвета (цвет № 5). Эти три точки могут быть соединены только отрезками последнего оставшегося цвета, то есть треугольник с одноцветными сторонами найдется. Противоречие. Таким образом, предположение было неверным, и раскрасить отрезки указанным в условии образом невозможно. |
Автор: И. Акулич. |
28 Февраля 2004 22:25 Раздел каталога :: Ссылка на задачу
|