Олимпиадные задачи по математике
В некоторой стране есть столица и еще 100 городов. Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.
Дима, приехав из Врунляндии, рассказал, что там есть несколько озер, соединённых между собой реками. Из каждого озера вытекают три реки, и в каждое озеро впадают четыре реки. Докажите, что он ошибается.
Каждое из рёбер полного графа с 18 вершинами покрашено в один из двух цветов.
Докажите, что есть четыре вершины, все рёбра между которыми – одного цвета.
Каждое из рёбер полного графа с 9 вершинами покрашено в синий или красный цвет.
Докажите, что либо есть четыре вершины, все рёбра между которыми – синие, либо есть три вершины, все рёбра между которыми – красные.
Каждое из рёбер полного графа с 17 вершинами покрашено в один из трёх цветов. Докажите, что есть три вершины, все рёбра между которыми – одного цвета.
Каждое из рёбер полного графа с 6 вершинами покрашено в один из двух цветов.
Докажите, что есть три вершины, все рёбра между которыми – одного цвета.
В некоторой стране каждые два города соединены либо авиалинией, либо железной дорогой. Докажите, что
а) можно выбрать вид транспорта так, чтобы от каждого города можно было добраться до любого другого, пользуясь только этим видом транспорта;
б) из некоторого города, выбрав один из видов транспорта, можно добраться до любого другого города не более чем с одной пересадкой (пользоваться можно только выбранным видом транспорта);
в) каждый город обладает свойством из пункта б);
г) можно выбрать вид транспорта так, чтобы пользуясь только им, можно было добраться из каждого города до любого другого не более чем с двумя пересадками.
Дима нарисовал на доске семь графов, каждый из которых является деревом с шестью вершинами. Докажите, что среди них есть два изоморфных.
<i>Расстоянием</i> между двумя произвольными вершинами дерева будем называть длину простого пути, соединяющего их. <i>Удалённостью</i> вершины дерева назовём сумму расстояний от неё до всех остальных вершин. Докажите, что в дереве, у которого есть две вершины с удалённостями, отличающимися на 1, нечётное число вершин.
Каждый из 102 учеников одной школы знаком не менее чем с 68 другими.
Докажите, что среди них найдутся четверо, имеющие одинаковое число знакомых.
На конференции присутствуют 50 учёных, каждый из которых знаком по крайней мере с 25 участниками конференции.
Докажите, что найдутся четверо из них, которых можно усадить за круглый стол так, чтобы каждый сидел рядом со знакомыми ему людьми.
Докажите, что связный граф с 2<i>n</i> нечётными вершинами можно нарисовать, оторвав карандаш от бумаги ровно <i>n</i> –1 раз и не проводя никакое ребро дважды.
На плоскости дано 100 окружностей, составляющих связную (то есть не распадающуюся на части) фигуру.
Докажите, что эту фигуру можно нарисовать, не отрывая карандаша от бумаги и не проводя дважды одну и ту же линию.
Можно ли составить решётку, изображённую на рисунке
а) из пяти ломаных длины 8?
б) из восьми ломаных длины 5?
(Длина стороны клетки равна 1.) <div align="center"><img width="113" height="113" align="BOTTOM" border="0" src="/storage/problem-media/30807/problem_30807_img_2.gif"> </div>
Докажите, что связный граф, имеющий не более двух нечётных вершин, можно нарисовать, не отрывая карандаша от бумаги и проводя каждое ребро ровно один раз.
Семиугольник разбит на выпуклые пяти- и шестиугольники, причём так, что каждая его вершина является вершиной по крайней мере двух многоугольников разбиения. Докажите, что число пятиугольников разбиения не меньше 13.
Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий.
Докажите, что либо "красный", либо "синий" граф не является плоским.
Докажите, что в плоском графе есть вершина, степень которой не превосходит 5.
Докажите, что граф, имеющий 10 вершин, степень каждой из которых равна 5, – не плоский.
Можно ли построить три дома, вырыть три колодца и соединить тропинками каждый дом с каждым колодцем так, чтобы тропинки не пересекались?
Докажите, что граф, имеющий пять вершин, каждая из которых соединена ребром со всеми остальными, не является плоским.
Докажите, что для любого плоского графа (в том числе и несвязного) справедливо неравенство <i>E</i> ≤ 3<i>V</i> – 6.
Докажите, что для плоского связного графа справедливо неравенство <i>E</i> ≤ 3<i>V</i> – 6.
Докажите, что для плоского графа справедливо неравенство 2<i>E</i> ≥ 3<i>F</i>.
В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?