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

В футбольном чемпионате участвуют 18 команд. На сегодняшний день проведено 8 туров (в каждом туре все команды разбиваются на пары и в каждой паре команды играют друг с другом, причём пары не повторяются). Верно ли, что найдутся три команды, которые не сыграли ни одного матча между собой?

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

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

Изначально на доске были написаны одночленs  1, <i>x, x</i>², ..., <i>xⁿ</i>.  Договорившись заранее, <i>k</i> мальчиков каждую минуту одновременно вычисляли каждый сумму каких-то двух многочленов, написанных на доске, и результат дописывали на доску. Через <i>m</i> минут на доске были написаны, среди прочих, многочлены  <i>S</i>₁ = 1 + <i>x,  S</i>₂ = 1 + <i>x + x</i>²,  <i>S</i>₃ = 1 + <i>x + x</i>² + <i>x</i>³,  ...,  <i>S_n</i> = 1 + <i>x + x</i>² + ... + <i>xⁿ</i>.  Докажите...

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

Обозначим через  <i>S</i>(<i>n</i>, <i>k</i>)  количество не делящихся на <i>k</i> коэффициентов разложения многочлена  (<i>x</i> + 1)<i>ⁿ</i>  по степеням <i>x</i>.

  а) Найдите  <i>S</i>(2012, 3).

  б) Докажите, что  <i>S</i>(2012²⁰¹¹, 2011)  делится на 2012.

На собрание пришло <i>n</i> человек  (<i>n</i> > 1).  Оказалось, что у каждых двух из них среди собравшихся есть ровно двое общих знакомых.

  а) Докажите, что каждый из них знаком с одинаковым числом людей на этом собрании.

  б) Покажите, что <i>n</i> может быть больше 4.

Даны положительные числа <i>b</i> и <i>c</i>. Докажите неравенство  (<i>b</i> – <i>c</i>)²⁰¹¹(<i>b</i> + <i>c</i>)²⁰¹¹(<i>c</i> – <i>b</i>)²⁰¹¹ ≥ (<i>b</i>²⁰¹¹ – <i>c</i>²⁰¹¹)(<i>b</i>²⁰¹¹ + <i>c</i>²⁰¹¹)(<i>c</i>²⁰¹¹ – <i>b</i>²⁰¹¹).

2011 складов соединены дорогами так, что от каждого склада можно проехать к любому другому, возможно, проехав по нескольким дорогам. На складах находится по  <i>x</i>₁, ..., <i>x</i>₂₀₁₁  кг цемента соответственно. За один рейс можно провезти с произвольного склада на другой по соединяющей их дороге произвольное количество цемента. В итоге на складах по плану должно оказаться по  <i>y</i>₁, ..., <i>y</i>₂₀₁₁  кг цемента соответственно, причём

<i>x</i>₁ + <i>x</i>₂ + ... + <i>x</i>₂₀₁₁ = <i>y</i>₁ + <i>y<...

В стране 100 городов и несколько дорог. Каждая дорога соединяет два каких-то города, дороги не пересекаются. Из каждого города можно добраться до любого другого, двигаясь по дорогам. Докажите, что можно объявить несколько дорог главными так, чтобы из каждого города выходило нечётное число главных дорог.

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

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

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

Продавец хочет разрезать кусок сыра на части, которые можно будет разложить на две кучки равного веса. Он умеет разрезать любой кусок сыра в одном и том же отношении  <i>a</i> : (1 – <i>a</i>)  по весу, где  0 < <i>a</i> < 1.  Верно ли, что на любом промежутке длины 0,001 из интервала  (0, 1)  найдётся значение <i>a</i>, при котором он сможет добиться желаемого результата с помощью конечного числа разрезов?

В некой стране 100 городов (города считайте точками на плоскости). В справочнике для каждой пары городов имеется запись, каково расстояние между ними (всего 4950 записей).   а) Одна запись стёрлась. Всегда ли можно однозначно восстановить её по остальным?   б) Пусть стёрлись <i>k</i> записей, и известно, что в этой стране никакие три города не лежат на одной прямой. При каком наибольшем <i>k</i> всегда можно однозначно восстановить стёршиеся записи?

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

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

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

Игра в "супершахматы" ведётся на доске размером 100×100, и в ней участвует 20 различных фигур, каждая из которых ходит по своим правилам. Известно, что любая фигура с любого места бьет не более 20 полей (но больше о правилах ничего не сказано, например, если фигуру <i>А</i> передвинуть, то о том, как изменится множество битых полей мы ничего не знаем). Докажите, что можно расставить на доске все 20 фигур так, чтобы ни одна из них не била другую.

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

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

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

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

В некоторых клетках квадрата 20×20 стоит стрелочка в одном из четырёх направлений. На границе квадрата все стрелочки смотрят вдоль границы по часовой стрелке (см. рис.). Кроме того, стрелочки в соседних (возможно, по диагонали) клетках не смотрят в противоположных направлениях. Докажите, что найдётся клетка, в которой стрелочки нет. <div align="center"><img src="/storage/problem-media/115497/problem_115497_img_2.gif"> </div>

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

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

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

<img align="right" src="/storage/problem-media/115364/problem_115364_img_2.gif"> Назовём лестницей высоты <i>n</i> фигуру, состоящую из всех клеток квадрата <i>n</i>×<i>n</i>, лежащих не выше диагонали (на рисунке показана лестница высоты 4). Сколькими различными способами можно разбить лестницу высоты <i>n</i> на несколько прямоугольников, стороны которых идут по линиям сетки, а площади попарно различны?

Для каждого простого <i>p</i> найдите наибольшую натуральную степень числа <i>p</i>!, на которую делится число (<i>p</i>²)!.

Докажите, что при любых натуральных  0 <<i>k</i><<i>m < n</i>  числа  <img align="absmiddle" src="/storage/problem-media/111922/problem_111922_img_2.gif">  и  <img align="absmiddle" src="/storage/problem-media/111922/problem_111922_img_3.gif">  не взаимно просты.