ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109587
Темы:    [ Раскраски ]
[ Правило произведения ]
[ Задачи с ограничениями ]
[ Теория графов (прочее) ]
[ Процессы и операции ]
Сложность: 4+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

В городе Цветочном n площадей и m улиц  (mn + 1).  Каждая улица соединяет две площади и не проходит через другие площади. По существующей в городе традиции улица может называться либо Синей, либо Красной. Ежегодно в городе происходит переименование: выбирается площадь и переименовываются все выходящие из неё улицы. Докажите, что можно назвать улицы так, что переименованиями нельзя добиться одинаковых названий у всех улиц города.


Решение

  Заметим, что существует всего 2m способов присвоения названий улицам (для краткости будем называть их раскрасками). Оценим количество K раскрасок, которые можно получить с помощью переименований из раскраски, для которой все улицы красные. Раскраска, полученная после серии переименований, не зависит от порядка, в котором эти переименования были произведены. Кроме того, можно считать, что каждая площадь выбирается не более одного раза (если площадь выбирается дважды, то все улицы сохранят свои прежние названия). Поэтому  K ≤ 2n,  так как раскраска определяется подмножеством выбираемых площадей. Заметим еще, что если провести n переименований, по одному для каждой площади, то каждая улица будет переименована два раза и поэтому сохранит свое название. Следовательно,  K ≤ 2n – 1.  Аналогично если все улицы были синими, то с помощью переименований можно получить не более  2n – 1  раскрасок. В сумме получается не более  2(2n – 1) < 2n+1 ≤ 2m  раскрасок, следовательно, какую-то раскраску A нельзя получить с помощью переименований из раскраски, для которой все улицы названы одинаково.
  Значит, из раскраски A нельзя получить "одноцветную" раскраску (если из A можно получить раскраску B, то, повторив те же действия, мы из B получим A).

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1994
Этап
Вариант 4
класс
Класс 10
задача
Номер 94.4.10.8

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .