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

Клетчатая полоска 1×1000000 разбита на 100 сегментов. В каждой клетке записано целое число, причём в клетках, лежащих в одном сегменте, числа совпадают. В каждую клетку поставили по фишке. Затем сделали такую операцию: все фишки одновременно передвинули, каждую – на то количество клеток вправо, которое указано в её клетке (если число отрицательно, то фишка двигается влево); при этом оказалось, что в каждую клетку снова попало по фишке. Эту операцию повторяют много раз. Для каждой фишки первого сегмента подсчитали, через сколько операций она впервые снова окажется в этом сегменте. Докажите, что среди полученных чисел не более 100 различных.

На координатной плоскости нарисовано <i>n</i> парабол, являющихся графиками квадратных трёхчленов; никакие две из них не касаются. Они делят плоскость на несколько областей, одна из которых расположена над всеми параболами. Докажите, что у границы этой области не более  2(<i>n</i> – 1)  углов (то есть точек пересечения пары парабол).

Для прохождения теста тысячу мудрецов выстраивают в колонну. Из колпаков с номерами от 1 до 1001 один прячут, а остальные в случайном порядке надевают на мудрецов. Каждый видит только номера на колпаках всех впереди стоящих. Далее мудрецы по порядку от заднего к переднему называют вслух целые числа. Каждое число должно быть от 1 до 1001, причём нельзя называть то, что уже было сказано. Результат теста – число мудрецов, назвавших номер своего колпака. Мудрецы заранее знали условия теста и могли договориться, как действовать.

  а) Могут ли они гарантировать результат более 500?

  б) Могут ли они гарантировать результат не менее 999?

Команда из <i>n</i> школьников участвует в игре: на каждого из них надевают шапку одного из <i>k</i> заранее известных цветов, а затем по свистку все школьники одновременно выбирают себе по одному шарфу. Команда получает столько очков, у скольких её участников цвет шапки совпал с цветом шарфа (шарфов и шапок любого цвета имеется достаточное количество; во время игры каждый участник не видит своей шапки, зато видит шапки всех остальных, но не имеет права выдавать до свистка никакую информацию). Какое наибольшее число очков команда, заранее наметив план действий каждого её члена, может гарантированно получить:

  а) при  <i>n = k = </i>2;

  б) при произвольных фиксированных <i>n</i> и <i>k</i>?

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

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

В НИИЧАВО работают несколько научных сотрудников. В течение 8-часового рабочего дня сотрудники ходили в буфет, возможно по нескольку раз. Известно, что для каждых двух сотрудников суммарное время, в течение которого в буфете находился ровно один из них, оказалось не менее <i>x</i> часов  (<i>x</i> > 4).  Какое наибольшее количество научных сотрудников могло работать в этот день в НИИЧАВО (в зависимости от <i>x</i>)?

В блицтурнире принимали участие  2<i>n</i> + 3  шахматиста. Каждый сыграл с каждым ровно по одному разу. Для турнира был составлен такой график, чтобы игры проводились одна за другой, и чтобы каждый игрок после сыгранной партии отдыхал не менее <i>n</i> игр. Докажите, что один из шахматистов, игравших в первой партии, играл и в последней.

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

Имеются три комиссии бюрократов. Известно, что для каждой пары бюрократов из разных комиссий среди членов оставшейся комиссии есть ровно 10 бюрократов, которые знакомы с обоими, и ровно 10 бюрократов, которые незнакомы с обоими. Найдите общее число бюрократов в комиссиях.

Расстоянием между числами  <span style="text-decoration: overline;"><i>a</i>₁<i>a</i>₂<i>a</i>₃<i>a</i>₄<i>a</i>₅</span>  и  <span style="text-decoration: overline;"><i>b</i>₁<i>b</i>₂<i>b</i>₃<i>b</i>₄<i>b</i>₅</span>  назовём максимальное <i>i</i>, для которого  <i>a_i</i> ≠ <i>b_i</i>.  Все пятизначные числа выписаны друг...

Сколькими способами числа 2⁰, 2¹, 2&sup2, ..., 2²⁰⁰⁵ можно разбить на два непустых множества <i>A</i> и <i>B</i> так, чтобы уравнение  <i>x</i>&sup2 – <i>S</i>(<i>A</i>)<i>x + S</i>(<i>B</i>) = 0,  где <i>S</i>(<i>M</i>) – сумма чисел множества <i>M</i>, имело целый корень?

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

Клетки таблицы 100×100 окрашены в 4 цвета так, что в каждой строке и в каждом столбце ровно по 25 клеток каждого цвета.

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

В семейном альбоме есть десять фотографий. На каждой из них изображены три человека: в центре стоит мужчина, слева от мужчины – его сын, а справа – его брат. Какое наименьшее количество различных людей может быть изображено на этих фотографиях, если известно, что все десять мужчин, стоящих в центре, различны?

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

  а) делится на 12!;

  б) делится на 13!.

