Олимпиадные задачи по теме «Теория графов» для 11 класса - сложность 3 с решениями

На собрание пришло <i>n</i> человек  (<i>n</i> > 1).  Оказалось, что у каждых двух из них среди собравшихся есть ровно двое общих знакомых.

  а) Докажите, что каждый из них знаком с одинаковым числом людей на этом собрании.

  б) Покажите, что <i>n</i> может быть больше 4.

В стране 100 городов и несколько дорог. Каждая дорога соединяет два каких-то города, дороги не пересекаются. Из каждого города можно добраться до любого другого, двигаясь по дорогам. Докажите, что можно объявить несколько дорог главными так, чтобы из каждого города выходило нечётное число главных дорог.

В некой стране 100 городов (города считайте точками на плоскости). В справочнике для каждой пары городов имеется запись, каково расстояние между ними (всего 4950 записей).   а) Одна запись стёрлась. Всегда ли можно однозначно восстановить её по остальным?   б) Пусть стёрлись <i>k</i> записей, и известно, что в этой стране никакие три города не лежат на одной прямой. При каком наибольшем <i>k</i> всегда можно однозначно восстановить стёршиеся записи?

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

Барон Мюнхгаузен рассказывал, что у него есть карта страны Оз с пятью городами. Каждые два города соединены дорогой, не проходящей через другие города. Каждая дорога пересекает на карте не более одной другой дороги (и не более одного раза). Дороги обозначены жёлтым или красным (по цвету кирпича, которым вымощены), и при обходе вокруг каждого города (по периметру) цвета выходящих из него дорог чередуются. Могут ли слова барона быть правдой?

Клетчатая прямоугольная сетка <i>m</i>×<i>n</i> связана из верёвочек единичной длины. Двое делают ходы по очереди. За один ход можно разрезать (посередине) не разрезанную ранее единичную верёвочку. Если не останется ни одного замкнутого верёвочного контура, то игрок, сделавший последний ход, считается проигравшим. Кто из игроков победит при правильной игре и как он должен для этого играть?

Множество клеток на клетчатой плоскости назовем <i>ладейно связным</i>, если из каждой его клетки можно попасть в любую другую, двигаясь по клеткам этого множества ходом ладьи (ладье разрешается перелетать через поля, не принадлежащие нашему множеству). Докажите, что ладейно связное множество из 100 клеток можно разбить на пары клеток, лежащих в одной строке или в одном столбце.

Из 54 одинаковых единичных картонных квадратов сделали незамкнутую цепочку, соединив их шарнирно вершинами. Каждый квадрат (кроме крайних) соединён с соседями двумя противоположными вершинами. Можно ли этой цепочкой квадратов полностью закрыть поверхность куба 3×3×3?

<i>N</i>³ единичных кубиков просверлены по диагонали и плотно нанизаны на нить, после чего нить связана в кольцо (то есть вершина первого кубика соединена с вершиной последнего). При каких <i>N</i> такое ожерелье из кубиков можно упаковать в кубическую коробку с ребром длины <i>N</i>?

В один из дней года оказалось, что каждый житель города сделал не более одного звонка по телефону. Докажите, что население города можно разбить не более чем на три группы так, чтобы жители, входящие в одну группу, не разговаривали в этот день между собой по телефону.

В стране 1993 города, и из каждого выходит не менее 93 дорог. Известно, что из каждого города можно проехать по дорогам в любой другой.

Докажите, что это можно сделать не более, чем с 62 пересадками. (Дорога соединяет между собой два города.)

В стране несколько городов, соединённых дорогами с односторонним и двусторонним движением. Известно, что из каждого города в любой другой можно проехать ровно одним путём, не проходящим два раза через один и тот же город. Докажите, что страну можно разделить на три губернии так, чтобы ни одна дорога не соединяла два города из одной губернии.

Раскраска вершин графа называется <i>правильной</i>, если вершины одного цвета не соединены ребром. Некоторый граф правильно раскрашен в <i>k</i> цветов, причём его нельзя правильно раскрасить в меньшее число цветов. Докажите, что в этом графе существует путь, вдоль которого встречаются вершины всех <i>k</i> цветов ровно по одному разу.

