Тема Количество способов, исходов, слагаемых и теория вероятностей

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

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

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

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

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

Подтемы раздела количество способов, исходов, слагаемых и теория вероятностей

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

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

Задача 1#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$

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

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

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

Задача 2#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$

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

Задача 3#68519

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

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

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

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

Ответ:

$Cn ∕2 2n$

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

Задача 4#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$

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

Задача 5#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!,$ то есть мы получили требуемое.

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

Задача 6#34020

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

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

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

Ответ:

Курсы

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

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

Задача 7#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$

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

Задача 8#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

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

Задача 9#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$

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

Задача 10#74784

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

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

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

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

Подсказка 1

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

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

Давайте для начала докажем вспомогательную лемму: произведение $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!$

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

Задача 11#80162

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

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

Ответ:

$20!$

Интенсивы

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

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

Задача 12#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$

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

Задача 13#67075

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

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

Подсказка 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$

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

Задача 14#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$

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

Задача 15#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$

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

Задача 16#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

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

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

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

Задача 17#92736

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

Источники: Лига открытий - 2017

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

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

3 3 C18− 3C7 =3 ⋅16⋅17− 3⋅7⋅5= 711

Ответ:

$711$

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

Задача 18#39430

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

Источники: ПВГ-2014 (см. pvg.mk.ru)

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

Подсказка 1

Поймем, что выбор, к примеру, вратаря, никак не влияет на выбор кого-либо другого(из другой группы) и наоборот. Что это значит? Как нам посчитать кол-во способов набрать одну группу?

Подсказка 2

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

Подсказка 3

Конечно, формула числа сочетаний. Осталось посчитать для каждой группы кол-во способов, потом перемножить это и получить ответ.

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

Выбор каждого вида игроков осуществляется независимо, поэтому количества способов нужно просто перемножить. Покажем, что число способов выбрать $k$ человек из $n$ подходящих на эту роль равно $k ---n!-- Cn =k!(n−k)!.$

Действительно, сначала рассмотрим все перестановки из $n$ человек (которых $n!$ ), будем брать в команду первых $k$ из них. Тогда нам не важен порядок этих $k$ человек, то есть нужно поделить на $k!$ , а также не важен порядок следующих за ними $n− k$ человек, то есть нужно поделить ещё на $(n− k)!$ . Что здесь означает не важен порядок? Если мы его изменим, то выбранная нами команда не поменяется.

В итоге мы показали, что способов $--n!-- k!⋅(n−k)!.$ Используя эту формулу для всех типов игроков и перемножая результаты, получаем

C12 ⋅C25 ⋅C38 = 2⋅10⋅56 =1120

Ответ: 1120

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

Задача 19#39644

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

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

Подсказка 1

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

Подсказка 2

Если бы семей было 7, то нам просто нужно было бы выбрать по одному человеку из каждой семьи. Но у нас 8 семей. Значит сначала нужно выбрать семьи, «представители» которых будут в комиссии. А это, по формуле сочетаний можно сделать C^7_8 способами. Выбрали семьи. Теперь по представителю из каждой надо выбрать. Сколькими способами это можно сделать?

Подсказка 3

У каждой семьи есть два претендента на роль «представителя», поэтому для каждой семьи будет два способа. Семей 7. Осталось посчитать ответ.

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

В комиссии будут участвовать ровно $7$ семей, которых можно выбрать $C7= 8 8$ способами. Далее из каждой надо выбрать одного члена $7 2$ способами, перемножая, получаем ответ.

Ответ:

$1024$

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

Задача 20#78843

Дан правильный 27-угольник $A A ...A 1 2 27$ . Найдите количество неравнобедренных треугольников с вершинами в точках $A1,A2,...,A27$ . Треугольники, отличающиеся порядком вершин (например, $A1A2A4$ и $A2A4A1$ ), считаются за один треугольник.

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Верно, всех треугольников C₂₇³. Чтобы посчитать кол-во равнобедренных треугольников, давайте попробуем найти что-то, что может помочь зафиксировать его.

Подсказка 4

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

Подсказка 5

Если задуматься, то на самом деле р/б треугольников вдвое меньше, потому что когда мы фиксировали его особую вершину, то мы могли выбрать как левую, так и правую из оставшихся вершин при подсчёте и получить тот же треугольник, поэтому результат нужно поделить пополам.

Подсказка 6

А не посчитали ли мы что-то ещё по несколько раз? У нас же есть равносторонние треугольники, которые мы посчитали трижды, ведь они "р/б с трёх вершин", поэтому стоит их вернуть так, чтобы мы их вычли ровно 1 раз.

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

Всего есть $C3 =2925 27$ треугольников. Каждой вершине соответствует $13$ равнобедренных треугольников(с вершиной в этой точке). При этом, если взять $27⋅13= 351$ , то получится, что каждый равносторонний треугольник мы посчитали $3$ раза. Значит, равнобедренных треугольников $351− 2⋅9= 333$ , а неравнобедренных — $2925 − 333= 2592.$

Ответ: 2592

Предыдущий раздел

Следующий раздел