Главная страница Карта сайта Контакты

Опросы

Довольны ли вы учебой?
 Да, конечно!
 Нормально
 Многое не устраивает
Голосовало : 2138

RSS / MAP


RSS - международный формат, специально созданный для трансляции данных с одного сайта на другой. 
Используя готовые экспортные файлы в формате RSS, вы можете разместить на своей странице заголовки и аннотации сюжетов наших новостей. 
Кроме того, посредством RSS можно читать новости специальными программами - агрегаторами новостей - и таким образом оперативно узнавать 
об обновлениях нужных сайтов.
Google SiteMap

О необыкновенных точках

Дано конечное множество черных и голубых точек. Некоторые точки соединены отрезками прямых. 

анализТочка множества называется «необыкновенной», если более половины исходящих из нее отрезков заканчиваются в точках другого цвета, чем она. Если в данном множестве точек имеются необыкновенные точки, то, выбрав любую из них, перекрасим ее в другой цвет. Тоже повторим и с полученными точками, если в нем существуют необыкновенные точки, и т. д.

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

Назовем отрезок, соединяющий две точки, «двуцветным», если он соединяет голубую точку с черной или черную точку с голубой, и «одноцветным», если он соединяет 2 голубые или 2 черные точки. Точка является необыкновенной в том и только в том случае, если из нее двуцветных отрезков выходит больше.

Если необыкновенную точку перекрасить, то из нее будет выходить больше одноцветных отрезков, чем двуцветных, а все остальные отрезки, не выходящие из перекрашенной точки, останутся такими, какими были. Следовательно, какую бы точку не выбрать, перекрасив ее, мы уменьшим число двуцветных отрезков.

Если бы после конечного числа шагов исходное множество точек не перестало содержать необыкновенные точки, то это означало бы, что существует множество точек, в котором возможно бесконечное число перекрашиваний. Но тогда должна была бы существовать бесконечная строго убывающая последовательность натуральных чисел (каждое из которых соответствовало бы числу двуцветных отрезков), что невозможно. Противоречие которое получилось доказывает утверждение задачи.

Страниц: 1
 

   Введите слово для поиска