Олимпиадные задачи по теме «Комбинаторика (прочее)» для 6-9 класса

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

Какое наибольшее количество клеток можно отметить на шахматной доске так, чтобы с каждой из них на любую другую отмеченную клетку можно было пройти ровно двумя ходами шахматного коня?

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

У Миши есть 1000 одинаковых кубиков, у каждого из которых одна пара противоположных граней белая, вторая – синяя, третья – красная. Он собрал из них большой куб 10×10×10, прикладывая кубики друг к другу одноцветными гранями. Докажите, что у большого куба есть одноцветная грань.

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

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

Даны пятьдесят различных натуральных чисел, двадцать пять из которых не превосходят 50, а остальные больше 50, но не превосходят 100. При этом никакие два из них не отличаются ровно на 50. Найдите сумму этих чисел.

Какое наибольшее число белых и чёрных фишек можно расставить на шахматной доске так, чтобы на каждой горизонтали и на каждой вертикали белых фишек было ровно в два раза больше, чем чёрных?

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

В ряд стоят 30 сапог: 15 левых и 15 правых. Докажите, что среди некоторых десяти подряд стоящих сапог левых и правых поровну.

<i>k</i> вершин правильного <i>n</i>-угольника закрашены. Закраска называется <i>почти равномерной</i>, если для любого натурального <i>m</i> верно следующее условие: если <i>M</i>₁ – множество <i>m</i> расположенных подряд вершин и <i>M</i>₂ – другое такое множество, то количество закрашенных вершин в <i>M</i>₁ отличается от количества закрашенных вершин в <i>M</i>₂ не больше чем на 1. Доказать, что для любых натуральных <i>n</i> и  <i>k</i> ≤ <i>n</i>  почти равномерная закраска существует и что она единственна с точностью до поворотов закрашенного множест...

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

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

Каждый разговор длится 1 час. За один разговор можно передать сколько угодно новостей.

Какое минимальное количество часов необходимо, чтобы все узнали все новости? Рассмотрите три случая:

  а)  <i>N</i> = 64,

  б)  <i>N</i> = 55,

  в)  <i>N</i> = 100.

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

По кругу стоит 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$ других членов последовательности (то есть назвать их номера и значения). Докажите, что они могут заранее договориться так, чтобы фокус удался.

Около таверны стоят $100$ эльфов, $100$ гномов и $100$ орков. Сначала в неё заходят $10$ эльфов, $10$ гномов и $10$ орков. Затем каждую минуту из неё выходит одно существо и тут же заходит другое, причём всегда после выхода эльфа заходит гном, после выхода гнома – орк, а после выхода орка – эльф. Могло ли оказаться так, что в какой-то момент в таверне побывали все возможные компании из $30$ существ ровно по одному разу? Все $300$ существ различны.

Сто сидений карусели расположены по кругу через равные промежутки. Каждое покрашено в жёлтый, синий или красный цвет. Сиденья одного и того же цвета расположены подряд и пронумерованы 1, 2, 3, ... по часовой стрелке. Синее сиденье № 7 противоположно красному № 3, а жёлтое № 7 — красному № 23. Найдите, сколько на карусели жёлтых сидений, сколько синих и сколько красных.

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

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

Белая фигура «жук» стоит в угловой клетке доски $1000\times n$, где $n$ — нечётное натуральное число, большее $2020$. В двух ближайших к ней углах доски стоят два чёрных шахматных слона. При каждом ходе жук или переходит на клетку, соседнюю по стороне, или ходит как шахматный конь. Жук хочет достичь противоположного угла доски, не проходя через клетки, занятые или атакованные слоном, и побывав на каждой из остальных клеток ровно по одному разу. Покажите, что количество путей, по которым может пройти жук, не зависит от $n$.

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