Выбрано 7 задач 
Убрать все задачи
У Носорога на шкуре есть вертикальные и горизонтальные складки. Всего складок 17. Если Носорог чешется боком о дерево, то либо две горизонтальные, либо две вертикальные складки на этом боку пропадают, зато на другом боку прибавляются две складки: горизонтальная и вертикальная. (Если двух складок одного направления нет, то ничего не происходит.) Носорог почесался несколько раз. Могло ли случиться, что на каждом боку вертикальных складок стало столько, сколько там раньше было горизонтальных, а горизонтальных стало столько, сколько там было вертикальных?
На плоскости даны оси координат с одинаковым, но не
обозначенным масштабом и график функции
Как с помощью циркуля и линейки построить касательную к этому графику в заданной его точке, если: а) α
Несколько спортсменов стартовали одновременно с одного и того же конца прямой беговой дорожки. Их скорости различны, но постоянны. Добежав до конца дорожки, спортсмен мгновенно разворачивается и бежит обратно, затем разворачивается на другом конце, и т.д. В какой-то момент все спортсмены снова оказались в одной точке. Докажите, что такие встречи всех будут продолжаться и впредь.
На параболе y = x² выбраны четыре точки A, B, C, D так, что прямые AB и CD пересекаются на оси ординат.
Найдите абсциссу точки D, если абсциссы точек A, B и C равны a, b и c соответственно.
Тридцать три богатыря нанялись охранять Лукоморье за 240 монет. Хитрый дядька Черномор может разделить богатырей на отряды произвольной численности (или записать всех в один отряд), а затем распределить всё жалованье между отрядами.
Каждый отряд делит свои монеты поровну, а остаток отдаёт Черномору. Какое наибольшее количество монет может достаться Черномору, если:
а) жалованье между отрядами Черномор распределяет как ему угодно;
б) жалованье между отрядами Черномор распределяет поровну?
На стороне AC остроугольного треугольника ABC выбрана точка D. Медиана AM пересекает высоту CH и отрезок BD в точках N и K соответственно.
Докажите, что если AK = BK, то AN = 2KM.
В стране 100 городов, некоторые пары городов соединены дорогами. Для каждых четырёх городов существуют хотя бы две дороги между ними. Известно, что не существует маршрута, проходящего по каждому городу ровно один раз. Докажите, что можно выбрать два города таким образом, чтобы каждый из оставшихся городов был соединен дорогой хотя бы с одним из двух выбранных городов.
|
|
 |
Условие
В стране 100 городов, некоторые пары городов соединены дорогами. Для каждых четырёх городов существуют хотя бы две дороги между ними. Известно, что не существует маршрута, проходящего по каждому городу ровно один раз. Докажите, что можно выбрать два города таким образом, чтобы каждый из оставшихся городов был соединен дорогой хотя бы с одним из двух выбранных городов.
Решение
Рассмотрим граф, вершины которого соответствуют городам, а рёбра
– дорогам. Выберем в этом графе самый длинный путьS, пусть вершиныA и B – концы этого пути. Из условия следует, что в пути S не более 99 вершин.
Отметим, что концы пути S – вершины A и B – не могут быть смежны с вершинами не из S (иначе путь можно удлинить). А в случае, когда вершины A и B смежны и наш путь замыкается в цикл, никакая вершина пути S по аналогичным причинам не может быть смежна с вершиной не из S. Рассмотрим два случая.
1) В S не более 98 вершин. Рассмотрим любые две вершины Y1 и Y2, не входящие в путь S, и концы
пути A и B. Среди этих четырёх вершин должны быть проведены хотя бы два ребра. Так как ни A, ни B не могут быть смежны с вершинами
не из S, то A и B соединены ребром.
Таким образом, путь S замыкается в цикл, и тогда ни одна из вершин пути S не смежна с вершиной не из S.
Рассмотрим четвёрку из любых двух вершин X1 и X2 пути S и любых двух вершин Y1 и Y2, не входящих в S. Так как между этими четырьмя вершинами проведено хотя бы два ребра, то одно из них соединяет X1 и X2, а другое – Y1 и Y2. Таким образом, в рассматриваемом случае все вершины пути S попарно смежны и все вершины не из S также попарно смежны. Отсюда очевидно следует утверждение задачи.
2) Вне пути S лежит ровно одна вершина D.
Если D не смежна ни с одной из вершин пути S, то рассмотрим D и любые три вершины пути S. Поскольку среди этих четырёх вершин проведено хотя бы два ребра, то среди любых трёх вершин пути S проведено хотя бы два ребра. Следовательно, для любой вершины из S есть не более одной не смежной с ней вершины пути S . Поскольку 99 вершин пути S нельзя разбить на пары не соединённых ребром, то в S должна быть вершина, смежная со всеми остальными вершинами S. Эта вершина в паре с D удовлетворяет утверждению задачи.
Если концы максимального пути A и B смежны, то, как мы доказали, вершина D не смежна ни с одной из вершин пути S, а этот случай уже разобран.
Остается рассмотреть случай, когда концы пути S не смежны
и вершина D смежна хотя бы с одной из вершин X пути S. Рассмотрим вершины A, B, D и произвольную четвёртую вершину Z (естественно, лежащую на пути S).
Так как A, B и D попарно не смежны, то Z смежна хотя бы с двумя вершинами из A, B и D. Одна из соседних с X вершин пути S не является концом пути. Можно считать, что это первая вершина Y, лежащая на пути из X в B по рёбрам S.
Если Y смежна с D, то, пройдя от A к X по пути S, далее по рёбрам XD и DY и затем по пути S от Y к B, мы обойдём все вершины нашего графа ровно по одному разу, что невозможно по условию.
Если же Y не смежна с D, то, как мы доказали, эта вершина смежна и с A и с B. Тогда пройдём по ребру DX, далее по пути S от X к A, по рёбрам AY и YB, и затем по пути S от его конца B до вершины, соседней с Y на пути S, – снова получился путь, проходящий по каждой вершине нашего графа ровно один раз.
