Методика обучения решению комбинаторных задач (стр. 12 из 15)

Упражнения

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

32. Курьер должен разнести пакеты в 7 различных учреждений. Сколько маршрутов он может выбрать?

33. Сколькими способами 9 человек могут встать в очередь в театральную кассу?

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

35. Сколько есть способов раздать спортивные номера с 1 по 5 пяти хоккеистам?

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

37. Ольга помнит, что телефон подруги оканчивается цифрами 5, 6, 7, но забыла в каком порядке эти цифры следуют. Укажите наибольшее число вариантов, которые ей придется перебрать, чтобы дозвониться подруге.

38. Сколько шестизначных чисел (без повторения цифр) можно составить из цифр:

а) 1, 2, 5, 6, 7, 8; б) 0, 2, 5, 6, 7, 8?

39. Сколько среди четырехзначных чисел (без повторения цифр), составленных из цифр 3, 5, 7, 9, таких, которые:

а) начинаются с цифры 3; б) кратны 15?

40. Найдите сумму цифр всех четырехзначных чисел, которые можно составить из цифр 1, 3, 5, 7 (без их повторения).

41. Сколько чисел (без повторения цифр) можно составить из цифр 1, 2, 3, 4, таких которые:

а) больше 3000; б) больше 2000?

42. Семь мальчиков, в число которых входят Олег и Игорь, становятся в ряд. Найдите число возможных комбинаций, если:

а) Олег должен находиться в конце ряда;

б) Олег должен находиться в начале ряда, а Игорь – в конце;

в) Олег и Игорь должны стоять рядом.

Решение. а) так как место Олега фиксировано, то число комбинаций зависит от расположения остальных шести мальчиков. Значит число комбинаций равно Р6=6!=1·2·3·4·5·6=720.

б) Так как места Олега и Игоря фиксированы, то число комбинаций зависит от расположения пяти остальных мальчиков, т.е. равно Р5=5!=1·2·3·4·5=120.

в) Будем рассматривать пару Олег-Игорь как один элемент. Расположение этой пары и пяти остальных мальчиков может быть выполнено Р6=6! способами. В каждой из этих комбинаций Олег и Игорь могут располагаться Р2=2! Способами. Значит искомое число способов расположения мальчиков равно Р6·Р2=6! ·2!=720·2=1440.

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

44. Сколько существует перестановок букв слова «конус», в которых буквы к, о, н стоят рядом?

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

46. Сколькими способами 5 мальчиков и 5 девочек могут занять в театре в одном ряду места с 1 по 10? Сколькими способами они могут это сделать, если мальчики будут сидеть на нечетных местах, а девочки – на четных?

Решение. Если мальчики и девочки сядут в один ряд в произвольном порядке, то это можно сделать Р10=10!=3628800 способами. Если мальчики сядут на нечетные места, то существуют Р5 способов их расположения. Столькими же способами могут расположиться девочки на четных местах. Каждому способу расположения мальчиков соответствует Р5 способов расположения девочек. Значит, расположиться так, что мальчики будут сидеть на нечетных местах, а девочки – на четных, можно Р5·Р5=5! ·5!=120·120=14400 способами.

47. Делится ли число 30! на:

а) 90; б) 92; в)94; г) 96?

Решение. а) 90=2·5·9. Среди множителей числа 30! есть числа 2, 5 и 9. значит, число 30! делится на 90.

б) 92=4∙23. Среди множителей 30! есть числа 4, 23. Значит, число 30! делится на 92.

в) 94=2·47. Число 47 простое и больше, чем 30. Так как среди множителей числа 30! нет числа 47, то число 30! не делится на 94.

г) 96=2·3·16. Среди множителей 30! есть числа 2, 3, 16. Значит, число 30! делится на 96.

48. Делится ли число 14! на:

а) 168; б) 136; в) 147; г) 132?

49. Найдите значение выражения:

а) б) в) г)

Решение: а) б)

в) г)

50. Вычислите значение дроби:

а) ; б) ; в) ; г) ; д) ; е)

51. Выпишите все натуральные делители числа:

а) 4!; б) 5!; в)6!

52. Докажите, что если n<m, то m! делится на n! без остатка.

53. Что больше и во сколько раз:

а) 6!∙5 или 5! ∙6 б) (п+1)! ∙п или п! ∙(п+1)

3. Размещения

Пусть имеется 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 считаются различными, если они отличаются самими элементами или порядком их расположения.

Составим из элементов 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.

Приведенный способ рассуждений используем для вывода формулы числа размещений из n элементов по k, где n≤ k.

Первый элемент можно выбрать n способами. Так как после этого остается n-1 элементов, то для каждого выбора первого элемента можно n-1 способами выбрать второй элемент. Далее, для каждого выбора первых двух элементов можно n-2 способами выбрать третий элемент (из n-2 оставшихся). Наконец, для каждого выбора первых k-1 элементов можно n – (k – 1) способами выбрать k-й элемент (из n – (k -1) оставшихся).

Значит,

=n(n – 1)(n – 2)∙…∙(n – (k – 1))

Мы получили формулу для вычисления числа размещений из п элементов по k.

Например, число размещений из шестнадцати элементов по пять равно произведению пяти множителей, первый из которых – число 16, а каждый следующий на 1 меньше предыдущего, т.е.

= 16·15·14·13·12=524160.

В пособии приводятся примеры применения формулы числа размещений.

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

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

= 8·7·6·5 = 1684.

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

Пример 2. Сколько трехзначных чисел (без повторения цифр) можно составить из цифр 0, 1, 2, 3, 4, 5, 6?

Если среди семи цифр нет нуля, то трехзначных чисел (без повторения), которые можно составить из этих цифр, равно числу размещений из 7 элементов по 3. однако среди данных цифр есть цифра 0, с которой не может начинаться трехзначное число. Поэтому из размещений из 7 элементов по 3 надо исключить те элементы, у которых первой цифрой является 0. их число равно числу размещений из 6 элементов по 2. значит, искомое число трехзначных чисел равно

.