Rambler's Top100 Service
Поиск   
 
Обратите внимание!   Обратите внимание!
 
  Наука | Задачи
 Написать комментарий  Добавить новое сообщение
перекрашивание точек
22.01.2001 0:00 | МЦНМО

    На плоскости даны 10 точек: несколько из них - белые, а остальные - черные. Некоторые точки соединены отрезками. Назовем точку особой, если более половины соединенных с ней точек имеют цвет, отличный от ее цвета. Каждым ходом выбирается одна из особых точек (если такие есть) и перекрашивается в противоположный цвет. Докажите, что через несколько ходов не останется ни одной особой точки.
  • Хочу подсказку


  •     Решение:
    Допустим, что в какой-то момент мы перекрашиваем особую точку A (для определенности, пусть эта особая точка до перекрашивания была белой). Пусть точка A соединена с m белыми и n черными точками; m<n согласно определению особой точки. Таким образом, среди отрезков, имеющих одним из концов точку A, до перекрашивания было m отрезков, имеющих два белых конца и n отрезков, имеющих один белый и один черный конец. После перекрашивания стало n отрезков, имеющих два белых конца и m отрезков, имеющих один белый и один черный конец. Мы видим, что после перекрашивания особой точки количество отрезков (среди всех данных отрезков, соединяющих 10 точек), имеющих один белый и один черный конец, уменьшается. Поскольку число отрезков конечно, такое уменьшение не может происходить бесконечно, следовательно через несколько перекрашиваний мы не сможем сделать больше ни одного нового перекрашивания, т.е. особых точек просто не останется.


    Написать комментарий
     Copyright © 2000-2015, РОО "Мир Науки и Культуры". ISSN 1684-9876 Rambler's Top100 Яндекс цитирования