Выбрано 6 задач 
Убрать все задачи
Миша написал на доске в некотором порядке 2004 плюса и 2005 минусов. Время от времени Юра подходит к доске, стирает любые два знака и пишет вместо них один, причём если он стёр одинаковые знаки, то вместо них он пишет плюс, а если разные, то минус. После нескольких таких действий на доске остался только один знак. Какой?
Две окружности w1 и w2 пересекаются в точках A и B. К ним через точку A проводятся касательные l1 и l2 (соответственно). Перпендикуляры, опущенные из точки B на l2 и l1, вторично пересекают окружности w1 и w2 соответственно в точках K и N. Докажите, что точки K, A и N лежат на одной прямой.
Пешеход обошёл шесть улиц одного города, пройдя каждую ровно два раза, но не смог обойти их, пройдя каждую лишь раз. Могло ли это быть?
Четырёхугольник ABCD вписан в окружность. Перпендикуляр, опущенный из вершины C на биссектрису угла ABD, пересекает прямую AB в точке C1; перпендикуляр, опущенный из вершины B на биссектрису угла ACD, пересекает прямую CD в точке B1. Докажите, что B1C1 || AD.
Юра, Лёша и Миша коллекционируют марки. Количество Юриных марок, которых нет у Лёши, меньше, чем количество марок, которые есть и у Юры, и у Лёши. Точно так же, число Лёшиных марок, которых нет у Миши, меньше, чем число марок, которые есть и у Лёши и у Миши. А число Мишиных марок, которых нет у Юры, меньше, чем число марок, которые есть и у Юры и у Миши. Докажите, что какая-то марка есть у каждого из трех мальчиков.
В городе Цветочном n площадей и m улиц (m ≥ n + 1). Каждая улица соединяет две площади и не проходит через другие площади. По существующей в городе традиции улица может называться либо Синей, либо Красной. Ежегодно в городе происходит переименование: выбирается площадь и переименовываются все выходящие из неё улицы. Докажите, что можно назвать улицы так, что переименованиями нельзя добиться одинаковых названий у всех улиц города.
|
|
 |
Условие
В городе Цветочном 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).
