Олимпиадные задачи по теме «Комбинаторика» для 9 класса - сложность 4-5 с решениями
Натуральные числа от 1 до 100 расставлены по кругу в таком порядке, что каждое число либо больше обоих соседей, либо меньше обоих соседей. Пара соседних чисел называется <i>хорошей</i>, если при выкидывании этой пары вышеописанное свойство сохраняется. Какое минимальное количество хороших пар может быть?
В кабинете президента стоят 2004 телефона, любые два из которых соединены проводом одного из четырёх цветов. Известно, что провода всех четырёх цветов присутствуют. Всегда ли можно выбрать несколько телефонов так, чтобы среди соединяющих их проводов встречались провода ровно трех цветов?
В стране 1001 город, каждые два города соединены дорогой с односторонним движением. Из каждого города выходит ровно 500 дорог, в каждый город входит ровно 500 дорог. От страны отделилась независимая республика, в которую вошли 668 городов. Докажите, что из каждого города этой республики можно доехать до любого другого ее города, не выезжая за пределы республики.
В стране несколько городов, некоторые пары городов соединены двусторонними беспосадочными авиалиниями, принадлежащими <i> k </i> авиакомпаниям. Известно, что каждые две линии одной авиакомпании имеют общий конец. Докажите, что все города можно разбить на <i>k</i> + 2 группы так, что никакие два города из одной группы не соединены авиалинией.
Дано дерево с <i>n</i> вершинами, <i>n</i> ≥ 2. В его вершинах расставлены числа <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, <i>x<sub>n</sub></i>, а на каждом ребре записано произведение чисел, стоящих в концах этого ребра. Обозначим через <i>S</i> сумму чисел на всех рёбрах. Докажите, что <img align="absmiddle" src="/storage/problem-media/109782/problem_109782_img_2.gif">
В стране 100 городов, некоторые пары городов соединены дорогами. Для каждых четырёх городов существуют хотя бы две дороги между ними. Известно, что не существует маршрута, проходящего по каждому городу ровно один раз. Докажите, что можно выбрать два города таким образом, чтобы каждый из оставшихся городов был соединен дорогой хотя бы с одним из двух выбранных городов.
Гидры состоят из голов и шей (каждая шея соединяет ровно две головы). Одним ударом меча можно снести все шеи, выходящие из какой-то головы <i>A</i> гидры. Но при этом из головы <i>A</i> мгновенно вырастает по одной шее во все головы, с которыми <i>A</i> не была соединена. Геракл побеждает гидру, если ему удастся разрубить её на две несвязанные шеями части. Найдите наименьшее <i>N</i>, при котором Геракл сможет победить любую стошеюю гидру, нанеся не более чем <i>N</i> ударов.
В некотором государстве было 2002 города, соединённых дорогами так, что если запретить проезд через любой из городов, то из каждого из оставшихся городов можно добраться до любого другого. Каждый год король выбирает некоторый несамопересекающийся циклический маршрут и приказывает построить новый город, соединить его дорогами со всеми городами выбранного маршрута, а все дороги этого маршрута закрыть за ненадобностью. Через несколько лет в стране не осталось ни одного несамопересекающегося циклического маршрута, проходящего по ее городам. Докажите, что в этот момент количество городов, из которых выходит ровно одна дорога, не меньше 2002.
В городе несколько площадей. Некоторые пары площадей соединены улицами с односторонним движением так, что с каждой площади можно выехать ровно по двум улицам. Докажите, что город можно разделить на 1014 районов так, чтобы улицами соединялись только площади из разных районов, и для каждых двух районов все соединяющие их улицы были направлены одинаково (либо все из первого района во второй, либо наоборот).
В стране несколько городов, некоторые пары городов соединены дорогами, причём между каждыми двумя городами существует единственный несамопересекающийся путь по дорогам. Известно, что в стране ровно 100 городов, из которых выходит по одной дороге. Докажите, что можно построить 50 новых дорог так, что после этого даже при закрытии любой дороги можно будет из каждого города попасть в любой другой.
В стране 2001 город, некоторые пары городов соединены дорогами, причём из каждого города выходит хотя бы одна дорога и нет города, соединённого дорогами со всеми остальными. Назовём множество городов <i>D доминирующим</i>, если каждый не входящий в <i>D</i> город соединён дорогой с одним из городов множества <i>D</i>. Известно, что в каждом доминирующем множестве хотя бы <i>k</i> городов. Докажите, что страну можно разбить на 2001 – <i>k</i> республик так, что никакие два города из одной республики не будут соединены дорогой.
Клетки таблицы 100×100 окрашены в 4 цвета так, что в каждой строке и в каждом столбце ровно по 25 клеток каждого цвета.
Докажите, что найдутся две строки и два столбца, все четыре клетки на пересечении которых окрашены в разные цвета.
В некоторой группе из 12 человек среди каждых девяти найдутся пять попарно знакомых. Докажите, что в этой группе найдутся шесть попарно знакомых.
В стране <i>N</i> 1998 городов, и из каждого осуществляются беспосадочные перелеты в три других города (все авиарейсы двусторонние). Известно, что из каждого города, сделав несколько пересадок, можно долететь до любого другого. Министерство Безопасности хочет объявить закрытыми 200 городов, никакие два из которых не соединены авиалинией. Докажите, что это можно сделать так, чтобы можно было долететь из каждого незакрытого города в любой другой, не делая пересадок в закрытых городах.
В прямоугольную коробку с основанием <i>m</i>×<i>n</i>, где <i>m</i> и <i>n</i> – нечётные числа, уложены домино размера 2×1 так, что остался не покрыт только квадрат 1×1 (дырка) в углу коробки. Если доминошка прилегает к дырке короткой стороной, её разрешается сдвинуть вдоль себя на одну клетку, закрыв дырку (при этом открывается новая дырка). Докажите, что с помощью таких передвижений можно перегнать дырку в любой другой угол.
В Думе 1600 депутатов, которые образовали 16000 комитетов по 80 человек в каждом.
Докажите, что найдутся два комитета, имеющие не менее четырёх общих членов.
Внутри круга расположены точки <i>A</i><sub>1</sub>, <i>A</i><sub>2</sub>, ..., <i>A<sub>n</sub></i>, а на его границе – точки <i>B</i><sub>1</sub>, <i>B</i><sub>2</sub>, ..., <i>B<sub>n</sub></i> так, что отрезки <i>A</i><sub>1</sub><i>B</i><sub>1</sub>, <i>A</i><sub>2</sub><i>B</i><sub>2</sub>, ..., <i>A<sub>n</sub>B<sub>n</sub></i> не пересекаются. Кузнечик может перепрыгнуть из точки <i>A<sub>i</sub></i> в точку <i>A<sub>j</sub></i>, если отрезок <i>A<sub>...
В семейном альбоме есть десять фотографий. На каждой из них изображены три человека: в центре стоит мужчина, слева от мужчины – его сын, а справа – его брат. Какое наименьшее количество различных людей может быть изображено на этих фотографиях, если известно, что все десять мужчин, стоящих в центре, различны?
Скажем, что колода из 52 карт сложена правильно, если каждая пара лежащих рядом карт совпадает по масти или достоинству, то же верно для верхней и нижней карты, и наверху лежит туз пик. Докажите, что число способов сложить колоду правильно
а) делится на 12!;
б) делится на 13!.
Натуральные числа от 1 до <i>n</i> расставляются в ряд в произвольном порядке. Расстановка называется <i>плохой</i>, если в ней можно отметить 10 чисел (не обязательно стоящих подряд), идущих в порядке убывания. Остальные расстановки называются <i>хорошими</i>. Докажите, что количество хороших расстановок не превосходит 81<sup><i>n</i></sup>.
Все имеющиеся на складе конфеты разных сортов разложены по <i>n</i> коробкам, на которые установлены цены в 1, 2, ..., <i>n</i> у. е. соответственно. Требуется купить такие <i>k</i> из этих коробок наименьшей суммарной стоимости, которые содержат заведомо не менее <i><sup>k</sup>/<sub>n</sub></i> массы всех конфет. Известно, что масса конфет в каждой коробке не превосходит массы конфет в любой более дорогой коробке.
а) Какие коробки следует купить при <i>n</i> = 10 и <i>k</i> = 3 ?
б) Тот же вопрос для произвольных натуральных <i>n ≥ k</i>.
По кругу расставлено несколько коробочек. В каждой из них может лежать один или несколько шариков (или она может быть пустой). За один ход разрешается взять все шарики из любой коробочки и разложить их, двигаясь по часовой стрелке, начиная со следующей коробочки, кладя в каждую коробочку по одному шарику.
а) Докажите, что если на каждом следующем ходе шарики берут из той коробочки, в которую попал последний шарик на предыдущем ходе, то в какой-то момент повторится начальное размещение шариков.
б) Докажите, что за несколько ходов из любого начального размещения шариков по коробочкам можно получить любое другое.
Система укреплений состоит из блиндажей. Некоторые из блиндажей соединены траншеями, причём из каждого блиндажа можно перебежать в какой-нибудь другой. В одном из блиндажей спрятался пехотинец. Пушка может одним выстрелом накрыть любой блиндаж. В каждом промежутке между выстрелами пехотинец обязательно перебегает по одной из траншей в соседний блиндаж (даже если по соседнему блиндажу только что стреляла пушка, пехотинец может туда перебежать). Назовём систему <i>надёжной</i>, если у пушки нет гарантированной стратегии поражения пехотинца (то есть такой последовательности выстрелов, благодаря которой пушка поразит пехотинца независимо от его начального местонахождения и последующих передвижений). <div align="center"><img src="/storage/problem-media/1050...
Решите в натуральных числах уравнение (1 + <i>n<sup>k</sup></i>)<sup><i>l</i></sup> = 1 + <i>n<sup>m</sup></i>, где <i>l</i> > 1.
Для чисел 1, ..., 1999, расставленных по окружности, вычисляется сумма произведений всех наборов из 10 чисел, идущих подряд.
Найдите расстановку чисел, при которой полученная сумма наибольшая.