Олимпиадные задачи по теме «Комбинаторика» для 1-6 класса - сложность 3 с решениями

Любознательный турист хочет прогуляться по улицам Старого города от вокзала (точка <i>A</i> на плане) до своего отеля (точка <i>B</i>). Турист хочет, чтобы его маршрут был как можно длиннее, но дважды оказываться на одном и том же перекрестке ему неинтересно, и он так не делает. Нарисуйте на плане самый длинный возможный маршрут и докажите, что более длинного нет. <div align="center"><img align="absmiddle" src="/storage/problem-media/111897/problem_111897_img_2.gif"></div>

Кощей Бессмертный похитил у царя трёх дочерей. Отправился Иван-царевич их выручать. Приходит он к Кощею, а тот ему и говорит: "Завтра поутру увидишь пять заколдованных девушек. Три из них – царёвы дочери, а ещё две – мои. Для тебя они будут неотличимы, а сами друг дружку различать смогут. Я подойду к одной из них и стану у неё спрашивать про каждую из пятерых: "Это царевна?". Она может отвечать и правду, и неправду, но ей дозволено назвать царевнами ровно двоих (себя тоже можно называть). Потом я так же опрошу каждую из остальных девушек, и они тоже должны будут назвать царевнами ровно двоих. Если после этого угадаешь, кто из них и вправду царевны, отпущу тебя восвояси невредимым. А если ещё и догадаешься, которая царевна старшая, которая средняя, а которая младшая, то и их...

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

Среди 49 школьников каждый знаком не менее чем с 25 другими.

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

Среди актеров театра Карабаса Барабаса прошёл шахматный турнир. Каждый участник сыграл с каждым из остальных ровно один раз. За победу давали один сольдо, за ничью – полсольдо, за поражение не давалось ничего. Оказалось, что среди каждых трёх участников найдётся шахматист, заработавший в партиях с двумя другими ровно 1,5 сольдо. Какое наибольшее количество актеров могло участвовать в таком турнире?

У Пети есть 12 одинаковых разноцветных вагончиков (некоторые, возможно, одного цвета, но неизвестно, сколько вагончиков какого цвета). Петя считает, что различных 12-вагонных поездов он сможет составить больше, чем 11-вагонных. Не ошибается ли Петя? (Поезда считаются одинаковыми, если в них на одних и тех же местах находятся вагончики одного и того же цвета.)

В шахматном турнире участвовали гроссмейстеры и мастера. По окончании турнира оказалось, что каждый участник набрал ровно половину своих очков в матчах с мастерами. Докажите, что количество участников турнира является квадратом целого числа. (Каждый участник сыграл с каждым по одной партии, победа – 1 очко, ничья – ½ очка, поражение – 0 очков.)

Найдите наибольшее число цветов, в которые можно покрасить рёбра куба (каждое ребро одним цветом) так, чтобы для каждой пары цветов нашлись два соседних ребра, покрашенные в эти цвета. Соседними считаются рёбра, имеющие общую вершину.

12 шахматистов сыграли турнир в один круг. Потом каждый из них написал 12 списков. В первом только он, в (<i>k</i>+1)-м – те, кто были в <i>k</i>-м и те, у кого они выиграли. Оказалось, что у каждого шахматиста 12-й список отличается от 11-го. Сколько было ничьих?

а) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет треугольников?

б) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет полного подграфа из четырёх вершин?

Есть волейбольная сетка 5×10. Какое максимальное число веревок, её составляющих, можно разрезать так, чтобы она не распалась?

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

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

В графе 20 вершин, степень каждой не меньше 10. Доказать, что в нём есть гамильтонов путь.

В стране каждые два города соединены дорогой с односторонним движением. Доказать, что можно проехать по всем городам, побывав в каждом по одному разу (то есть что в полном ориентированном графе есть <i>гамильтонов путь</i>).

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

20 команд сыграли круговой турнир по волейболу.

Докажите, что команды можно занумеровать числами от 1 до 20 так, что 1-я команда выиграла у 2-й, 2-я – у 3-й, ..., 19-я – у 20-й.