Разделы 
Дополнительно
Задача по математике - 1220
2018-11-02 
В городе Цветочном n площадей и m улиц $ (m \geq n +1) $. Каждая улица соединяет две площади и не проходит через другие площади. По существующей в городе традиции улица может называться либо синей, либо красной. Ежегодно в городе происходит переименование: выбирается площадь и переименовываются все выходящие из нее улицы. Докажите, что вначале можно назвать улицы так, что переименованиями нельзя добиться одинаковых названий у всех улиц города.
Решение:
Заметим, что существует всего $2^{m}$ способов присвоения названий улицам (для краткости будем называть их раскрасками).
Оценим количество K раскрасок, которые можно получить с помощью переименований из раскраски, для которой все улицы красные. Раскраска, полученная после серии переименований, не зависит от порядка, в котором эти переименования были произведены. Кроме того, можно считать, что одна площадь не выбирается более одного раза, так как если площадь выбирается дважды, то все улицы сохранят свои прежние названия. Поэтому $K\leq 2^{n}$, так как раскраска определяется подмножеством выбираемых площадей. Заметим еще, что если провести n переименований, по одному для каждой площади, то каждая улица будет переименована два раза и поэтому сохранит свое название. Следовательно, $K \leq 2^{n} - 1$.
Аналогично, если все улицы были синими, то с помощью переименований можно получить не более $2^{n} - 1$ раскрасок. В сумме получается не более $2(2^{n} - 1)< 2^{n + 1}\leq 2^{m}$ раскрасок, следовательно, какую-то раскраску нельзя получить с помощью переименований из раскраски, для которой все улицы названы одинаково.
В городе Цветочном n площадей и m улиц $ (m \geq n +1) $. Каждая улица соединяет две площади и не проходит через другие площади. По существующей в городе традиции улица может называться либо синей, либо красной. Ежегодно в городе происходит переименование: выбирается площадь и переименовываются все выходящие из нее улицы. Докажите, что вначале можно назвать улицы так, что переименованиями нельзя добиться одинаковых названий у всех улиц города.
Решение:
Заметим, что существует всего $2^{m}$ способов присвоения названий улицам (для краткости будем называть их раскрасками).
Оценим количество K раскрасок, которые можно получить с помощью переименований из раскраски, для которой все улицы красные. Раскраска, полученная после серии переименований, не зависит от порядка, в котором эти переименования были произведены. Кроме того, можно считать, что одна площадь не выбирается более одного раза, так как если площадь выбирается дважды, то все улицы сохранят свои прежние названия. Поэтому $K\leq 2^{n}$, так как раскраска определяется подмножеством выбираемых площадей. Заметим еще, что если провести n переименований, по одному для каждой площади, то каждая улица будет переименована два раза и поэтому сохранит свое название. Следовательно, $K \leq 2^{n} - 1$.
Аналогично, если все улицы были синими, то с помощью переименований можно получить не более $2^{n} - 1$ раскрасок. В сумме получается не более $2(2^{n} - 1)< 2^{n + 1}\leq 2^{m}$ раскрасок, следовательно, какую-то раскраску нельзя получить с помощью переименований из раскраски, для которой все улицы названы одинаково.
