7 класс Группа "профи"("Ш")

Задачи по индукции для самостоятельного решения

1. 
   На плоскости расположено несколько прямых и окружностей. Докажите, что части, на которые они разбивают плоскость, можно покрасить в два цвета так, что любые две части, имеющие общий участок границы, покрашены в разные цвета.
   
2. 
   В прямоугольнике 3n (3 строки, n столбцов) расставлены фишки трех цветов по n штук каждого цвета. Докажите, что переставляя фишки в строчках, можно сделать так, чтобы в каждом столбце были фишки всех трех цветов.
   
3. 
   Отряд девочек отправился в поход. После того, как они вернулись, их родителям стало известно, что хотя бы одна из них искупалась в походе без разрешения, и каждый решил высечь свою дочь, если узнает о том, что она купалась. Каждое утро девочки ходят в школу и обмениваются слухами о том, кто искупался в походе и кого высекли родители, которые сообщают вечером родителям (исключая информацию о том, купались ли они сами). Через 13 дней несколько отцов, получив очередную порцию информацию, догадались о провинности их дочерей и высекли их. Сколько детей получило в этот вечер наказание?
   
4. 
   Можно ли отметить на плоскости несколько точек так, чтобы на расстоянии 1 от каждой отмеченной точки находилось ровно 10 отмеченных?
   

Графы – 3: Ребра и компоненты, циклы, деревья

Дирихле степеней

Зад1. Докажите, что по итогам однокругового турнира всегда найдутся две команды, сыгравшие одинаковое число игр вничью.

Зад2. Во дворе живут 4 песика: Бобик, Робик, Тобик и Толстолобик. Каждому из них случалось драться с кем-нибудь из остальных, причем у Бобика, Робика и Тобика число тех, с кем они дрались – разное. Со сколькими собаками двора дрался Толстолобик?

Зад3. Докажите, что у каждого многогранника найдутся две грани с одинаковым числом сторон.

Зад4. Степень каждой вершины связного графа – не менее 100. Одно ребро выкинули. Может ли получиться несвязный граф?

Определение. Ребро, при выкидывании которого граф перестает быть связным, называется мостом. Циклом называется замкнутый путь по ребрам графа без повторяющихся ребер.

Упр5. Докажите, что мост не входит ни в какой цикл.

Зад6. В Огогондии 2000 городов. Президент издал указ связать их железными дорогами в единую сеть. Каждая ветка связывает два города, не пересекаясь с другими ветками. Докажите, что всего понадобится не менее 1999 веток.

Определение. Деревом называется связный граф без циклов.

Теорема 7 (свойства деревьев). а) В дереве порядка n ровно n-1 ребро. б) Если в связном графе n-1 ребро, то это – дерево. в) Каждое ребро дерева – мост.

Зад8. Из спичек сложили квадрат, разбитый линиями из спичек на 64 квадратных поля со стороной в одну спичку. Какое наименьшее число спичек надо убрать, чтобы с любого поля на любое другое можно было пройти, не перепрыгивая через спички?

Теорема 9 (о числе ребер связного графа). В графе порядка n с k компонентами связности – не менее n-k ребер.

Зад10. Можно ли раскрасить ребра куба в два цвета так, чтобы по ребрам каждого цвета можно было пройти из любой вершины в любую?

Зад11. В связном графе между любыми двумя вершинами есть маршрут из не более чем трех ребер, а степень каждой вершины не более, чем 4. Докажите, что в графе не более 53-х вершин.

Зад12. Сеть дорог в графстве Вишкиль устроена так, что из любого города можно добраться в любой другой ровно одним способом. а) Докажите, что есть город, из которого выходит ровно одна дорога; б) Докажите, что таких города по крайней мере два.

Зад13. В соседнем графстве Омутнинске тоже можно добраться из любого города в любой, но, возможно, более чем одним способом. Докажите, что начальник ГАИ графства может (в целях экономии) закрыть несколько дорог так, чтобы любые два города оказались соединены единственным маршрутом.

Упр14. Докажите, что если в графе порядка n есть не менее n ребер, то в нем есть цикл.

жүктеу/скачать 471 Kb.

Достарыңызбен бөлісу: