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

Количество способов, исходов, слагаемых → .06 Числа сочетаний (цэ изэн пока)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1#119820

Пусть $n >3$ — натуральное число. Сколько существует способ выбрать два не пересекающихся прямоугольника внутри квадрата $n× n,$ идущих по линиям сетки? Прямоугольники пересекаются, если у них есть хотя бы одна общая внутренняя клетка или общая точка на границе.

Источники: Турнир Ломоносова - 2025, 11.2(см. turlom.olimpiada.ru)

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

Подсказка 1

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

Подсказка 2

Давайте попробуем задать прямоугольники при помощи двух интервалов: один для горизонтальной стороны, а другой — для вертикальной! Тогда несложно вывести условие того, что прямоугольники не пересекаются.

Подсказка 3

Для начала разберите случай, когда не пересекаются "горизонтальные" интервалы. А сколько тогда способов будет для "вертикальных" интервалов?

Подсказка 4

Если "горизонтальные" интервалы не пересекаются, то вертикальные можно выбрать абсолютно любыми! Аналогично и со случаем, когда не пересекаются "вертикальные" интервалы. Осталось лишь проверить, не посчиталось ли ничего лишнего ;)

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

Прямоугольник можно задать двумя интервалами: один определяет его горизонтальную сторону, а другой — вертикальную. Чтобы прямоугольники не пересекались, необходимо и достаточно, чтобы либо горизонтальные, либо вертикальные интервалы были непересекающимися (возможно, оба).

Сначала посчитаем количество способов, при которых горизонтальные интервалы не пересекаются. Пусть эти интервалы — $[a,b]$ и $[c,d].$ Поскольку порядок прямоугольников не имеет значения, без потери общности можно предположить, что $a< c,$ то есть $a <b< c< d.$ Тогда количество способов выбрать $a,b,c,d$ равно $4 Cn+1.$ На вертикальные интервалы ограничений нет, поэтому количество способов выбрать их равно $2 2 (C n+1) .$ Таким образом, общее количество пар прямоугольников с непересекающимися горизонтальными интервалами равно $4 2 2 Cn+1⋅(C n+1) .$ По симметрии, количество пар прямоугольников с непересекающимися вертикальными интервалами такое же.

Осталось посчитать и вычесть количество способов, при которых и горизонтальные, и вертикальные интервалы не пересекаются. Пусть горизонтальные интервалы — $[a,b]$ и $[c,d],$ а вертикальные — $[e,f]$ и $[g,h].$ Без потери общности можно предположить $a< b< c< d,$ поэтому оличество способов выбрать горизонтальные интервалы равно $C4n+1.$ Однако случаи $e <f <g <h$ и $g <h < e<f$ теперь различны, поэтому количество способов выбрать вертикальные интервалы равно $2⋅C4n+1.$ Следовательно, количество пар прямоугольников, у которых и горизонтальные, и вертикальные интервалы не пересекаются, равно $2 ⋅(C4n+1)2.$

Ответ:

$2⋅C4 ⋅(C2 )2 − 2⋅(C4 )2 n+1 n+1 n+1$

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

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

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

Задача 2#121754

В комплекте для сборки игрушечного поезда есть один локомотив (который всегда расположен спереди), $2n$ одинаковых красных вагонов и $3n$ одинаковых желтых вагонов. Назовем поезд длинным, если в нем есть хотя бы $n$ вагонов (не считая локомотива). Сколько различных длинных поездов можно собрать, используя этот комплект? (Ответ должен быть дан в замкнутом виде: в ответе не должно быть сумм с переменным числом слагаемых, многоточий и т.д.)

Источники: Высшая проба - 2025, 11.4(см. olymp.hse.ru)

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

Подсказка 1

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

Подсказка 2

В общем виде, для длины x, и, допустим, количества красных вагонов y, получаем, что количество поездов будет равно C из x по y (так как вагоны считаются одинаковыми, и нас интересует только расположение цветов). Теперь зафиксируем количество красных вагонов и просуммируем по всевозможным длинам поезда. Получаем какую-то неприятную сумму "цешек", которую, однако, можно упростить, если применить тождество Паскаля. Как нам это помогло?

Подсказка 3

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

Подсказка 4

Теперь остается только посчитать количество поездов, в которых менее n вагонов, чтобы вычесть его из общего количества поездов. Здесь задача проще: каждого цвета по количеству вагонов хватает для того, чтобы заполнить поезд любой длины, так что можно не так утруждаться. Как легко посчитать?

Подсказка 5

Можем просто считать, что для каждой позиции имеем 2 варианта: красный или жёлтый. Суммируем по всевозможным длинам (от 0 до n не включительно), вычитаем из ранее найденного и получаем ответ.

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

Посчитаем количество всех поездов, которые можно собрать в данном наборе, и потом вычтем количество поездов, в которых не более $n − 1$ вагонов.

