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

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

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

Каждая деталь конструктора "Юный паяльщик" – это скобка в виде буквы П, состоящая из трёх единичных отрезков. Можно ли из деталей этого конструктора спаять полный проволочный каркас куба 2×2×2, разбитого на кубики 1×1×1? (Каркас состоит из 27 точек, соединённых единичными отрезками; любые две соседние точки должны быть соединены ровно одним проволочным отрезком.)

Назовём раскраску доски 8×8 в три цвета <i>хорошей</i>, если в любом уголке из пяти клеток присутствуют клетки всех трёх цветов. (Уголок из пяти клеток – это фигура, получающаяся из квадрата 3×3 вырезанием квадрата 2×2.)  Докажите, что количество хороших раскрасок не меньше чем 6⁸.

На вечеринку пришли 100 человек. Затем те, у кого не было знакомых среди пришедших, ушли. Затем те, у кого был ровно один знакомый среди оставшихся, тоже ушли. Затем аналогично поступали те, у кого было ровно 2, 3, 4, ..., 99 знакомых среди оставшихся к моменту их ухода.

Какое наибольшее число людей могло остаться в конце?

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

На встречу выпускников пришло 45 человек. Оказалось, что любые двое из них, имеющие одинаковое число знакомых среди пришедших, не знакомы друг с другом. Какое наибольшее число пар знакомых могло быть среди участвовавших во встрече?

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

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

В стране 2000 городов. Каждый город связан беспосадочными двусторонними авиалиниями с некоторыми другими городами, причём для каждого города число исходящих из него авиалиний есть степень двойки (то есть 1, 2, 4, 8, ...). Для каждого города <i>A</i> статистик подсчитал количество маршрутов, имеющих не более одной пересадки, связывающих <i>A</i> с другими городами, а затем просуммировал полученные результаты по всем 2000 городам. У него получилось 100000. Докажите, что статистик ошибся.

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

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

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

Назовём десятизначное число <i>интересным</i>, если оно делится на 11111 и все его цифры различны. Сколько существует интересных чисел?

а) Имеются 300 яблок, любые два из которых различаются по весу не более чем в 2 раза.

Докажите, что их можно разложить в пакеты по два яблока так, чтобы любые два пакета различались по весу не более чем в 1,5 раза. б) Имеются 300 яблок, любые два из которых различаются по весу не более чем в 3 раза.

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

На столе лежат 365 карточек, на обратной стороне которых написаны различные числа. За один рубль Вася может выбрать три карточки и попросить Петю положить их слева направо так, чтобы числа на карточках располагались в порядке возрастания. Может ли Вася, потратив 2000 рублей, с гарантией выложить все 365 карточек на стол слева направо так, чтобы числа на них располагались в порядке возрастания?

На бесконечном белом листе клетчатой бумаги конечное число клеток окрашено в чёрный цвет так, что у каждой чёрной клетки чётное число (0, 2 или 4) белых клеток, соседних с ней по стороне. Докажите, что каждую белую клетку можно окрасить в красный или зелёный цвет так, чтобы у каждой чёрной клетки стало поровну красных и зелёных клеток, соседних с ней по стороне.

Натуральные числа от 1 до 100 расставлены по кругу в таком порядке, что каждое число либо больше обоих соседей, либо меньше обоих соседей. Пара соседних чисел называется <i>хорошей</i>, если при выкидывании этой пары вышеописанное свойство сохраняется. Какое минимальное количество хороших пар может быть?

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

В стране <i>n</i> городов. Между каждыми двумя из них проложена либо автомобильная, либо железная дорога. Турист хочет объехать страну, побывав в каждом городе ровно один раз, и вернуться в город, с которого он начинал путешествие. Докажите, что турист может выбрать город, с которого он начнет путешествие, и маршрут так, что ему придётся поменять вид транспорта не более одного раза.

Гидры состоят из голов и шей (каждая шея соединяет ровно две головы). Одним ударом меча можно снести все шеи, выходящие из какой-то головы <i>A</i> гидры. Но при этом из головы <i>A</i> мгновенно вырастает по одной шее во все головы, с которыми <i>A</i> не была соединена. Геракл побеждает гидру, если ему удастся разрубить её на две несвязанные шеями части. Найдите наименьшее <i>N</i>, при котором Геракл сможет победить любую стошеюю гидру, нанеся не более чем <i>N</i> ударов.

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

В компании из  2<i>n</i> + 1 человека для любых <i>n</i> человек найдётся отличный от них человек, знакомый с каждым из них.

Докажите, что в этой компании есть человек, знающий всех.

В стране несколько городов, некоторые пары городов соединены дорогами. При этом из каждого города выходит хотя бы три дороги.

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

Имеются пять внешне одинаковых гирь с попарно различными массами. Разрешается выбрать любые три из них <i>A</i>, <i>B</i> и <i>C</i> и спросить, верно ли, что

<i>m</i>(<i>A</i>) < <i>m</i>(<i>B</i>) < <i>m</i>(<i>C</i>)  (через <i>m</i>(<i>x</i>) обозначена масса гири <i>x</i>). При этом даётся ответ "Да" или "Нет". Можно ли за девять вопросов гарантированно узнать, в каком порядке идут веса гирь?