Тема КОМБИНАТОРИКА

Количество способов, исходов, слагаемых → .01 Правила сложения и умножения

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела комбинаторика

Разделы подтемы Количество способов, исходов, слагаемых

Правила сложения и умножения

Счастливые билеты

Зачем делить в комбинаторике

Раскрываем скобки комбинаторными рассуждениями

Перебор случаев

Числа сочетаний (цэ изэн пока)

Метод шаров и перегородок

Рекурренты в комбинаторике и числа Фибоначчи f(n)

Числа Каталана

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 61#31507Максимум баллов за задание: 7

В числе $2∗0∗1 ∗6∗0∗2∗$ нужно заменить каждую из $6$ звёздочек на любую из цифр $0$ , $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ , $8$ (цифры могут повторяться) так, чтобы полученное $12$ -значное число делилось на $45$ . Сколькими способами это можно сделать?

Подсказки к задаче

Подсказка 1

Если число делится на 45, то оно делится на 9 и на 5. Что нужно для делимости на 5? А на 9?

Подсказка 2

Для делимости на 5 нужно, чтобы число оканчивалось на 0 или 5. Если нам по сути даны все остатки от деления на 9, то можем ли мы за одну цифру контролировать делимость на 9?

Подсказка 3

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

Показать ответ и решение

Заметим, что нам даны все остатки по модулю $9$ , поэтому достаточно поставить $0$ или $5$ на последнюю позицию — $2$ способа, а затем поставить любые цифры вместо ещё $4$ звёздочек (например, первых) — $4 9$ способов. Останется одна звёздочка, для которой найдётся ровно один остаток такой, что число будет кратно $9$ (обратный по сложению к остатку полученного числа без учёта этой звёздочки). В итоге число делится на $45$ , потому как делится на $5$ и $9$ , и каждое такое мы посчитали ровно один раз, откуда ответ $4 2⋅9$ .

Ответ:

$13122$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 62#91239Максимум баллов за задание: 7

В числе $2016∗∗∗ ∗02∗∗$ нужно заменить каждую из 6 звёздочек на любую из цифр $0$ , $2$ , $4$ , $5$ , $7$ , $9$ (цифры могут повторяться) так, чтобы полученное 12-значное число делилось на 15. Сколькими способами это можно сделать?

Источники: Физтех - 2016, 9.3 (см. olymp-online.mipt.ru)

Подсказки к задаче

Подсказка 1

Когда число делится на 15?

Подсказка 2

Когда делиться на 3 и на 5. С тройкой, кажется, будет разобраться сложнее, ведь надо смотреть на всю сумму цифр, о которой мы пока особо ничего не знаем. Начнём с деления на 5. На какие цифры числа нужно посмотреть?

Подсказка 3

Очевидно, на последнюю. То есть в конце либо 0 либо 5. Осталось обеспечить сумму цифр числа кратную 3. Докажите, что если расставить все цифры кроме одной, то вот эта последняя всегда может как и обеспечить деление на 3, так и разрушить.

Подсказка 4

Используйте, тот факт, что среди чисел 0, 2, 4, 5, 7, 9 есть числа сравнимые и с 0, и с 1, и с 2 по модулю 3. Останется посчитать. Уверены, вы справитесь. Успехов!

Показать ответ и решение

Восстанавливаем цифры, начиная с последней. Так как число должно делиться на $5,$ оно должно оканчиваться на $0$ или $5$ — всего $2$ варианта. Делимость на $3$ зависит от суммы цифр — значит, мы можем ставить любые цифры на место звёздочек, кроме последней (считая с конца) звёздочки. Значит, для $2$ – $5$ пропусков у нас есть по $6$ вариантов, на $6$ месте — $2$ варианта. Теперь посчитаем, сколькими способами мы можем восстановить первую звёздочку. Если на данный момент сумма цифра имеет остаток $1,$ то на месте пропуска мы можем поставить $2$ или $5.$ Если же сумма цифр даёт остаток $2$ — $4$ или $7,$ если $0$ — $0$ или $9.$ Значит, на месте первой звёздочки у нас всегда будет ровно $2$ варианта восстановить цифру. Итого получаем $4 2⋅6 ⋅2 =5184$ способа расставить цифры.

Ответ:

5184

Ошибка.
Попробуйте повторить позже

