Задачи и решения
Практикум по комбинаторике и дискретной математике: множества и подсчёт вариантов, логика и отношения, рекурсии, арифметика по модулю и графы. Классические вероятностные задачи также сохранены. В разборе отделены условие, решение, проверка и типичная ошибка.
Как заниматься
Сначала попробуйте решить задачу самостоятельно и только потом открывайте решение. Полезно сверять ответ на малых значениях параметров: перебрать все варианты вручную или короткой программой. Начните с задач на правило произведения и сочетания, затем переходите к включениям-исключениям, рекуррентным соотношениям и производящим функциям. В вероятностных задачах сначала опишите пространство равновозможных исходов, а для математических ожиданий ищите разложение в сумму индикаторов.Происхождение материалов
Самостоятельные учебные условия и объяснения редакции отмечены на своих страницах. У материалов на основе открытых сборников приведены точные источники и условия использования. Для классических сопоставлений с задачами МЦНМО сохранены номера близких задач; это не утверждение, что весь практикум взят из одного сборника.
Задачи по темам
В разделе 26 страниц. Раскройте нужную тему; внутри группы названия расположены по алфавиту.
Множества и подсчёт вариантов — 14
- Беспорядки пяти элементов: перестановки без единого неподвижного места
- Включения и исключения: сколько студентов изучают хотя бы один из двух языков
- Двоичные строки: три несоседние единицы в восьми позициях
- Коэффициенты многочлена (1 + x⁴ + x⁹)²⁵: при x¹⁷ — 6900, при x¹⁸ — 300, при x¹⁹ — 0
- Ограниченные разложения: три числа от 0 до 4 с суммой 10
- Перестановки с повторениями: сколько разных строк получается из слова «МАТЕМАТИКА»
- Принцип Дирихле: что гарантируют 25 дат рождения без вероятностной модели
- Разрезание выпуклого девятиугольника на треугольники: 429 способов и числа Каталана
- Сумма произведений цифр всех чисел от 1 до 999 равна 93 195, а для трёхзначных — 45³
- Счастливые билеты: 55 252 номера из миллиона и производящая функция (1 + x + … + x⁹)⁶
- Сюръекции из четырёх элементов в три: включения и исключения и разбиение на прообразы
- Три множества: почему тройное пересечение нужно прибавить обратно
- Чётность перестановки: инверсии и независимость от разложения на обмены
- Шары и перегородки: неотрицательные и положительные решения x+y+z=12