Олимпиадная задача про переименования улиц города Цветочного. Классическая комбинаторика, 8–10 класс
Задача
В городе Цветочном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).
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь