Методика обучения решению комбинаторных задач

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. значит, искомое число трехзначных чисел равно .

Из данных цифр можно составить 180 трехзначных чисел (без повторения цифр).

Упражнения

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

55. Из 30 участников собрания надо выбрать председателя и секретаря. Сколькими способами это можно сделать?

56. Сколькими способами могут занять первое, второе и третье места 8 участниц финального забега на дистанцию 100 м?

57. На станции 7 запасных путей. Сколькими способами можно расставить на них 4 поезда?

58. Сколькими способами можно изготовить трехцветный флаг с горизонтальными полосами, если имеется материал 7 различных цветов?

59. На соревнования по легкой атлетике приехала команда из 12 спортсменок. Сколькими способами тренер может определить, кто из них побежит в эстафете 4?100 м на первом, втором, третьем и четвертом этапах?

Решение. В этом задании идет речь о размещениях из 12 элементов по 4. Таким образом, искомое число выбора спортсменок равно = 12·11·10·9 = 11880 способов.

60. Сколькими способами могут быть распределены первая, вторая и третья премии между 15 участниками конкурса?

61. Сколькими способами 6 студентов, сдающих экзамен, могут занять места в аудитории, в которой стоит 20 одноместных столов?

62. На странице альбома 6 свободных мест для фотографий. Сколькими способами можно вложить в свободные места:

а) 2 фотографии; б) 4 фотографии; в) 6 фотографий?

63. На плоскости отметили 5 точек. Их надо обозначить латинскими буквами. Сколькими способами это можно сделать (в латинском алфавите 26 букв)?

64. Сколько четырехзначных чисел, в которых нет одинаковых цифр, можно составить из цифр:

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

65. Из трехзначных чисел, записанных с помощью цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 (без повторения цифр), сколько таких, в которых:

а) не встречаются цифры 6 и 7;

б) цифра 8 является последней?

66. Сколько существует семизначных телефонных номеров, в каждом из которых все цифры различные и первая цифра отлична от нуля?

Решение. В этом задании идет речь о размещениях из 10 элементов по 7, т.е. . Но первая цифра номера должна отличаться от нуля, т.е. размещение из 9 элементов по 6.

Так как из всех размещений надо исключить те, которые начинаются с цифры 0, то имеем: = 10·9·8·7·6·5·4 - 9·8·7·6·5·4 = 604800 - 60480 = 544320.

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

а) четными; б) кратными 5?

4. Сочетания

Пусть имеется пять гвоздик разного цвета. Обозначим их буквами a, b, c, d, е. требуется составить букет из трех гвоздик. Выясним, какие букеты могут быть составлены.

Если в букет входит гвоздика а, то можно составить такие букеты:

abc, abd, abe, acd, ace, ade

Если в букет не входит гвоздика а, но входит гвоздика b, то можно получить такие букеты:

bcd, bce, bde.

Наконец, если в букет не входит ни гвоздика а, ни гвоздика b, то возможен только один вариант составления букета: cde.

Мы указали все возможные способы составления букетов, в которых по-разному сочетаются три гвоздики из данных пяти. Говорят, что мы составили все возможные сочетания из пяти элементов по три.

Сочетанием из п элементов по k (0<k<n) называется любое множество, составленное из k элементов, выбранных из данных п элементов.

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

В отличие от размещений в сочетаниях не имеет значения, в каком порядке указаны элементы. Два сочетания из n элементов по k отличаются друг от друга хотя бы одним элементом.

В рассмотренном примере, составив все сочетания из 5 элементов по 3, мы нашли, что

Выведем формулу числа сочетаний из п элементов по k, где k?n. Для этого сначала выясним, как выражается через и .

Мы нашли, что из пяти элементов a, b, c, d, e можно составить следующие сочетания по трем элементам:

abc, abd, abe, acd, ace, ade, bed, bec, bde, cde.

