Комбинаторика в задачах (стр. 2 )

7.  Сколько всего четырехзначных чисел можно составить из цифр 0 и 3?

8.  В палатке имеется 3 сорта мороженого: рожок, брикет и эскимо? Наташа и Данил решили купить по одной порции каждого сорта мороженого. Сколько существует вариантов такой покупки?

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

10.  Сколько пятизначных чисел можно составить из цифр 5, 9, 0, 6?

11.  Сколькими способами можно указать на шахматной доске два квадрата – белый и черный? Решите эту же задачу, если нет ограничений на цвет квадратов; если надо выбрать два белых квадрата.

12.  Сколькими способами можно выбрать гласную и согласную буквы из слова «ЗДАНИЕ»

13.  На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?

14.  Из города А в город В ведут две дороги, из города В в город С – три дороги, из города С до пристани – две дороги. Туристы хотят проехать из города А через города В и С к пристани. Сколькими способами они могут выбрать маршрут?

15.  В кафе имеются три первых блюда, пять вторых блюд и два третьих. Сколькими способами посетитель кафе может выбрать обед, состоящий из первого, второго и третьего блюд?

16.  Сколько различных пятизначных чисел, делящихся на 10 можно составить из цифр 0, 1, 2, 3, 4? Каждую цифру можно использовать в записи только один раз.

17.  Сколько пятизначных чисел, делящихся на три, можно составить из цифр 3, 4, 6, 7, 9 если каждое число не содержит одинаковых цифр?

18.    Сколько шестизначных чисел можно составить из цифр 4, 5, 6, 7, 8, 9 так, чтобы каждое из них начиналось с комбинации «567»?

19.  Сколько пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5, 6 так, чтобы каждое из них начиналось с комбинации «45»?

20.  Сколько чётных положительных пятизначных чисел можно получить из цифр 5, 9, 6, 0, так, чтобы цифры в числе не повторялись?

21.  Сколько четных положительных пятизначных чисел можно получить из цифр 1,2,3,4?

22.  Запишите все двузначные числа, в записи которых используются только цифры 3, 5, 7, 9. Сколько двузначных чисел можно записать, если использовать при записи числа каждую цифру только один раз?

23.  В четверг в первом классе должно быть три урока: русский язык, математика и физкультура. Сколько различных вариантов расписания можно составить на этот день?

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

25.  Школьники из Волгограда собрались на каникулы поехать в Москву, посетив по дороге Нижний Новгород. Сколькими различными способами могут ребята осуществить свое путешествие, если из Волгограда в Нижний Новгород можно отправиться на теплоходе ли поезде, а из Нижнего Новгорода в Москву – на самолете, теплоходе, поезде или автобусе? Решите задачу с помощью построения дерева.

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

27.  Лена, Света, Маша, Катя и Наташа пришли к зубному врачу. Сколькими способами они могут встать в очередь?

28.   Девять школьников, сдавая экзамены по математике и информатике, получили отметки «4» и «5». Можно ли утверждать, что по крайней мере двое из них получили по каждому предмету одинаковые отметки?

29.  Сколько существует двузначных чисел, у которых первая цифра больше второй?

30.  К полднику в детском саду на четырёхместный стол поставили сок, молоко, какао и компот. Сколькими способами четверо детей могут выбрать себе один из напитков?

Размещения.

Пусть имеется 4 шара и 3 пустых ячейки. Обозначим шары буквами a, b, c, d. в пустые ячейки можно по-разному разместить три шара из этого набора шаров. Если мы поместим шар a в первую ячейку, шар b во вторую, а шар с в третью ячейку, то получим одну из возможных упорядоченных троек шаров:

a

b

c

Выбирая по-разному первый, второй и третий шары, будем получать различные упорядоченные тройки шаров, например:

a

c

b

b

a

c

a

b

c

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

Размещением из n элементов по k (k ≤ n) называется любое множество, состоящее из любых k элементов, взятых в определенном порядке из данных n элементов.

Число размещений из n элементов по k обозначают (читают «А из n по k»).

Из определения следует, что два размещения из п элементов по k считаются различными, если они отличаются самими элементами или порядком их расположения. Значит, =n(n – 1)(n – 2)∙…∙(n – (k – 1))

Составим из элементов a, b, с, d все размещения по три элемента. В первой строке запишем все размещения, которые начинаются с элемента a, во второй – с элемента b, в третьей – с элемента c, в четвертой – с элемента d.

Получим такую таблицу:

abc, abd, acb, acd, adb, adc,

bac, bad, bca, bcd, bda, bdc,

cab, cad, cba, cbd, cda, bdc,

dab, dac, dba, dbc, dca, dcb.

Из составленной таблицы видно, что =24.

Число размещений из четырех элементов по три можно найти, не выписывая самих размещений. Первый элемент можно выбрать четырьмя способами, так как им может быть один из четырех элементов. Для каждого выбранного первого элемента можно тремя способами выбрать второй элемент из трех оставшихся. Наконец, для каждых первых двух элементов можно двумя способами выбрать из двух оставшихся третий элемент. В результате получаем, что =4·3·2=24.

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

Любое расписание на один день, составленное из 4 различных предметов, отличается от другого либо предметами, либо порядком следования предметов. Значит, в этом примере идет речь о размещениях из 8 элементов по 4. Имеем, = 8·7·6·5 = 1684.

Расписание можно составить 1680 способами.

Задачи:

1.  Из 30 студентов класса надо выбрать хозяйку класса, старосту и физорга. Сколькими способами это можно сделать?

2.  Сколько букв русского алфавита можно закодировать, используя лишь комбинации точек и тире, содержащие только три знака?

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

4.  В классе 30 человек. Сколькими способами могут быть выбраны из них староста и казначей?

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

6.  Сколькими способами можно обозначить вершины треугольника, используя буквы А, В,С, D,E и F?

7.  Для запирания автоматической камеры применяется секретный замок, который открывается лишь тогда, когда набрано «тайное слово». Это слово набирают с помощью пяти дисков, на каждом из которых изображено 12 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова и подбирающего его наудачу?

8.  Сколько различных четырехзначных чисел можно составить из цифр 2, 6, 7, 8 и 9, если каждая цифра может входить в комбинацию несколько раз?

9.  На референдуме предложены четыре вопроса, на которые надо ответить «да» или «нет». Сколько есть возможностей заполнения бюллетеня (на все вопросы надо дать ответ)?

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

11.  У Лены есть восемь красок. Она хочет написать ими слова «Новый Год». Сколькими способами она может это сделать, если собирается каждую букву раскрашивать одним цветом?

12.  Сколькими различными способами можно распределить между шестью лицами две различные путевки в санаторий?

13.  Из 20 учащихся надо выбрать старосту, его заместителя и редактора газеты. Сколькими способами это можно сделать?

14.  В классе изучаются 7 предметов. В среду 4 урока, причем все разные. Сколькими способами можно составить расписание на среду?

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

16.  Из десяти различных книг выбирают четыре для посылки. Сколькими способами это можно сделать?

17.  Для запирания сейфа на диск нанесены 12 букв, а секретное слово состоит из 5 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова?

18.  Из 30 студентов класса надо выбрать хозяйку класса, старосту и физорга. Сколькими способами это можно сделать?

19.  В конкурсе песен «Галерея звезд» участвуют 15 человек. Сколькими способами могут распределиться между ними места?

20.  Сколько трехзначных чисел можно составить из цифр 5, 6, 8, 7, 1?