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

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

На некоторых клетках доски 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>.

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

По кругу стоит 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$)?

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

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

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