В каждом сочетании выполним все перестановки. Число таких перестановок равно Р₃. В результате получим все возможные комбинации из 5 элементов по 5, которые отличаются либо самими элементами, либо порядком элементов, т.е. все размещения из 5 элементов по 3. всего мы получим размещений.

Значит, . Отсюда .

Аналогично будем рассуждать и в общем случае. Допустим, сто имеется множество, содержащее n элементов, и из его элементов составлены все возможные сочетания по k элементов. Число таких сочетаний равно . В каждом сочетании можно выполнить P_k перестановок. В результате мы получим все размещения, которые можно составить из n элементов по k. Их число равно .

Значит, . Отсюда, .

Мы получили формулу: .

Формулу числа сочетаний можно записать в другом виде. Умножим числитель и знаменатель дроби на (n - k)!, где n k. Получим:

Очевидно, что в числителе дроби записано произведение всех натуральных чисел от n до 1, взятых в порядке убывания, т.е. числитель дроби равен п!.

Получаем формулу: .

Заметим, что эту формулу можно использовать и в случае, когда n=k, если принять по определению, что 0!=1.

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

Каждый выбор отличается от другого хотя бы одним дежурным. Значит, здесь речь идет о сочетаниях из 15 элементов по 3:

.

Следовательно, трех дежурных можно выбрать 455 способами.

Пример 2. Из вазы с фруктами, в которой лежит 9 яблок и 6 груш, надо выбрать 3 яблока и 2 груши. Сколькими способами можно сделать такой выбор?

Выбрать 3 яблока из 9 можно способами, а выбрать 2 груши из 6 можно способами. Так как при каждом выборе яблок груши можно выбрать способами, то сделать выбор фруктов, о котором говорится в задаче, можно способами.

Значит, указанный выбор фруктов можно сделать 1260 способами.

Упражнения

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

69. В магазине «Филателия» продается 8 различных наборов марок, посвященных спортивной тематике. Сколькими способами можно выбрать из них 3 набора?

Решение. Искомое число способа выбора трех наборов равно .

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

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

72. Сколькими способами можно выбрать 49 предметов из 50

73. Сколькими способами можно отобрать стартовую шестерку в волейбольном матче, если в команде заявлено 10 игроков?

74. Из лаборатории, в которой работают заведующий и 10 сотрудников, надо отправить 5 человек в командировку. Сколькими способами это можно сделать, если:

а) заведующий лабораторией должен ехать в командировку;

б) заведующий лабораторией должен остаться?

75. На полке стоит 12 книг: англо-русский словарь и 11 художественных произведений на английском языке. Сколькими способами читатель может выбрать 3 книги, если:

а) словарь нужен ему обязательно; б) словарь ему не нужен?

Решение. а) Так как выбор англо-русского словаря уже сделан, то оставшиеся 2 книги из 11 можно выбрать способами. Следовательно, .

Значит, выбор можно сделать 55 способами.

б) В этом случае надо выбрать 3 книги из 11. это можно сделать способами. Находим, что .

Выбор можно сделать 165 способами.

Ответ: а) 55 способов;

б) 165 способов.

76. В классе учатся 16 мальчиков и 12 девочек. Для уборки территории требуется выделить 4 мальчиков и 3 девочек. Сколькими способами это можно сделать?

Решение. Четырех мальчиков из 16 можно выделить способами, а трех девочек из 12 можно выделить способами. Каждому выбору четырех мальчиков соответствует возможностей выбора трех девочек. Значит, указанный выбор дежурных можно сделать способами.

.

Значит, выбор дежурных можно сделать 400400 способами.

Ответ: 400400 способов.

В задачах 54-60 рассматриваются различные комбинации элементов (перестановки, размещения, сочетания).

77. Сколько среди всех перестановок букв слова «высота» таких, которые:

а) начинаются с буквы в;

б) начинаются с буквы а, а оканчиваются буквой т?

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

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

а) Иванов и Петров должны пойти в наряд;

б) Иванов и петров должны остаться;

в) Иванов должен пойти, а Петров - остаться?

80. В шахматном кружке занимаются 16 человек. Сколькими способами тренер может выбрать из них для предстоящего турнира:

а) команду из четырех человек;

б) команду из четырех человек, указав при этом, кто из членов команды будет играть на первой, второй, третьей и четвертой досках?

81. Для ремонта школы прибыла бригада, состоящая из 12 человек. Трех из них надо отправить на четвертый этаж, а четырех на пятый. Сколькими способами это можно сделать?

82. Номер машины в некотором городе состоит из двух различных букв, взятых из набора М, Н, К, Т, С, и трех различных цифр. Сколько машин можно обеспечить такими номерами?

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

Дополнительные упражнения

84. Сколько существует четырехзначных чисел, кратных 10, если цифры в числах могут повторяться?

85. Пешеход должен пройти один квартал на север и три квартала на запад. Выпишите все возможные маршруты пешехода.

86. Выпишите все пятизначные числа, записанные тремя четверками и двумя единицами.

87. Из цифр 1, 2, 3, 5 составили все возможные четырехзначные числа (без повторения цифр). Сколько среди них таких цифр, которые больше 2000, но меньше 5000?

88. Сколько четных четырехзначных чисел, в которых цифры не повторяются, можно записать с помощью цифр:

а) 1, 2, 3, 7; б) 1, 2, 3, 4?

89. Делится ли число 50! на:

а) 100; б) 305; в) 1550?

90. Найдите наименьшее значение п, при котором число п! оканчивается:

а) одним нулем; б) двумя нулями; в) тремя нулями.

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

а) кратны 2; б) кратны 3?

92. Сократите дробь:

а) ; б) ; в)

93. Решите уравнение:

а) ; б) .

94. Сколькими способами из класса, где учатся 24 учащихся, можно выбрать:

а) двух дежурных; б) старосту и помощника старосты?

95. У Антона шесть друзей. Он может пригласить в гости одного или нескольких из них. Определите общее число возможных вариантов.

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

97. Сколькими способами четыре пассажира: Алексеев, Смирнов, Федоров и Харитонов - могут разместиться в девяти вагонах поезда, если:

а) все они хотят ехать в разных вагонах;

б) Алексеев и Смирнов хотят ехать в одном вагоне, а Смирнов и Харитонов в других вагонах, причем различных?

98. В 9 «А» классе учатся 25 учащихся, в 9 «Б» - 20 учащихся, а в 9 «В» - 18 учащихся. Для работы на пришкольном участке надо выделить трех учащихся из 9 «А», двух - из 9 «Б» и одного - из 9 «В». Сколько существует способов выбора учащихся для работы на пришкольном участке?

99. Из группы туристов требуется выбрать дежурного и его помощника. Если туристов было бы на одного больше, то возможностей выбора было бы в 1,25 раза больше. Сколько туристов в группе?

100. Сколькими способами группу из 12 человек можно разбить на две группы:

а) по 4 и 8 человек; б) по 5 и 7 человек?

101. В отделе работают 5 ведущих и 8 старших научных сотрудников. В командировку надо послать двух ведущих и трех старших научных сотрудников. Сколькими способами может быть сделан выбор сотрудников, которых надо послать в командировку?

102. Из цифр 1, 2, 3, 4, 5 составили все возможные трехзначные числа (с повторением цифр) сколько среди них таких, сумма цифр которых равна:

а) 3; б) 4; в) 6?

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

а) 6; б) 9?

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

а) ; б) ; в) .

105. Сколько надо взять элементов, чтобы число размещений из них по 4 было в 12 раз больше, чем число размещений из них по 2?

106. Число размещений из п элементов по 4 в 14 раз больше числа размещений из п - 2 элементов по 3. Найдите п.

107. Решите уравнение:

а)

б)

в)

г)

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

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

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

111. Сколько всевозможных трехзначных чисел можно составить из цифр 1, 2, 3 и 4 так, чтобы цифры в записи числа не повторялись? Изменится ли решение этой задачи, если вместо цифры 4 будет дана цифра 0?

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

