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

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

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

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

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

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

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

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

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

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

На сторонах треугольника $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

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

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

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

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

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

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

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

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

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

Ответ:

$711$

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

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

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

Источники: ПВГ-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

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

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

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

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

Ответ:

$1024$

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

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

Дан правильный 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

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

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

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

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

Подсказка 1

У нас есть условие на синие шары, поэтому давайте их пока трогать не будем. Сколько есть способов разложить в ряд 3 красных и 5 зеленых шаров?

Подсказка 2

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

Подсказка 3

Да, надо просто располагать синие шары между красными и зелеными, а еще можно положить их в конец или начало исходного ряда! Сколько способов есть это сделать?

Подсказка 4

Конечно, число сочетаний из 9 по 4.

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

Сначала разложим красные и зелёные шары. Для этого, не умаляя общности, надо выбрать $3$ места из $8$ для красных шаров. Между ними (а также слева и справа) остаётся $9$ мест, куда можно ставить синие шары. Из этих мест надо выбрать четыре. Итого $3 4 C8 ⋅C 9 = 7056.$

Ответ:

$7056$

Курсы

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

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

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

Сколько существует способов выбрать из $n$ человек футбольную команду, в которой будет ровно $k$ человек? А сколько при этом есть способов выбрать тех $n− k$ человек, которые в футбол играть не будут? Докажите, что $k n−k Cn = Cn$ .

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

Заметим, что каждый раз, когда мы выбираем $k$ человек, которые будут играть в футбол, мы также выбираем $n− k$ человек, которые играть в футбол не будут. Поэтому количество способов выбрать $k$ человек, которые будут играть в футбол, столько же, сколько есть способов выбрать $n− k$ человек, которые в футбол играть не будут. Соответственно, по определению в первом случае способов $k Cn$ , а во втором — $n−k Cn$ . Из сказанного выше следует, что эти количества равны.

Ответ:

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

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

Рассмотрим 6-ю строчку и число 20 в ней. Сколькими способами можно добраться до него от верхней единички, перемещаясь либо вправо-вниз, либо влево-вниз? Подсказка: попробуйте пойти с конца.

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

Будем доказывать, что число способов попасть в каждое число равно самому этому числу. Сначала рассуждаем на примере числа 20.

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

Более строго, будем последовательно для строчек целиком доказывать, что каждое число равно количеству способов в него попасть. Для самой верхней единицы это очевидно: мы уже в ней находимся, значит, есть только 1 способ в нее попасть, а именно никуда не двигаться.

Далее, предположим, что для какой-то строчки мы уже доказали утверждение для каждого числа. Рассмотрим произвольное число $x$ из следующей строчки. В него можно попасть непосредственно из двух чисел $a$ и $b$ , стоящих выше него в предыдущей строке. Для каждого из чисел $a$ и $b$ мы уже знаем, что количество способов попасть в них равно самим числам, то есть $a$ и $b$ соответственно. Поэтому, чтобы получить общее число способов попасть в $x$ , надо сложить количество способов попасть в $a$ и $b$ , то есть $a+ b$ .

Но с другой стороны, по правилу построения треугольника Паскаля, $x = a+b$ . Значит, количество способов попасть в число $x$ равно $x$ , что и требовалось доказать.

Ответ: 20 способами

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

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

Докажите, что в строчке под номером $n$ на $k$ -м месте стоит число $Ck n$ . Напомним, что и строчки, и места в каждой строчке мы нумеруем с нуля.

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

Будем пользоваться тем, что только что доказали в прошлом примере. Рассмотрим $k$ -е число из $n$ -й строки. Чтобы до него добраться, надо ровно $k$ раз пойти вниз-вправо, а остальные $n− k$ раз пойти вниз-влево. По сути надо из $n$ ходов выбрать те $k$ , на которых мы пойдем направо. Как мы уже знаем, количество способов выбрать из $n$ ходов $k$ без учета порядка равно $k Cn$ , значит, и количество способов добраться до рассматриваемого числа равно $k Cn$ . Но также мы уже знаем, что количество способов добраться до числа равно самому числу, значит, в строчке под номером $n$ на $k$ -м месте стоит число $k Cn$ , что и требовалось доказать.

Ответ: