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

Можно ли провести в каждом квадратике на поверхности кубика Рубика диагональ так, чтобы получился несамопересекающийся путь?

Можно ли нарисовать на поверхности кубика Рубика такой замкнутый путь, который проходит через каждый квадратик ровно один раз (через вершины квадратиков путь не проходит)?

Тетрадный лист раскрасили в 23 цвета по клеткам. Пара цветов называется хорошей, если существует две соседние клетки, закрашенные этими цветами. Каково минимальное число хороших пар?

20 футбольных команд проводят первенство. В первый день все команды сыграли по одной игре. Во второй также все команды сыграли по одной игре.

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

Посёлок построен в виде квадрата 3 квартала на 3 квартала (кварталы – квадраты со стороной <i>b</i>, всего 9 кварталов). Какой наименьший путь должен пройти асфальтоукладчик, чтобы заасфальтировать все улицы, если он начинает и кончает свой путь в угловой точке <i>A</i>? (Стороны квадрата – тоже улицы).

Несколько фишек двух цветов расположены в ряд (встречаются оба цвета). Известно, что фишки, между которыми 10 или 15 фишек, одинаковы.

Какое наибольшее число фишек может быть?

На кошачьей выставке в ряд сидят 10 котов и 19 кошек, причём рядом с каждой кошкой сидит более толстый кот.

Докажите, что рядом с каждым котом сидит кошка, которая тоньше него.

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

  Школьник сказал своему приятелю Вите Иванову:

  – У нас в классе тридцать пять человек. И представь, каждый из них дружит ровно с одиннадцатью одноклассниками...

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

  Почему он так решил?

Можно ли 77 телефонов соединить между собой проводами так, чтобы каждый был соединён ровно с пятнадцатью?

Во время шахматного турнира, несколько игроков сыграли нечётное количество партий. Докажите, что число таких игроков чётно.

Докажите, что в любом графе

  а) сумма степеней всех вершин равна удвоенному числу рёбер (и следовательно, чётна);

  б) число вершин нечётной степени чётно.

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

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

Каждые две из шести ЭВМ соединены своим проводом. Укажите, как раскрасить каждый из этих проводов в один из пяти цветов так, чтобы из каждой ЭВМ выходило пять проводов разного цвета.

Двадцать городов соединены 172 авиалиниями.

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

Имеются две страны: <i>Обычная</i> и <i>Зазеркалье</i>. У каждого города в <i>Обычной</i> стране есть "двойник" в <i>Зазеркалье</i>, и наоборот. Однако если в <i>Обычной</i> стране какие-то два города соединены железной дорогой, то в <i>Зазеркалье</i> эти города не соединены, а каждые два несоединённых в <i>Обычной</i> стране города обязательно соединены железной дорогой в <i>Зазеркалье</i>. В <i>Обычной</i> стране девочка Алиса не может проехать из города <i>A</i> в город <i>B</i>, сделав менее двух пересадок. Доказать, что Алиса в <i>Зазеркалье</i> сможет проехать из любого города в любой другой, сделав не более двух пересадок.

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

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

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

Система точек, соединённых отрезками, называется "связной", если из каждой точки можно пройти в любую другую по этим отрезкам. Можно ли соединить пять точек в связную систему так, чтобы при стирании любого отрезка образовались ровно две связные системы точек, не связанные друг с другом? (Мы считаем, что в местах пересечения отрезков переход с одного из них на другой невозможен.)

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

Доказать, что общее число отрезков равно  <i>n</i> – 1.

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

Дан отрезок <i>OA</i>. Из конца отрезка <i>A</i> выходит 5 отрезков <i>AB</i>₁, <i>AB</i>₂, <i>AB</i>₃, <i>AB</i>₄, <i>AB</i>₅. Из каждой точки <i>B</i>_i могут выходить ещё пять новых отрезков или ни одного нового отрезка и т.д. Может ли число свободных концов построенных отрезков равняться 1001? Под свободным концом отрезка понимаем точку, принадлежащую только одному отрезку (кроме точки <i>O</i>).

На консультации было 20 школьников и разбиралось 20 задач. Оказалось, что каждый из школьников решил две задачи и каждую задачу решили два школьника. Докажите, что можно так организовать разбор задач, чтобы каждый школьник рассказал одну из решённых им задач и все задачи были разобраны.