(руководитель Александр Шаповалов)
Сочетания. Если есть N
предметов, то из них можно выбрать
k предметов C(N,k) способами (читается
"цэ из эн по ка"). Порядок предметов нам не
важен. Мы можем эти k предметов
расставить по порядку k! способами,
поэтому
из каждого сочетания по k можно получить
k! размещений по k. Значит, C(N,k)·k! = Nk.
Поэтому число сочетаний из N по k
C(N,k) = N(N-1)(N-2)...(N-k+1) / k!
(в числителе и знаменателе по k
сомножителей).
Упражнения
1. Вычислите
a) 102 Ответ
b)
C(10,2) Ответ
2. Вычислите
a) 93 Ответ
b)
C(9,3) Ответ
c) 93 / C(9,3) Ответ
3. Есть 9 предметов на выбор. Сколькими
способами можно
а) составить список из трех предметов по
порядку? Ответ
b) выбрать набор из трех предметов (порядок
не важен)? Ответ
4. В команде 10 человек. Сколькими
способами можно
а) выбрать из них капитана и заместителя?
Ответ
b) выбрать из них двух дежурных? Ответ
5. В команде 10 человек. Сколькими способами можно выбрать из них 8 игроков на ближайшую игру? Ответ
6. Вычислите C(9,6). Объясните, почему ответ совпадает с одним из ответов выше. Ответ
7. В карточке лотереи "4 из 12" надо заполнить 4 пронумерованные клеточки из 12. При розыгрыше наугад вынимаются 4 номера из 12. Главный приз выигрывает тот, кто угадает все номера. Сколько карточек надо заполнить, чтоб наверняка получить главный приз? Ответ
Задачи
8. Вычислите С(1001,3) / С(1001,2) Ответ
9. В карточке надо отметить 4 лошадей из 12 участниц забега. Приз "Миллион" выигрывает тот, у кого все 4 отмеченные лошади придут среди первых четырех. Пете подсказали двух лошадей, которые точно не окажутся в первой четверке. Сколько карточек ему надо заполнить, чтоб наверняка получить приз "Миллион"? Ответ
10. В команде 15 человек, включая Петю.
На ближайшую игру надо выбрать 11 человек.
Сколькими способами это можно сделать так,
чтобы
а) взять Петю? Ответ
b) не взять Петю? Ответ
(ответ можно давать в виде C(...,...), не доводя
до числа.
11. Не вычисляя, докажите что
а) C(14,11)+C(14,10) = C(15,10)
b) C(N-1,k)+C(N-1,k-1) = C(N,k)
12 а) Среди 9 шаров три радиоактивных. Можно проверять на радиоактивность кучку из любых шаров.
Объясните, почему не существует способа за 6
проверок гарантированно найти все три радиоактивных шара. (Измеритель радиоактивности не показывает уровня радиации, а только выдает ответ «в данной кучке шаров нет радиоактивных» или «в данной кучке шаров есть радиоактивные»)
Ответ
b) Среди 9 монет – три фальшивых (легче
настоящих). Объясните, почему не существует
способа за 4 проверки гарантированно найти
все три фальшивых монеты. Ответ
13. Сколько есть 10-значных чисел, составленных из трех цифр 5 и семи цифр 6? Ответ
14* Шахматной ладье разрешили
ходить только на одну клетку вверх или на
одну клетку вправо. Сколькими способами она
может добраться из правого нижнего угла
угла в левый верхний на доске размером
a) 3x3 Ответ
b) 4x4 Ответ
c)
8x8 Ответ
d) NxN Ответ
e) MxN ? Ответ