Условие
В городе Цветочном
n площадей и
m улиц (
m ≥
n + 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 |