Зафиксируем число $k$ $(0≤ k≤ 2n)$ и посчитаем, сколько всего поездов с ровно $k$ красными вагонами. Жёлтых вагонов может быть от $0$ до $3n,$ и для каждого числа $l$ жёлтых вагонов от $0$ до $3n$ мы выбираем $k$ мест в строке длины $k+l.$ Таким образом, искомое количество поездов с $k$ красными вагонами равно сумме

Ckk +Ckk+1 +⋅⋅⋅+ Ckk+3n

Докажем, что эта сумма равна $k+1 Ck+3n+1.$

Распишем каждое слагаемое, пользуясь следующим тождеством Паскаля:

b+1 Cba = Ca+1− Cb+a1

Мы получим:

( k+1 k+1) ( k+1 k+1) ( k+1 k+1) ( k+1 k+1 ) ( k+1 k+1) Ck+1 − Ck + C k+2 − Ck+1 + Ck+3 − Ck+2 + ⋅⋅⋅ + Ck+3n− Ck+3n−1 + Ck+3n+1− Ck+3n

В каждой скобке вычитаемое равно уменьшаемому из предыдущей скобки. Нетронутым останется лишь уменьшаемое в последней скобке, равное $k+1 Ck+3n+1,$ — это и есть искомый результат сложения.

Заметим, что в силу симметрии биномиальных коэффициентов этот результат можно переписать как

k+1 3n Ck+3n+1 = Ck+3n+1

Теперь нужно сложить эти числа по всем $k$ от $0$ до $2n.$ Получим сумму

3n 3n 3n C3n+1 +C3n+2+ ⋅⋅⋅+ C5n+1

которая суммируется аналогичным образом через тождество Паскаля, и результат этого суммирования равен

3n+1 3n 2n+1 C5n+2 − C3n = C5n+2 − 1

Мы посчитали количество всех поездов. Осталось лишь вычесть количество поездов, в которых не более $n − 1$ вагонов, но для каждого $l≤ n− 1$ количество поездов длины $l$ очевидно равно $2l,$ а всего в сумме таких поездов $2n− 1.$ Таким образом, длинных поездов $C2n+1− 2n. 5n+2$

Ответ:

$C2n+1− 2n 5n+2$

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

Задача 3#94343

Назовем упорядоченную четвёрку целых чисел $(a,b,c,d)$ интересной, если верно, что $1≤ a< b<c <d ≤10$ и $a+ d> b+c.$ Сколько существует интересных упорядоченных четвёрок?

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

Подсказка 1

Заметим, что если в четверке (a, b, c, d) выполняется a + d > b + c, то в четверке (11-a, 11-b, 11-c, 11-d) это неравенство выполняется в другую сторону и наоборот. Как тогда найти количество нужных пар?

Подсказка 2

Верно! Нужно из количества всех четверок, вычесть количество тех четверок, у которых a + d = b + c и разделить получившееся число на 2. Как найти число четверок с равенством?

Подсказка 3

Точно! Сумма a + d является числом от 3 до 19. Можно посчитать для каждого числа количество разбиений в сумму двух натуральных чисел, меньших 11. Тогда легко посчитать общее количество.

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

Предположим, что для упорядоченной четвёрки $a< b< c< d$ верно, что $a +d> b+ c,$ тогда

(11− a)+ (11− d)< (11− b)+(11− c)

И наоборот, если $a+d <b +c,$ то

(11− a)+ (11− d)> (11− b)+(11− c)

То есть, упорядоченные четвёрки $a <b< c< d$ с условием $a+ d> b+ c$ находятся во взаимно-однозначном соответствии с упорядоченными четвёрками $a <b <c< d$ с условием $a+ d< b+ c.$ Посчитаем количество четвёрок со свойством $a+ d= b+ c.$ Заметим, что $(a +d)$ является целым числом из промежутка $[3,19].$ Для каждого числа из этого диапазона посчитаем количество разбиений числа в сумму двух различных натуральных слагаемых, меньших $11.$ Тогда всего таких четвёрок будет

2 2 2 2 2 2 2 2 2 2C1 + 2C2 + 2C3 + 2C 4 +C 5 + 2C4 +2C3 +2C2 + 2C1 = 2+ 6+ 12 +10+ 12+6 +2 =50

С другой стороны, количество всех четвёрок равно $C410 = 210.$ Тогда оставшиеся $210− 50 =160$ четвёрок бьются на пары, в каждой из которых нам подходит ровно одна четвёрка. Получаем ответ $160∕2= 80.$

Ответ:

$80$

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

Задача 4#94903

Найдите количество способов расставить 4 одинаковые фигуры на шахматной доске размером $8× 8$ так, что три из них будут находиться либо на одной горизонтали, либо на одной вертикали, либо на одной из двух главных диагоналей.

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

Подсказка 1

Для начала попробуем разбить задачу на две более простые. Какие случаи будем различать для подсчета?

Подсказка 2

Верно! Будем рассматривать два случая: либо 3 фигуры на одной линии — диагонали, горизонтали и вертикали, либо все 4 фигуры стоят на одной линии. Как посчитать количество способов во втором случае?

Подсказка 3

Всего у нас 18 доступных линий: диагоналей, горизонталей и вертикалей. Посчитаем нужное количество для одной линии. Тогда достаточно выбрать 4 клетки из 8 доступных. А как посчитать количество для одной линии во втором случае и как после этого получить общее количество?

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

Наша задача эквивалентна тому, чтобы найти число способов расставить три одинаковые фигуры на одной линии (диагонали, горизонтали, вертикали) и одну не на этой линии или расставить $4$ одинаковые фигуры на одной линии. Всего у нас $18$ различных линий. Число способов расставить фигуры на одну линию равно $3 1 4 C8 ⋅C56+ C8 = 3206.$ Тогда итоговый ответ равен $3206⋅18 =57708.$

Ответ:

$57708$

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

Задача 5#68519

Дано нечётное число $n$ . В классе $2n$ человек. Известно, что $n$ из них мальчики. Каждый день какие-то $n$ учеников назначаются дежурными. Известно, что девочек среди дежурных всегда меньше половины. Какое максимальное число дней команда дежурных может не повторяться?

Источники: автор И. А. Ефремов

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

Рассмотрим произвольный подходящий набор из $n$ дежурных. Заметим, что все ученики, которых мы не взяли, образуют не подходящий набор. И наоборот, дополнение не подходящего набора является подходящим набором. Тогда подходящих и не подходящих наборов поровну. То есть подходящих наборов ровно $n C2n∕2$ .

Ответ:

$Cn ∕2 2n$

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

Задача 6#69399

У бельчонка есть 5 орехов, 8 грибов и 11 ягод. Сколькими способами он может выложить все эти предметы в ряд так, чтобы никакие две ягоды не лежали рядом?

Источники: Бельчонок-2023, 11.1 (см. dovuz.sfu-kras.ru)

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

Подсказка 1

На расположение ягод есть ограничение, а вот грибы и орехи мы можем класть как захотим. Полезным будет посмотреть, сколькими способами мы можем выложить в ряд только орехи и грибы без ягод.

Подсказка 2

Ягоды не должны лежать рядом друг с другом. Значит, теперь, когда мы разложили грибы и орехи, у нас есть 14 позиций под ягоды, при этом в каждое место мы можем положить не более одной ягоды. Вычислите, сколькими способами мы можем это сделать. По какому правилу теперь можно посчитать общее количество случаев?

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

Первое решение.

Выложим в ряд орехи и грибы — сделать это можно $5 C13$ способами. Далее рассмотрим позиции между выложенными орехами и грибами и по краям от них — получим 14 мест для ягод. Остаётся выложить их туда $11 C14$ способами.

Второе решение.

Сначала объединим орехи и грибы в неягоды, откуда получим 13 неягод и 11 ягод. Далее назовём нейтроном пару (неягода, ягода).

Если на крайней левой позиции в ряду лежит неягода, то 11 ягод образуют нейтроны, поскольку рядом с ними не могут находиться другие ягоды, и левее каждой точно есть неягода. Отсюда имеем 11 нейтронов и 2 дополнительные неягоды. В итоге получаем $2 C13$ способов поставить эту неягоду, то есть 78 расстановок.

Если на крайней левой позиции лежит ягода, то остаются только 10 ягод, каждая из которых попадает в свой нейтрон. Получаем 10 нейтронов и 3 неягоды, откуда имеем $C313 = 286$ расстановок.

Получаем $364= C314$ расстановки. Остаётся вспомнить, что неягоды делятся на два вида. Чтобы учесть это, домножим все способы на $51!3!⋅8!,$ то есть число способов расставить $5$ орехов среди тринадцати неягод, откуда и получаем ответ.

Ответ:

$C5 ⋅C11 13 14$

Курсы

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

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

Задача 7#73598

Докажите, что произведение $n$ подряд идущих чисел делится на $n!.$

Показать доказательство

Если среди чисел есть ноль, то задача тривиальна. В противном случае можно считать, что последовательные числа положительные, потому что знак тут роли не играет. Рассмотрим число сочетаний $k Cn+k$ для натурального $k$ и неотрицательного целого $n.$ Как известно, при любых $n$ и $k$ оно целое. Распишем его: $k (n+k)! (n+1)(n+2)⋅...⋅(n+k) Cn+k = k!n! = k! .$ Заметим, что в числителе находится произведение $k$ последовательных чисел, а в знаменателе — $k!,$ то есть мы получили требуемое.

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

Задача 8#34020

Перед Дашей лежит доска $10×10$ . Она хочет обвести по контуру на этой доске клетчатый прямоугольник. Сколькими способами Даша может это сделать? Прямоугольники одинакового размера, но отмеченные в разных местах, считаются различными.

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

Чем задается прямоугольник на доске? Четырьмя сторонами, идущими по границам клеток: верхней, нижней, правой и левой. Сколько способов выбрать нижнюю и верхнюю стороны? Столько же, сколько выбрать две горизонтальные линии, идущие по границе клеток, из 11 линий (так как 10 горизонтальных полосок из клеток, у которых всего 11 горизонтальных линий сетки), а это $2 C11$ . Аналогично, $2 C11$ способов выбрать левую и правую границу. Границы выбираем независимо, поэтому ответ $2 2 (C11)$ . $(11⋅10)2 --2--$ .

Ответ:

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

Задача 9#50997

На сторонах треугольника $ABC$ отметили точки: $10$ — на стороне $AB,11$ — на стороне $BC,12$ — на стороне $AC.$ При этом ни одна из вершин треугольника не отмечена. Сколько существует треугольников с вершинами в отмеченных точках?

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

Первое решение.

Три точки из $33$ данных можно выбрать $3 C33 =5456$ способами.

При этом треугольник образуется во всех случаях за исключением того, когда все три точки лежат на одной прямой. Итак, не подходят $3 3 3 C12+ C11+C 10 =220+ 165 +120= 505$ случаев.

Значит, всего есть $5456− 505 =4951$ треугольник.

Второе решение.

Выбрать по одной точке на каждой стороне можно $1 1 1 C 12⋅C11⋅C10 = 12⋅11 ⋅10 =1320$ способами.

Выбрать две точки на одной стороне и одну точку на другой можно $2 1 2 1 2 1 2 1 2 1 2 1 C12⋅C11+ C12⋅C10 +C11⋅C12+ C11 ⋅C 10+ C10⋅C12+C 10⋅C11 = 66⋅21+55⋅22+ 45⋅23 =1386+ 1210+ 1035 =3631$ способами.

Значит, всего есть $1320+ 3631 =4951$ треугольник.

Ответ:

$4951$

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

Задача 10#71371

В Криптоландии используется алфавит, состоящий из четырёх латинских букв $a,b,c,d.$ Любая последовательность букв алфавита будет словом криптоландского языка при выполнении единственного ограничения: если в последовательности есть хоть одна буква " $a$ то тогда в ней обязательно должны встретиться две буквы " $a$ "подряд.

Например, последовательности $baacda,aabb,ddd$ являются словами, а последовательности $bcadda,abba$ — не являются. Найдите число слов длины 8 в криптоландском языке.

Источники: Верченко-2022 (см. v-olymp.ru)

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

Подсказка 1

Всего существует 4⁸ последовательностей длины 8, составленных из букв криптоландского алфавита. Подумайте, как удобнее всего почитать число тех последовательностей, которые являются словами.

Подсказка 2

Все последовательности разбиваются на три непересекающихся множества: 1. Не содержащие буквы a; 2. Содержащие букву а и хотя бы одну пару аа; 3. Содержащие букву а и не содержащие ни одной пары аа. При этом очевидно, что элементы 1 и 2 множеств являются словами, а 3 - нет. Посчитать число элементов второго множества выглядит либо очень сложной задачей, либо вовсе нереальной. Тогда удобнее всего найти число последовательностей, являющихся словами, будет просто вычтя из 4⁸ число элементов 3 множества. Подумайте, каким образом их можно сосчитать.

Подсказка 3

Для n букв а в слове возможно найти число способов расставить их в последовательности длины 8 по формуле: число сочетаний из 8+1-n по n. Кроме того у нас есть еще 3^(8-n) способов расставить b, c, d на оставшиеся места. Подумайте, какое максимально значение может принимать n.

Подсказка 4

При n ≥ 5 гарантировано будет существовать пара aa. Значит, они нам не подходят. Теперь найдем число последовательностей для n = 1, 2, 3, 4, сложим их и таким образом получим количество элементов 3 множества.

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

Множество всех последовательностей длины $8$ состоит из $48$ последовательностей. Это множество разбивается на три непересекающихся между собой подмножества:

1.: Последовательностей, не содержащих $a.$
2.: Последовательностей, содержащих $a,$ но не содержащих двух подряд идущих таких букв.
3.: Последовательностей, содержащих $a$ , в которых встречаются две подряд идущие такие буквы.

Чтобы решить задачу, нужно найти число последовательностей во втором подмножестве и вычесть его из числа $48.$

В свою очередь, множество последовательностей второго типа можно разбить на непересекающиеся подмножества, в которые входят последовательности, содержащие $1,2,3,4$ букв " $a$ ".

Поскольку число последовательностей длины $8$ , содержащих ровно $t$ отдельно стоящих букв $a$ , равно $Ct8+1−t(4− 1)8−t,$ то общее число последовательностей второго типа будет равно

4∑ t 8−t C9−t3 =38070 t=1

В итоге получаем

48 − 38070 =27466

Ответ: 27466

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

Задача 11#74092

Дан клетчатый квадрат $101× 101.$ Внутри него выбирается квадрат $100× 100.$ Внутри этого квадрата выбирается квадрат $99 ×99,$ и так далее, пока не будет выбран квадрат $1×1.$ Оказалось, что выбранный квадрат $1×1$ совпадает с центральной клеткой исходного квадрата $101× 101.$ Сколько существует таких последовательностей квадратов? Ответ не должен содержать знака многоточия.

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

Подсказка 1

Смотрите, у нас есть конкретный процесс по изменению квадратов. Мы знаем, где находится центральная клетка квадрата в начале и конце процесса (в одном и том же месте). Значит, надо последить за ее движением в процессе уменьшения квадрата. Подумайте, как это сделать.

Подсказка 2

Сразу понять, как движется клетка, не так и просто. Но можно рассмотреть более простые объекты, связанные с ней. Подумайте, какие.

Подсказка 3

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

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

Будем следить за центром квадрата. При выборе меньшего квадрата две его границы остаются на месте, две — смещаются на одну клетку. Следовательно, центр смещается на полклетки влево-вверх, влево-вниз, вправо-вверх или вправо-вниз. За $100$ операций центр должен вернуться в исходное положение, поэтому сделает по $50$ передвижений влево и вправо ( $50 C100$ способов) и по столько же перемещений вверх и вниз. Так как мы должны скомбинировать все подходящие способы передвигать квадрат по вертикали и по горизонтали, ответом будет $( 50 )2 C100 .$

Ответ:

$(C50 )2 100$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#74784

Пусть $a + ...+ a = n 1 m$ , где $a ,...,a 1 m$ - натуральные числа. Докажите, что $n$ ! делится на произведение

a1!⋅a2!⋅...⋅am!

Источники: ФЕ-2022, 11.1 (см. www.formulo.org)

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

Подсказка 1

Мы знаем, как представить n в виде суммы. Попробуем представить n! в виде произведения, используя данные о сумме.

Подсказка 2

Заметим, что мы можем выразить n! как произведение a_1 подряд идущих чисел на a_2 подряд идущих чисел…и так далее…теперь нужно доказать делимость на произведение каждого из факториалов.

Подсказка 3

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

Показать доказательство

Давайте для начала докажем вспомогательную лемму: произведение $k$ подряд идущих чисел делится на $k!$

.. (n+ 1)(n+ 2)⋅...⋅(n +k).k!

Заметим, что количество способов выбрать $k$ человек из $k +n$ равно

(n+-k)(n+-k−-1)⋅...⋅(n-+1) k!

Но количество способов - целое число, поэтому числитель делится на знаменатель. Лемма доказана.

Так как $a1+ a2+...+am = n,$ то $n!$ можно представить в виде произведения $a1$ подряд идущих чисел на $a2$ следующих чисел $...$ на $am$ последних чисел:

n!= (1⋅2⋅...a1)⋅((a1+ 1)⋅(a1+ 2)⋅...⋅(a1+ a2))⋅...⋅((n − am +1)⋅...⋅n)

Произведение $ai$ подряд идущих чисел делится на $ai!,$ поэтому $n!$ делится на произведение факториалов $a1!⋅...⋅am!$

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

Задача 13#80162

У Ильи $6$ друзей, и ежедневно в течение $20$ дней он приглашает к себе в гости троих из них так, что компания ни разу не повторяется. Сколькими способами он может это сделать?

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

Подсказка 1

Так как Илья приглашает к себе тройки друзей, то естественно задаться вопросом, сколько их всего. Вспомните, как это можно посчитать.

Подсказка 2

Давайте же посчитаем. Выходит, что способов выбрать первого друга 6, второго — 5, первого — 4. Но порядок нам не важен, поэтому делим на 3!=6. После сокращения получаем 20. По условию нам сказано посчитать число способов пригласить компании без повторений. Как тогда можно переформулировать задачу?

Подсказка 3

Да, это число способов, как можно переставить наши тройки. Получается, что у нас 20 дней и 20 троек, каждая из которых точно была. Осталось только вспомнить, как считать число перестановок, и победа!

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

Заметим, что всего существует $C3= 20 6$ различных комбинаций из трёх друзей. Значит, каждая из этих $20$ троек в какой-то день была приглашена. Таким образом, искомое количество способов равно количеству способов переставить двадцать троек, то есть $20!$

Ответ:

$20!$

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

Задача 14#30937

Найдите количество восьмизначных чисел, произведение цифр каждого из которых равно $3375.$ Ответ необходимо представить в виде целого числа.

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

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

Подсказка 1

Если произведение 8 цифр это 3375, то надо выяснить, какие это могут быть цифры вообще и сколько раз они встречаются в записи числа.

Подсказка 2

Ага, получилось два набора цифр: в одном пятерки, тройки и единички, в другом есть помимо них девятка. Находим, сколько в первом наборе способов поставить тройки, потом на оставшиеся места пятерки и тд, то же делаем для второго набора и понимаем, что эти наборы не пересекаются -> работает правило сложения

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

Разложим $3375$ на множители. $3375 =5⋅675= 52⋅135= 53⋅27= 53⋅33.$ Значит, либо в нашем числе есть $3$ пятерки, $3$ тройки и остальные единицы, либо в нашем числе есть $3$ пятерки, $1$ девятка, $1$ тройка и остальные единицы.

В первом случае способов выбрать места для пятерок можно $3 8⋅7⋅6 C8 = 3!$ способами, так как нам нужно выбрать три места из восьми для пятерок. Затем выбрать места для троек $3 5⋅4⋅3 C5 = 3!$ вариантов, а остальные места займут единицы, поэтому всего в этом случае $8⋅7⋅6 5⋅4⋅3 3! ⋅ 3! =56⋅10= 560$ вариантов.

В втором случае способов выбрать места для пятерок так же $3 8⋅7⋅6 C8 = 3! ,$ выбрать место для тройки можно из оставшихся пяти, для девятки — из оставшихся четырёх, а остальные места займут единицы, поэтому всего в этом случае $8⋅7⋅6 3! ⋅5⋅4= 56⋅20= 1120$ вариантов.

Итого $1120+ 560 =1680$ вариантов.

Ответ:

$1680$

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

Задача 15#67075

Найдите количество восьмизначных чисел, произведение цифр которых равно $1400.$ Ответ необходимо представить в виде целого числа.

Источники: Физтех - 2020, 10 класс (см. olymp.mipt.ru)

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

Подсказка 1

Разложим 1400 на простые множители, чтобы посмотреть, какие вообще наборы цифр есть для того, чтобы составить нужные по условию числа.

Подсказка 2

Отлично, получается 3 набора: "22255711", "42557111" и "85571111". Перестановкой цифр в каждом наборе мы получаем нужное число. Поработаем с первым набором: допустим, в нем все цифры разные, тогда подошло бы 8! чисел. Но теперь заметим, что не все цифры одинаковые, например, двойки повторяются 3 раза. Это значит, что на самом деле подходящих чисел в 3! раз меньше. То же проделаем и с пятерками (и с единичками тоже).

Подсказка 3

Отлично, в первом наборе получили 8! / (3! * 2! * 2!) вариантов. Аналогично считаем варианты и в втором, и в третьем наборах. Теперь остается сложить все эти варианты и получить итоговый ответ.

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

Разложим $1400$ на множители. $1400 =5⋅280= 52⋅56 =52⋅7⋅8= 23⋅52⋅7.$ Значит, искомые числа могут состоять из следующих цифр:

1) три двойки, две пятёрки, одна семёрка и две единицы,

2) четвёрка, двойка, две пятёрки, одна семёрка и три единицы,

3) восьмёрка, две пятёрки, одна семёрка и четыре единицы.

В первом случае способов выбрать места для двоек можно $3 8⋅7⋅6 C8 = 3!$ способами, так как нам нужно выбрать три места из восьми для двоек. Затем выбрать места для пятёрок $2 5⋅4 C5 = 2!$ вариантов, затем одно из трёх оставшихся мест для семёрки $3$ способами, а остальные места займут единицы, поэтому всего в этом случае $8⋅7⋅6 5⋅4 -3!-⋅-2! ⋅3= 1680$ вариантов.

В втором случае способов рассуждения абсолютно аналогично для трёх единиц, двух пятёрок, семёрки, но дальше есть ещё 2 способа выбрать место двойке, а оставшееся место занимает четвёрка. В этом случае $1680⋅2$ вариантов.

В третьем случае выбрать места для единиц можно $C48 = 8⋅7⋅64!⋅5$ способами, далее для двух пятёрок $C24 = 4⋅32$ способа, оставшиеся восьмёрку и семёрку ставим двумя способами. Всего получается $70⋅6⋅2= 840$ вариантов.

Итого $1680⋅3+ 840 =5880$ вариантов.

Ответ:

$5880$

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

Задача 16#126028

Фигура (см. рисунок) состоит из одинаковых квадратных клеток, и две из них покрасили в синий цвет, а остальные клетки остались белыми. Сколько существует таких раскрасок, если раскраски, получающиеся друг из друга поворотом, считаются за одну?

$PIC$

Источники: Бельчонок - 2020, 11.4 (см. dovuz.sfu-kras.ru)

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

Подсказка 1

Давайте сначала поймём, сколько всего существует способов раскрасить в синий 2 клетки на поле. Ведь это же можно легко посчитать! Действительно, количество способов равно 21 × 20 / 2 = 210.

Подсказка 2

Теперь давайте подумаем, сколько из этих раскрасок являются центрально-симметричными. Для того, чтобы раскраска была центрально-симметричной, необходимо выбрать любую клетку поля, отличную от центральной, и ей будет соответствовать одна симметричная. Получается, что таких раскрасок целых 10 штук!

Подсказка 3

Чтобы решить задачу, необходимо учесть подсказки 1 и 2, а также понять, сколько раскрасок можно получить поворотом из центрально-симметричных и не являющихся центрально-симметричными.

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