Все имеющиеся на складе конфеты разных сортов разложены по <i>n</i> коробкам, на которые установлены цены в 1, 2, ..., <i>n</i>  у. е. соответственно. Требуется купить такие <i>k</i> из этих коробок наименьшей суммарной стоимости, которые содержат заведомо не менее <i>^k/_n</i> массы всех конфет. Известно, что масса конфет в каждой коробке не превосходит массы конфет в любой более дорогой коробке.

  а) Какие коробки следует купить при  <i>n</i> = 10  и  <i>k</i> = 3 ?

  б) Тот же вопрос для произвольных натуральных  <i>n ≥ k</i>.

Для чисел 1, ..., 1999, расставленных по окружности, вычисляется сумма произведений всех наборов из 10 чисел, идущих подряд.

Найдите расстановку чисел, при которой полученная сумма наибольшая.

Имеется набор гирь, веса которых в граммах: 1, 2, 4,... , 512 (последовательные степени двойки) – по одной гире каждого веса. Груз разрешается взвешивать с помощью этого набора, кладя гири на обе чашки весов.

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

  б) Приведите пример груза, который можно взвесить ровно 89 способами.

  а) Четыре порта 1, 2, 3, 4 расположены (в этом порядке) на окружности круглого острова. Их связывает плоская сеть дорог, на которых могут быть перекрёстки, то есть точки, где пересекаются, сходятся или разветвляются дороги. На всех участках дорог введено одностороннее движение так, что, выехав от любого порта или перекрёстка, нельзя вернуться в него снова. Пусть  <i>f_ij</i>  означает число различных путей, идущих из порта <i>i</i> в порт <i>j</i>. Докажите неравенство   <i>f</i>₁₄<i>f</i>₂₃ ≥ <i>f</i>₁₃<i>f</i>₂₄.

  б) Докажите, что если портов шесть: 1, 2, 3, 4, 5, 6 (по кругу в этом поря...

Игра в "супершахматы" ведётся на доске размером 30×30, и в ней участвуют 20 разных фигур, каждая из которых ходит по своим правилам. Известно, однако, что

  1) любая фигура с любого поля бьёт не более 20 полей и

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

Докажите, что

  а) любая фигура <i>F</i> бьёт данное поле <i>Х</i> не более, чем с 20 полей;

  б) можно расставить на доске все 20 фигур так, чтобы ни одна из них не била другую.

  Для каждого натурального <i>n</i> обозначим через <i>P</i>(<i>n</i>) число разбиений <i>n</i> в сумму натуральных слагаемых (разбиения, отличающиеся лишь порядком слагаемых, считаются одинаковыми; например,  <i>P</i>(4) = 5,  потому что  4 = 4 = 1 + 3 = 2 + 2 = 1 + 1 + 2 = 1 + 1 + 1 + 1  – пять способов).

  а) Количество различных чисел в данном разбиении назовем его <i>разбросом</i> (например, разбиение  4 = 1 + 1 + 2  имеет разброс 2, потому что в этом разбиении два различных числа). Докажите, что сумма <i>Q</i>(<i>n</i>) разбросов всех разбиений числа <i>n</i> равна   1 + <i>P</i>(1) + <i>P</i>(2) + ... + <i>P</i>(<i>n</i>–1)....

По одной стороне бесконечного коридора расположено бесконечное количество комнат, занумерованных числами от минус бесконечности до плюс бесконечности. В комнатах живут 9 пианистов (в одной комнате могут жить несколько пианистов), кроме того, в каждой комнате находится по роялю. Каждый день какие-то два пианиста, живущие в соседних комнатах (<i>k</i>-й и (<i>k</i>+1)-й), приходят к выводу, что они мешают друг другу, и переселяются соответственно в (<i>k</i>–1)-ю и (<i>k</i>+2)-ю комнаты. Докажите, что через конечное число дней эти переселения прекратятся. (Пианисты, живущие в одной комнате, друг другу не мешают.)

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

  а) хотя бы один треугольник;

  б) не менее <i>n</i> треугольников.

За круглым столом сидят <i>n</i> человек. Разрешается любых двух людей, сидящих рядом, поменять местами. Какое наименьшее число таких перестановок необходимо сделать, чтобы в результате каждые два соседа остались бы соседями, но сидели бы в обратном порядке?

Имеется 100-значное число, состоящее из единиц и двоек. Разрешается в любых десяти последовательных цифрах поменять местами первые пять с пятью следующими. Два таких числа называются<i>похожими</i>, если одно из них получается из другого несколькими такими операциями. Какое наибольшее количество попарно непохожих чисел можно выбрать?