Математика 9 класс 9-М-7

§1. Правило произведения

Решение многих комбинаторных задач основывается на двух фундаментальных правилах, которые называются правилом произведения и правилом суммы. В этом параграфе мы познакомимся с первым из них. Однако проведём небольшой мысленный эксперимент.

Представьте себя на месте учителя начальной школы, который только что рассказал своим ученикам, что такое умножение. Дальше, возможно, ученики спросят, почему так получается, что, например, взять семь раз по девять будет то же самое что девять раз по семь (т. е. как бы мы не переставляли множители, произведение не поменяется)?

Эту проблему можно объяснить несколькими способами; опишем один из способов, который заведомо является неверным. Так, неверно будет дать ученику заучить правило «при перестановке мест множителей произведение не меняется», не объяснив, почему это правило работает – после этого, возможно, ученик будет относиться к математике как к гуманитарной науке, где нужно учить, а не понимать. Более верным будет поступить так: нарисовать прямоугольник `7xx9` и посчитать количество его клеток сначала по горизонталям, потом по вертикалям.

Теперь рассмотрим квадрат, например, `5xx5` и вычеркнем из него все клетки на диагонали «слева-сверху – вправо-вниз». Посчитаем количество не зачёркнутых клеток. С одной стороны – это `25-5`: всего было `25` клеток, `5` зачеркнули, `20` клеток осталось. Но то же самое можно посчитать как `5xx4` – в каждой строке не зачёркнутыми остались `4` клетки. Если складывать 5 раз по 4, как раз и получится умножение. Неважно, что не зачёркнутые клетки стоят в разных столбцах (в зависимости от строки) – важно лишь то, что в каждой строке их одинаковое количество, по четыре, иначе бы мы не смогли превратить сумму в произведение.

Сформулируем правило произведения для двух объектов.

Правило произведения

Если объект a1a_1 можно выбрать n1n_1 способами, и после каждого такого выбора объект a2a_2 можно выбрать n2n_2 способами, то выбор упорядоченной пары $$(a_1,\: a_2)$$ можно осуществить n1n2n_1n_2 способами.

Вернёмся к квадрату с зачеркнутыми клетками и разберём правило произведения по словам на этом примере.

`1` `2` `3` `4` `5`
`"X"` `1`
`"X"` `2`
`"X"` `3`
`"X"` `4`
`"X"` `5`


Пусть объект a1a_1 – это номер строки. Его можно выбрать 5-ю способами. Объект a2a_2 будет номером столбца. Фраза «после каждого такого выбора объект a2a_2 можно выбрать n2n_2 способами» означает, что после того, как мы выбрали строку, столбец можно выбрать одним и тем же количеством способов. То есть в нашем случае – что в каждом столбце не зачеркнуто одно и то же количество клеток. Это – важное и необходимое условие. Иначе – сумма нескольких одинаковых слагаемых не свернётся в произведение, а так и останется суммой нескольких разных слагаемых (в этом случае придётся пользоваться правилом суммы, см. §4).

Итак, «объект a1a_1 (номер строки) можно выбрать n1=5n_1 = 5 способами, и после каждого такого выбора объект a2a_2 (номер столбца) можно выбрать n2=4n_2 = 4 способами». Согласно правилу произведения, «выбор упорядоченной пары $$(a_1,\: a_2)$$ можно осуществить n1n2=20n_1n_2 = 20 способами». Пара чисел $$(a_1,\: a_2)=$$  (номер строки, номер столбца) будет являться координатами клетки, которая не будет зачеркнута, таким образом, мы посчитали количество не зачеркнутых клеток. Отдельно выделим слово «упорядоченной» в правиле произведения. В паре $$(a_1,\: a_2)$$ важно, что первым идёт номер строки, вторым – номер столбца. Клетки, например (4,1) и (1,4) – это две совершенно разные клетки. Таким образом, понятие упорядоченности в правиле произведения важно, без этого данное правило применить не получится. Что делать в таких случаях – см. §3.

Пример 1

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

Решение

Выбрав ручку, фломастер к ней можно купить десятью способами. Так как ручек всего `3`, то количество способов купить ручку и фломастер равно `3xx10=30`. Это количество совпадает с площадью таблицы-прямоугольника `3xx10`, каждая строка которого соответствует фломастеру, столбец – ручке, а клетка – комбинации «фломастер-ручка».

ОТВЕТ

`30`.

Пример 2

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

Решение

Из двух выбранных учеников важно, кто из них является дежурным, а кто заместителем дежурного – если ученики поменяются ролями, это будет другой способ. Поэтому сначала выберем, например, дежурного, после этого выберем его заместителя. Дежурного (объект a1a_1) можно выбрать десятью способами. После каждого такого выбора остается `9` кандидатов[1], любой из которых может стать заместителем дежурного (объект a2a_2). По правилу произведения общее количество способов выбрать пару (дежурного и заместителя) равно `9xx10 = 90`.

ОТВЕТ

`90`.

Пример 3

Сколькими способами можно поставить на шахматную доску белую и чёрную ладьи, чтобы они не «били» друг друга?

Решение

Выбор объекта a1a_1 – поля для белой ладьи – может быть сделан 64-мя способами. Независимо от этого выбора белая ладья «бьёт» `15` полей, поэтому для чёрной ладьи $$(a_2)$$ остаётся `64−15=49` возможных полей. По правилу произведения общее количество способов поставить белую и чёрную ладьи равно `64xx49=3136`.

ОТВЕТ

`3136`.

Теперь, сформулируем правило произведения для нескольких объектов.

Правило произведения

Если объект a1a_1 можно выбрать n1n_1 способами и после каждого выбора объекта a1a_1 объект a2a_2 можно выбрать n2n_2 способами и т. д., после каждого выбора объектов a1,a2,,ap1a_1,\: a_2,\: … ,\: a_{p−1} объект apa_p можно выбрать npn_p способами, то выбор совокупности объектов $$(a_1,\: a_2,\: … \: a_p)$$ именно в таком порядке можно осуществить n1n2npn_1n_2 … n_p способами.

Правило произведения для нескольких объектов можно получить из правила произведения для двух объектов, применяя метод математической индукции[2].


Пример 4

Сколькими способами можно разыграть среди `20` спортсменов золотую, серебряную и бронзовую медали?

Решение

Выбрать золотого медалиста (объект a1a_1) можно 20-ю способами. После этого выбрать серебряного медалиста (объект a2a_2) среди оставшихся участников можно 19-ю способами. После розыгрыша золотой и серебряной медали выбрать бронзового медалиста (объект a3a_3) можно 18-ю способами. Из правила произведения получаем, что количество способов разыграть между спортсменами золотую, серебряную и бронзовую медали равно `20xx19xx18 = 6840`.

ОТВЕТ

`6840`.

[1] Множество оставшихся после исключения дежурного учеников зависит от выбранного дежурного. Но количество оставшихся учеников всегда равно `9`, и правило произведения справедливо.

[2] Метод математической индукции описан в задании 5 для 9-х классов «Элементы логики. Элементы теории множеств» или в [2].