Всего способов выбрать две чёрные клетки $C2 = 21⋅20-=210. 21 2$ Если синие клетки центрально-симметричны, то для каждой такой раскраски можно поворотом (на $∘ 90$ ) получить ещё ровно одну раскраску. Всего центрально-симметричных раскрасок $20- 2 =10$ (в качестве первой клетки можно выбрать любую, кроме центральной, вторая клетка определяется из симметрии относительно центра единственным образом). Остальных раскрасок $210− 10= 200,$ и из каждой такой раскраски можно поворотом получить ещё три раскраски. Таким образом, число раскрасок, различных при поворотах, равно $10 200- 2 + 4 =55.$

Ответ:

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

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

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

Задача 17#126030

Квадрат $5× 5$ расчертили на 25 одинаковых клеток, и две из них покрасили в синий цвет, а остальные клетки остались белыми. Сколько существует таких раскрасок, если раскраски, получающиеся друг из друга поворотом, считаются за одну?

Источники: Бельчонок - 2020, 11.4 (см. dovuz.sfu-kras.ru)

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

Подсказка 1

Давайте сначала поймём, сколько всего существует способов раскрасить в синий 2 клетки на поле. Ведь это же можно легко посчитать! Действительно, количество способов равно 25 × 24 / 2 = 300.

Подсказка 2

Подсказка 3

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

Всего способов выбрать две синие клетки $C2 = 25⋅24-=300. 25 2$ Если выбранные клетки симметричны относительно центра, то из такой раскраски можно получить еще ровно одну (поворотом на $∘ 90$ ). Чтобы построить такую раскраску, достаточно выбрать любую из $24$ не центральных клеток, а вторая определяется однозначно). Итого $24 2 = 12$ раскрасок.

Остальных раскрасок $300− 12 =288,$ из каждой такой раскраски можно поворотом на $∘ 90$ получить еще 3 раскраски. Таким образом, число раскрасок, различных при поворотах, равно $12- 288- 2 + 4 = 78.$

Ответ:

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

Задача 18#30938

На столе лежат $130$ различных карточек с числами $502,504,506,...,758,760$ (на каждой карточке написано ровно одно число, каждое число встречается ровно один раз). Сколькими способами можно выбрать $3$ карточки так, чтобы сумма чисел на выбранных карточках делилась на $3?$

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

Подсказка 1

Так, нас просят выбрать три числа так, чтобы их сумма делилась на три. В таком случае, какие остатки должны быть у чисел при делении на 3?

Подсказка 2

Да, числа должны давать либо одинаковые остатки, либо наоборот различные(0, 1, 2). Можно ли посчитать, какие остатки при делении на 3 дают числа в условии задачи?

Подсказка 3

Да, можно, так 502 ≡ 1 (mod=3), 504 ≡ 0 (mod=3), 506 ≡ 2(mod=3), …, 760 ≡ 1(mod=3). То есть, по модулю 3: 44 числа сравнимы с единицей, 43 числа сравнимы с двойкой, 43 числа сравнимы с нулем. Как посчитать общее число способов?

Подсказка 4

Выбрать три числа с разными остатками, это просто 43*43*44. А если мы хотим выбрать три числа с одинаковым остатком, то нужно воспользоваться формулой числа сочетаний. И посчитать сумму всех этих способов!

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

Первое решение.

Если мы возьмём три карточки с числами подряд по возрастанию, то среди них будут по одной карточке с остатками $0,1$ и $2$ при делении на $3.$ Значит, среди карточек $502,504,506,...,758$ по $43$ карточки с каждым остатком (разобьём на $43$ тройки подряд идущих) и ещё есть карточка с числом $760,$ которое дает остаток $1.$

Давайте подумаем, какие есть варианты для остатков трёх карточек, чтобы их сумма делилась на $3:$ либо все три числа должны давать разные остатки (способов выбрать так карточки $43 ⋅44⋅43,$ так как выбрать карточку с остатком $0$ — $43$ способа, способов выбрать карточку с остатком $1$ — $44$ и способов выбрать карточку с остатком $2$ — $43$ ), либо все три остатка $0$ (тогда способов $3 C 43),$ либо все три остатка 1 (тогда способов $3 C44),$ либо все три остатка $2$ (тогда способов $3 C43).$ Итого всего

43⋅44⋅43+C343+ C344+ C343 = 81356+ 12341+ 13244+ 12341= 119282

Второе решение.

Данные числа, расположенные в порядке возрастания, образуют арифметическую прогрессию с разностью $2≡3 −1.$ Следовательно, остатки от деления на $3$ у этих чисел чередуются (идут по убыванию с шагом $1,$ то есть $0→ 2→ 1→ 0→ ...$ ).

Среди данных нам чисел есть $44,$ дающие остаток $1$ от деления на $3$ (они образуют множество $A ={502;508;514;...;760}$ ), $43$ числа, делящихся на $3$ (образуют $B = {504;510;516;...;756}$ ) и $43$ числа, дающих остаток $2$ от деления на $3$ ( $C ={506;512;518;...;758}$ ).

Сумма трёх чисел может делиться на $3$ в следующих случаях.