113. Сколько пятизначных чисел, первые (слева) три цифры которых 2, 3 и 4, можно составить из цифр 1, 2, 3, 4 и 5? Изменится ли ответ этой задачи, если цифры числа не будут повторяться?

114. Из цифр 0, 1, 2, 3,4 составляют всевозможные пятизначные числа, причем так, что в записи данного числа содержатся все данные цифры. Сколько можно составить таких чисел? Чему будет равна разность между наименьшим и наибольшим из полученных чисел?

115. Сколько натуральных чисел, меньших 1000, можно записать, используя цифры 7, 4 и 5? Сколько среди них четных? Нечетных? Кратных 5?

Размещения и сочетания

116. Покажите, что в нижеприведенных задачах рассматриваются размещения из n элементов по k; определите значения n и k и найдите число размещений:

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

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

в) В соревновании участвуют 10 человек. Сколькими способами могут распределиться между ними места?

г) Сколько всевозможных трехзначных чисел можно записать, используя цифры 3, 4, 5 и 6?

117. Покажите, что в нижеприведенных задачах рассматриваются сочетания из n элементов по k; определите значения n и k и найдите число для каждой задачи:

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

б) Сколькими способами можно выбрать 4 краски из 10 различных красок?

118. Два человека обменялись своими фотокарточками. Сколько было фотокарточек?

119. Два человека пожали друг другу руки. Сколько было рукопожатий? А если 15 человек пожали друг другу руки, то, сколько будет рукопожатий?

120. Сколькими способами можно расставить на полке 3 различные книги?

121. 15 человек сыграли друг с другом по одной партии в шахматы по одной партии. Сколько было сыграно партий?

122. На плоскости отметили 7 точек. Каждые две точки соединили отрезком. Сколько получилось отрезков?

123. Решите следующие задачи, используя формулы. Ответ проверьте с помощью перебора всех возможных вариантов:

а) Сколько словарей необходимо переводчику, чтобы он мог переводить непосредственно с любого из четырех языков - русского, английского, немецкого и французского на любой другой из этих языков?

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

в) Мальчик выбрал в библиотеке 5 книг. По правилам библиотеки одновременно можно взять только две книги. Сколько у мальчика вариантов выбора двух книг из пяти?

г) четыре друга собрались на футбольный матч. Но им удалось купить только три билета. Из скольких вариантов им надо выбрать тройку счастливцев? Как осуществить выбор, чтобы у всех ребят были равные шансы попасть на матч?

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

е) Задача Леонарда Эйлера. Трое господ при входе в ресторан отдали швейцару свои шляпы, а при выходе получили их обратно. Сколько существуют вариантов, при которых каждый из них получит чужую шляпу?

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

124. Аня, Боря, Вера и Гена - лучшие лыжники школы. На соревнования надо выбрать троих из них. Сколькими способами это можно сделать?

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

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

127. На прямой взяли 4 точки. Сколько всего получилось отрезков, концами которых являются эти точки?

128. За свои рисунки ученик получил две положительные отметки. Какими они могут быть?

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

Приложение 2

Таблица 1. Виды событий:

1	Равновозможные
2	Маловероятные
3	Более вероятные
4	Достоверные
5	Невозможные

Таблица 2. Варианты падения спичечного коробка:

Плашмя	На ребро	На попa

2

Таблица 3. Варианты падения монеты:

ОРЕЛ	РЕШКА

2

2

Таблица 5. Результаты эксперимента:

коробок	монета	игральный кубик
плашмя	на ребро	на попа	орел	решка	1	2	3	4	5	6

Приложение 3.

Рисунок 1. Древо составления трехзначных чисел из цифр 1, 2, 3 без повторения.

1	2	3
2	3	1	3	1	2
3	2	3	1	2	1

Рисунок 2.

2

Приложение 4

Диаграмма 1. Сравнение показателей гибкости мышления.

Диаграмма 2. Сравнение показателей развития логической памяти.

Диаграмма 3. Сравнение показателей выбора и решения учащимися задач.