а) Электрическая схема имеет вид решётки 3×3: всего в схеме 16 узлов (вершины квадратиков решётки), которые соединены проводами (стороны квадратиков решётки). Возможно, часть проводов перегорела. За одно измерение можно выбрать любую пару узлов схемы и проверить, проходит ли между ними ток (то есть, проверить, существует ли цепочка неперегоревших проводов, соединяющая эти узлы). В действительности схема такова, что ток проходит от любого узла к любому. За какое наименьшее число измерений всегда можно в этом удостовериться? б) Тот же вопрос для решётки 7×7 (всего 64 узла).

На большой шахматной доске отметили 2<i>n</i> клеток так, что ладья может ходить по всем отмеченным клеткам, не перепрыгивая через неотмеченные.

Докажите, что фигуру из отмеченных клеток можно разрезать на <i>n</i> прямоугольников.

Какое минимальное количество точек на поверхности

   а) додекаэдра,

   б) икосаэдра

надо отметить, чтобы на каждой грани была хотя бы одна отмеченная точка?

На окружности имеется 21 точка.

Докажите, что среди дуг, имеющих концами эти точки, найдётся не меньше ста таких, угловая мера которых не превышает 120°.

В стране больше 101 города. Столица соединена авиалиниями со 100 городами, а каждый город, кроме столицы, соединён авиалиниями ровно с десятью городами (если <i>A</i> соединён с <i>B</i>, то <i>B</i> соединён с <i>A</i>). Известно, что из каждого города можно попасть в любой другой (может быть, с пересадками). Доказать, что можно закрыть половину авиалиний, идущих из столицы, так, что возможность попасть из каждого города в любой другой сохранится.

На клетчатой доске 11×11 отмечено 22 клетки так, что на каждой вертикали и на каждой горизонтали отмечено ровно две клетки. Два расположения отмеченных клеток эквивалентны, если, меняя любое число раз вертикали между собой и горизонтали между собой, мы из одного расположения можем получить другое. Сколько существует неэквивалентных расположений отмеченных клеток?

В шахматном турнире каждый участник сыграл с каждым из остальных одну партию.

Доказать, что участников можно так занумеровать, что окажется, что ни один участник не проиграл непосредственно за ним следующему.

Собралось <i>n</i> человек. Некоторые из них знакомы между собой, причём каждые два незнакомых имеют ровно двух общих знакомых, а каждые два знакомых не имеют общих знакомых. Доказать, что каждый из присутствующих знаком с одинаковым числом человек.

Между зажимами <i>A</i> и <i>B</i> включено несколько сопротивлений. Каждое сопротивление имеет входной и выходной зажимы. Какое наименьшее число сопротивлений необходимо иметь и какова может быть схема их соединения, чтобы при порче любых девяти сопротивлений цепь оставалась соединяющей зажимы <i>A</i> и <i>B</i>, но не было короткого замыкания? (Порча сопротивления: короткое замыкание или обрыв.)

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

(Проволока может проходить по одному ребру дважды, загибаться <nobr>на 90° и 180°, но ломать её нельзя.)</nobr>

Назовём ходы коня, при которых он смещается на две клетки по горизонтали и на одну по вертикали,<i>горизонтальными</i>, а остальные —<i>вертикальными</i>. Требуется поставить коня на одну из клеток доски $46\times46$, после чего чередовать им горизонтальные и вертикальные ходы. Докажите, что если запрещено посещать клетки более одного раза, то будет сделано не более 2024 ходов.

На микросхеме $2025$ различных элементов, некоторые пары из которых соединены проводами. Жора хочет раскидать элементы по $n$ платам так, чтобы никакие два элемента одной платы не были соединены проводами. Жора посчитал, что если плат будет всего две, то у него будет $2$ способа, а если плат $2025$ – то $2025~\cdot~2024^{2024}$ способов. Сколько проводов на микросхеме? <i>Все элементы и все платы разные, какие-то из плат могут не содержать элементов. Способы считаются разными, если хотя бы один элемент в способах находится на разных платах.</i>