1.: Все три числа дают одинаковые остатки от деления на $3.$ Есть $C344$ способов выбрать $3$ числа из множества $A$ и по $C343$ способов выбрать $3$ числа из множеств $B$ и $C.$ В сумме получаем $44⋅436⋅42+ 2⋅ 43⋅462⋅41-=13244+2 ⋅12341= 37926$ способов.
2.: Если не все остатки одинаковы, то подходит только случай, когда все три остатка разные, т.е. мы должны выбрать по одному числу из каждого из множеств $A,B,C.$ Получаем $44 ⋅43⋅43= 81356$ способов. Если есть два равных остатка, то для кратности их суммы трём третий должен быть таким же.

В сумме выходит $119282$ способов.

Ответ:

$119282$

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

Задача 19#39646

Сколько диагоналей в правильном $32$ -угольнике не параллельны ни одной из сторон этого $32$ -угольника?

Источники: Ломоносов-2017, 9.3 (см. olymp.msu.ru)

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

Подсказка 1

Давайте попробуем посчитать эти диагонали через разность, общее количество минус количество параллельных хоть какой-то стороне. То что мы вычитаем, считать немного проще, чем то что дано нам изначально. Сколько же у нас всего диагоналей?

Подсказка 2

Верно, всего 32 вершины и после выбора одной 3 уже выбрать нельзя(эту и две соседние), поэтому 32*29/2, так как посчитали по два раза одну и ту же диагональ(выбрав одну точку, а потом у этой диагонали точку напротив). Что же теперь с "параллельными" диагоналями. А сколько у нас всего пар параллельных сторон? Выбрав какую-то из них, сколько будет параллельных диагоналей именно им?

Подсказка 3

Ага, пар 16, и, выбрав какую-то из них, остаётся ещё 28 точек, которые мы можем соединить попарно. Итого 14 диагоналей для одной пары. Осталось только умножить это на количество пар и дорешать задачу.

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

Первое решение.

Пронумеруем вершины, начиная с произвольной. Заметим, что диагональ параллельна какой-то стороне тогда и только тогда, когда номера вершин в ней имеют разную чётность. Действительно, из второго очевидно следует первое, достаточно рассмотреть операцию “сдвинем одну вершину по часовой, а другую — против”, такими операциями мы будем получать параллельные отрезки и попадём в сторону (при такой операции чётность не меняется и в итоге приходим к соседним вершинам, которые имеют разную чётность). Из этой же операции получаем следствие в обратную сторону, поскольку такие операции сходятся в точку.

Нам нужно найти число непараллельных сторонам диагоналей. Так что задача сводится к поиску числа пар вершин одинаковой чётности. Число способов выбрать две вершины с чётными номерами $2 C16,$ аналогично с нечётными. Получаем всего $16⋅15 =240$ диагоналей.

Второе решение.

Всего в $32$ -угольнике

32⋅ (32−2-3)= 464

диагоналей. Разобьем стороны на $16$ пар параллельных сторон. Несложно заметить, что если зафиксировать какую-то пару ( $4$ вершины), то оставшиеся вершины можно соединить попарно диагоналями, параллельными этой паре. Их всего будет $(32−24)= 14.$ Значит, диагоналей, параллельных какой-то стороне $− 14⋅16=224.$ А непараллельных $464− 224 =240.$

Ответ:

$240$

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

Задача 20#78845

На сторонах треугольника $ABC$ отмечены точки: 10 точек на стороне $AB$ , 11 точек на стороне $BC$ , 12 точек на стороне $AC$ . Вершины треугольника соединили отрезками со всеми точками на противоположных сторонах. Никакие три проведённых отрезка не проходят через одну точку. Сколько всего треугольников можно увидеть на этой картинке?

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

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

Подсказка 1

Нам сказали, что никакие три проведённых отрезка не пересекаются в одной точке, а значит, любые 2 образуют свою точку, попробуйте выбрать 3 отрезка и посмотреть на точки их пересечения, что мы можем про них сказать?

Подсказка 2

Верно, когда мы выберем 3 отрезка, то получим 3 точки - вершины треугольника, а значит, задача свелась к выбору трёх отрезков (не забудьте про стороны исходного треугольника, они тоже могут выступать в качестве сторон треугольников, которые мы считаем).

Подсказка 3

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

Подсказка 4

Правильно, надо исключить выборки тех отрезков, которые имеют общую точку в вершине исходного треугольника, ведь для остальных треугольников по условию задачи у нас найдутся 3 точки пересечения, а значит, и треугольник.

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

Треугольник образуют любые три проведённые отрезка (с учётом сторон, то есть из 36 возможных), если они не исходят из одной и той же вершины $△ABC.$ Вычитая тройки отрезков от каждой вершины из всевозможных троек отрезков, получаем

3 ( 3 3 3) C36− C12+ C13+C 14 = 7140 − 870= 6270

$PIC$

Ответ: 6270

Предыдущая подтема

Следующая подтема