Комбинаторика
Теория и подборка олимпиадных задач по комбинаторике.
Полезные материалы
- Подсчет вариантов (Фоксфорд.Учебник)
- Правила суммы и произведения (Фоксфорд.Учебник)
- Число перестановок (Фоксфорд.Учебник)
- Число размещений (Фоксфорд.Учебник)
- Число сочетаний (Фоксфорд.Учебник)
- Треугольник Паскаля (Фоксфорд.Учебник)
- Бином Ньютона (Фоксфорд.Учебник)
Записи онлайн-занятий
Подборка задач
- Сколькими способами можно выбрать одну гласную и одну согласную буквы из слова ФОКСФОРД?
- На почте продаются восемь видов конвертов, 25 различных открыток и 30 видов марок. Сколькими способами можно купить конверт с открыткой и марку?
Из города $A$ в город $B$ ведет одна дорога, в город $C$ --- четыре, в $D$ --- пять, из города $C$ в город $B$ --- три дороги, а из $D$ в $B$ --- шесть. Сколько существует способов доехать из города $A$ в город $B$, если считать, что по дорогам можно ехать лишь в одном направлении --- слева направо?- Монетку бросают десять раз. Сколько различных последовательностей из орлов и решек может при этом получиться?
- Сколько существует семизначных чисел, все цифры которых нечетны?
- Дана квадратная таблица $3\times 3$, каждую клетку которой можно окрасить в один из трех цветов. Сколько различных раскрасок таблицы можно получить?
- Сколькими способами можно прочитать слово ФОКСФОРД, двигаясь вправо или вниз?
Ф О К С Ф О Р Д О К С Ф О Р Д К С Ф О Р Д С Ф О Р Д Ф О Р Д О Р Д Р Д Д 
Квадрат $5\times 5$ разбит на единичные клеточки. Его покрывают 25 черных и 25 белых прямоугольных равнобедренных треугольников, так что каждую клетку закрывают два треугольника. "Шахматным" будем называть такие покрытия, что любые два треугольника, имеющие общую сторону, разного цвета. Сколько существует различных "шахматных" покрытий? (Одно из возможных "шахматных" покрытий изображено на рисрисунке)- В классе 25 человек. Сколькими способами можно выбрать старосту класса и его помощника?
- Сколько существует способов выбрать четыре карты из колоды (36 карт) так, чтобы они все были различных мастей и достоинств?
- В русском алфавите 33 буквы. Сколько различных пятибуквенных "слов" можно составить, если не допускать "слов", где две одинаковые буквы идут подряд? "Слово" не обязательно должно быть осмысленным. Например, абвгд или ьъыйы -- подходящие "слова" являются, а класс, ссора и пресс -- не подходят, так как в них есть две одинаковые подряд идущие буквы.
- Сколько существует различных вариантов раскраски граней кубика в данные шесть цветов, если считать раскраски, отличающиеся лишь поворотом кубика за один и тот же вариант?
- Сколько существует десятизначных чисел с нечетной суммой цифр?
- Сколькими способами можно поставить на шахматную доску черную и белую ладьи так, чтобы они не били друг друга?
- Сколькими способами можно поставить на шахматную доску черного и белого слона так, чтобы они не били друг друга?
- Сколькими способами можно поставить на шахматную доску черного и белого ферзя так, чтобы они не били друг друга?
- Сколькими способами можно поставить на шахматную доску черного и белого короля так, чтобы полученная ситуация не противоречила правилам игры в шахматы (ведь, как известно, королей бить нельзя)?
- Сколькими способами можно поставить на шахматную доску черного и белого коня так, чтобы они не били друг друга?
- На танцплощадке собрались 20 парней и 20 девушек. Сколькими способами они могут разбиться на пары для участия в очередном танце?
- Чему равна сумма всех пятизначных чисел, которые можно получить всевозможными перестановками цифр 1, 2, 3, 4, 5?
- Десять девушек водят хоровод. Сколькими различными способами они могут встать в круг?
- Сколько всего десятизначных чисел, в которых хотя бы две какие-то цифры одинаковы?
- Сколько существует различных возможностей рассадить 10 мальчиков и 10 девочек за круглый стол с двадцатью креслами так, чтобы они чередовались?
- Сколькими способами 20 учеников могут выстроиться в очередь в столовую, если Маша хочет стоять рядом с подругой Катей?
- Сколько различных слов можно получить перестановкой букв в слове "ШКОЛА"?
- Сколько различных слов можно получить перестановкой букв в слове "АЛГЕБРА"?
- Сколько различных слов можно получить перестановкой букв в слове "ПАРАБОЛА"?
- Сколько различных слов можно получить перестановкой букв в слове "МАТЕМАТИКА"?
- Сколько существует шестизначных чисел, у которых каждая последующая цифра меньше предыдущей?
- Сколько существует шестизначных чисел, у которых каждая последующая цифра больше предыдущей?
- Имеется $m$ белых и $n$ черных шаров, причем $m > n$. Сколькими способами можно все шары разложить в ряд так, чтобы никакие два черных шара не лежали рядом?
- Сколькими способами можно выложить в ряд 5 красных, 5 синих и 5 зеленых шаров так, чтобы никакие два синих шара не лежали рядом?
- На полке стоит 12 книг. Сколькими способами можно выбрать из них 5 книг, никакие две из которых не стоят рядом?
- Имеется куб размером $10 \times 10 \times 10$, состоящий из маленьких единичных кубиков. В центре $O$ одного из угловых кубиков сидит кузнечик. Он может прыгать в центр кубика, имеющего общую грань с тем, в котором кузнечик находится в данный момент; причем так, чтобы расстояние до точки $O$ увеличивалось. Сколькими способами кузнечик может допрыгать до кубика, противоположного исходному?
- Имеется 20 человек – 10 юношей и 10 девушек. Сколько существует способов составить компанию, в которой было бы одинаковое (хотя бы по одному) число юношей и девушек?
- На собеседовании десяти человекам был предложен тест, состоящий из нескольких вопросов. Известно, что любые пять человек ответили вместе на все вопросы (т. е. на каждый вопрос хоть один из пяти дал правильный ответ), а любые четыре – нет. При каком минимальном количестве вопросов это могло быть?
- Каких чисел больше среди натуральных чисел от 1 до 1000000 включительно: представимых в виде суммы точного квадрата и точного куба или не представимых в таком виде? (А. Голованов, Финал, 1995-1996, 9 класс, №1)
- На шахматной доске стоят 8 ладей, не бьющих друг друга. Докажите, что среди попарных расстояний между ними найдутся два одинаковых. (Расстояние между ладьями – это расстояние между центрами клеток, в которых они стоят.) (Д. Кузнецов, Финал, 2001-2002, 9 класс, №5)
- Назовем билет с номером от 000000 до 999999 отличным, если разность некоторых двух соседних цифр его номера равна 5. Найдите число отличных билетов. (А. Шаповалов, Региональный этап, 1995-1996, 8 класс, №2)
- Назовем раскраску доски $8\times 8$ в три цвета хорошей, если в любом уголке из пяти клеток присутствуют клетки всех трех цветов. (Уголок из пяти клеток – это фигура, получающаяся из квадрата $3\times3$ вырезанием квадрата $2\times2$.) Докажите, что количество хороших раскрасок не меньше, чем $6^8$. (О. Подлипский, Региональный этап, 2005-2006, 10 класс, №2)
- Правильный треугольник разбит на правильные треугольники со стороной 1 линиями, параллельными его сторонам и делящими каждую сторону на $n$ частей. Какое наибольшее число отрезков длины 1 с концами в вершинах этих треугольников можно отметить так, чтобы не нашлось треугольника, все стороны которого состоят из отмеченных отрезков? (М. Антонов, Финал, 1998-1999, 9 класс, №5)
- На новогодний вечер пришли несколько супружеских пар, у каждой из которых было от 1 до 10 детей. Дед Мороз выбирал одного ребёнка, одну маму и одного папу из трёх разных семей и катал их в санях. Оказалось, что у него было ровно 3630 способов выбрать нужную тройку людей. Сколько всего могло быть детей на этом вечере? (С. Волченков, Региональный этап, 2014-2015, 11 класс, №2)
- В волейбольном турнире с участием 73 команд каждая команда сыграла с каждой по одному разу. В конце турнира все команды разделили на две непустые группы так, что каждая команда первой группы одержала ровно $n$ побед, а каждая команда второй группы – ровно $m$ побед. Могло ли оказаться, что $m \ne n$? (Н. Агаханов, Региональный этап, 2011-2012, 11 класс, №6)
- Расстоянием между числами $\overline{a_1a_2a_3a_4a_5a_6}$ и $\overline{b_1b_2b_3b_4b_5b_6}$ назовем максимальное $i$, для которого $a_i \ne b_i$. Все пятизначные числа выписаны друг за другом в некотором порядке. Какова при этом минимально возможная сумма расстояний между соседними числами? (Р. Карасев, Региональный этап, 2003-2004, 11 класс, №6)
- 100 идущих подряд натуральных чисел отсортировали по возрастанию суммы цифр, а числа с одинаковой суммой цифр – просто по возрастанию. Могли ли числа 2010 и 2011 оказаться рядом? (С. Волченков, Региональный этап, 2010-2011, 8 класс, №3)
- а) Имеются 300 яблок, любые два из которых различаются по весу не более, чем в два раза. Докажите, что их можно разложить в пакеты по два яблока так, чтобы любые два пакета различались по весу не более, чем в полтора раза. (А. Шаповалов, Региональный этап, 1996-1997, 8 класс, №2)
б) Имеются 300 яблок, любые два из которых различаются по весу не более, чем в три раза. Докажите, что их можно разложить в пакеты по четыре яблока так, чтобы любые два пакета различались по весу не более, чем в полтора раза. (А. Шаповалов, Региональный этап, 1996-1997, 9 класс, №3) - На встречу выпускников пришло 45 человек. Оказалось, что любые двое из них, имеющие одинаковое число знакомых среди пришедших, не знакомы друг с другом. Какое наибольшее число пар знакомых могло быть среди участвовавших во встрече? (С. Берлов, Региональный этап, 2002-2003, 10 класс, №3)
- Проведено три семейства параллельных прямых, по 10 прямых в каждом. Какое наибольшее число треугольников они могут вырезать из плоскости? (А. Шаповалов, Региональный этап, 2000-2001, 10 и 11 классы, №4)