Задача 63#31510Максимум баллов за задание: 7

Найдите количество прямоугольников со сторонами, параллельными осям координат, таких, что точка $(14;22)$ содержится внутри (но не на границе) каждого из них, абсциссы вершин являются натуральными числами меньше $29$ , а ординаты — натуральны и меньше, чем $31$ .

Источники: Физтех-2013, 11 (см. fizteh2013.ru)

Подсказки к задаче

Подсказка 1

Прямоугольник задаётся четырьмя прямыми. Каким условиям должны удовлетворять эти прямые, чтобы точка (14, 22) была внутри? А чтобы при этом выполнялись ограничения на абциссу и ординату?

Подсказка 2

0 < a < 14 < b < 29, 0 < c < 22 < d < 31, где a,b — абсциссы вертикальных границ фигуры, c, d — ординаты горизонтальных границ прямоугольника! Сколько вариантов у нас есть для a? А для b?

Показать ответ и решение

Прямоугольник можно задать 4 прямыми вида $x= a$ , $x= b$ , $y = c$ , $y = d$ . Пусть не умаляя общности $a< b$ и $c< d$ . По условию $0 <a <14< b< 29$ и $0<c <22< d< 31$ . Отсюда для $a$ у нас 13 вариантов, для $b$ у нас $28 − 14= 14$ вариантов, для $c$ у нас 21 вариант и для $d$ у нас $30− 22= 8$ вариантов.

Получаем ответ $13⋅14 ⋅21⋅8 =30576$ .

Ответ:

$30576$

Ошибка.
Попробуйте повторить позже

Задача 64#31505Максимум баллов за задание: 7

Какое количество натуральных чисел $a$ обладает следующим свойством: “Наименьшее общее кратное чисел $16$ , $50$ и $a$ равняется $1200$ ”?

Источники: Физтех-2012, 11.8 (см. olymp.mipt.ru)

Подсказки к задаче

Подсказка 1

Разложите числа на простые множители и вспомните, как представляется НОК через эти множители.

Подсказка 2

Верно, он содержит в себе все самые большие степени вхождения простых множителей. Какие множители ОБЯЗАНО иметь число а, а какие МОЖЕТ? Когда это узнаем, то поймем, что для любого простого р1 мы можем взять все степени простого р2, правило умножения :)

Показать ответ и решение

2 4 4 2 1200= 5 ⋅2 ⋅3,16= 2,50= 2⋅5

Если $НОК (24,2⋅52,a)= 52 ⋅24⋅3$ , то в числе $a$ может быть любая степень двойки от $0$ до $4$ , любая степень пятёрки от $0$ до $2$ , обязательно первая степень тройки для того, чтобы она появилась в $НО К$ и больше никаких простых чисел, так как их нет в числе $1200.$

Всего получается $5⋅3⋅1= 15$ вариантов составления числа из множителей.

Ответ:

$15$

Ошибка.
Попробуйте повторить позже

Задача 65#120491Максимум баллов за задание: 7

Сколькими способами можно расположить на полке 10 томов энциклопедии?

A: $10! 2$

Б: $10!$

В: $1 A10$

Г: $10 C 10$

Показать ответ и решение

Решение скрыто

Ответ: Б

Ошибка.
Попробуйте повторить позже

Задача 66#120509Максимум баллов за задание: 7

Есть 3 билета в различные театры. Сколькими способами они могут быть распределены среди 25 студентов группы, если каждый студент может получить только один билет?

A: $3 C25$

Б: $25! 3!$

B: $3 A25$

Г: $3 25$

Показать ответ и решение

Решение скрыто

Ответ: В

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 67#120510Максимум баллов за задание: 7

Есть 3 билета на танцпол на один концерт (билеты неразличимы). Сколькими способами они могут быть распределены среди 25 студентов, если каждый студент может получить только один билет?

A: $25! 3!$

Б: $3 A25$

B: $3 C25$

Г: $25! 22!$

Показать ответ и решение

Решение скрыто

Ответ: В

Ошибка.
Попробуйте повторить позже

Задача 68#120511Максимум баллов за задание: 7

Сколько есть вариантов составить расписание дежурств на неделю среди 25 студентов, если каждый день должен дежурить ровно один студент и один и тот же студент может дежурить несколько раз?

A: $25 7$