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

В команде сторожей у каждого есть разряд (натуральное число). Сторож <i>N</i>-го разряда <i>N</i> суток дежурит, потом <i>N</i> суток спит, снова <i>N</i> суток дежурит, <i>N</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<...

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

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

2<i>n</i> радиусов разделили круг на 2<i>n</i> равных секторов: <i>n</i> синих и <i>n</i> красных, чередующихся в произвольном порядке. В синие сектора, начиная с некоторого, записывают против хода часовой стрелки числа от 1 до <i>n</i>. В красные сектора, начиная с некоторого, записывают те же числа, но по ходу часовой стрелки. Докажите, что найдётся полукруг, в котором записаны все числа от 1 до <i>n</i>.

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

По кругу стоит 99 тарелок, на них лежат булочки (на тарелке может быть любое число булочек или вовсе их не быть). Известно, что на любых 20 подряд идущих тарелках лежит суммарно хотя бы $k$ булочек. При этом ни одну булочку ни с одной тарелки нельзя убрать так, чтобы это условие не нарушилось. Какое наибольшее суммарное число булочек может лежать на тарелках?

Пусть $A$ — набор из $n>1$ различных натуральных чисел. Для каждой пары чисел $a,b\in A$, где $a < b$, подсчитаем, сколько чисел в $A$ являются делителями числа $b-a$. Какое наибольшее значение может принимать сумма полученных $\frac{n(n-1)}2$ чисел?

В стране, валюта которой — тугрики, ходят только купюры двух целочисленных достоинств. И покупатель, и продавец имеют достаточно много и тех, и других купюр, но при каждом платеже могут использовать вместе не более $k$ купюр (включая сдачу). Известно, что так можно сделать платёж на любую целую сумму от 1 до $n$ тугриков. Каково наибольшее возможное $n$ (в зависимости от $k$)?

В классе $N$ школьников, среди них образовалось несколько компаний.<i>Общительностью</i>школьника назовём количество людей в наибольшей компании, куда он входит (если ни в одну не входит, то общительность равна $1$). Оказалось, что у всех девочек в классе общительность разная. Каково наибольшее возможное количество девочек в классе?

Фокусник вместе со своим помощником собираются показать следующий фокус. Помощник надевает фокуснику повязку на глаза, приглашает на сцену случайного зрителя из зала и просит его написать последовательность из нулей и единиц длины $2^{2025}$. Затем помощник верно называет фокуснику номер и значение некоторого одного члена последовательности. Задача фокусника – отгадать $2025$ других членов последовательности (то есть назвать их номера и значения). Докажите, что они могут заранее договориться так, чтобы фокус удался.

Даны выпуклый многоугольник $M$ и простое число $p$. Оказалось, что существует ровно $p$ способов разбить $M$ на равносторонние треугольники со стороной 1 и квадраты со стороной 1.

Докажите, что длина одной из сторон многоугольника $M$ равна  $p$ – 1.

Петя расставляет 500 королей на клетках доски 100×50 так, чтобы они не били друг друга. А Вася – 500 королей на белых клетках (в шахматной раскраске) доски 100×100 так, чтобы они не били друг друга. У кого больше способов это сделать?

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

К Ивану на день рождения пришли $3 n$ гостей. У Ивана есть $3 n$ цилиндров с написанными сверху буквами А, Б и В, по $n$ штук каждого типа. Иван хочет устроить бал: надеть на гостей цилиндры и выстроить их в хороводы (один или больше) так, чтобы длина каждого хоровода делилась на $3$, а при взгляде на любой хоровод сверху читалось бы по часовой стрелке АБВАБВ...АБВ. Докажите, что Иван может устроить бал ровно $(3n)!$ различными способами. (Цилиндры с одинаковыми буквами неразличимы; все гости различны.)

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

На плоскости отметили все вершины правильного <i>n</i>-угольника, а также его центр. Затем нарисовали контур этого <i>n</i>-угольника, и центр соединили со всеми вершинами; в итоге <i>n</i>-угольник разбился на <i>n</i> треугольников. Вася записал в каждую отмеченную точку по числу (среди чисел могут быть равные). В каждый треугольник разбиения он записал в произвольном порядке три числа, стоящих в его вершинах; после этого он стёр числа в отмеченных точках. При каких <i>n</i> по тройкам чисел, записанным в треугольниках, Петя всегда сможет восстановить число в каждой отмеченной точке?

В классе имеется <i>a</i>₁ учеников, получивших в течение года хотя бы одну двойку, <i>a</i>₂ учеников, получивших не менее двух двоек, ..., <i>a_k</i> учеников, получивших не менее <i>k</i> двоек. Сколько всего двоек в этом классе? (Предполагается, что ни у кого нет более <i>k</i> двоек.)

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

Какое наибольшее число элементов может быть в <i>M</i>?

По окружности выписано 10 чисел, сумма которых равна 100. Известно, что сумма каждых трёх чисел, стоящих рядом, не меньше 29.

Укажите такое наименьшее число <i>А</i>, что в любом таком наборе чисел каждое из чисел не превосходит <i>А</i>.

На доске <i>n</i>×<i>n</i> расставлено  <i>n</i> – 1  фишек так, что никакие две из них не стоят на соседних (по стороне) клетках.

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

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

На доске 100×100 расставлено 100 ладей, не бьющих друг друга.

Докажите, что в правом верхнем и в левом нижнем квадратах размером 50×50 расставлено равное число ладей.

Трое играют в настольный теннис, причем игрок, проигравший партию, уступает место игроку, не участвовавшему в ней. В итоге оказалось, что первый игрок сыграл 10 партий, второй – 21. Сколько партий сыграл третий игрок?