Примеры задач с решениями

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

а) сколькими способами можно расселить группу специалистов, если в гостинице 8 свободных одноместных номеров, а в группе 5 человек?

б) сколькими способами можно распределить 4 свободных одноместных номера между специалистами группы, включающей 7 человек?

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

a) Ответом на первый вопрос будет являться количество различных кортежей (упорядоченных списков) одноместных номеров, предоставляемых для проживания (размещения) прибывших специалистов.

При этом длина k любого из кортежей совпадает с числом специалистов, т.е. k = 5, а сами кортежи составляются (формируются) из предметов n- элементного множества, роль которого в данном случае выполняет список свободных одноместных номеров, т.е. n = 8.

Используя формулу (3.1), получаем искомое число различных способов расселения (размещения) группы специалистов

.

б) Ответом на второй вопрос будет являться количество различных кортежей (упорядоченных списков) специалистов, которым могут быть предоставлены одноместные номера. При этом длина k любого из кортежей равна числу свободных номеров, т.е. k = 5, а сами кортежи составляются (формируются) из предметов n -элементного множества, роль которого в данном случае выполняет список группы специалистов, т.е. n = 7.

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

.

Пример 3.2. По завершении семестра каждый студент, входящий в определенную группу, должен защитить 1 курсовую работу и сдать 3 зачета и 4 экзамена по 7 предметам. Сколько различных результатов (наборов оценок) может получить группа студентов, если они допускаются к экзаменам при любых оценках за зачеты и курсовую работу?

Чтобы ответить на вопрос, заметим, что искомое число различных наборов оценок для группы студентов и для одного студента будет одинаковым. В данном случае мы имеем дело с составлением всевозможных комбинаций оценок, содержащихся в двух алфавитах A = { 2,3,4,5 } и B = { зачет, незачет }.

Из алфавита A выбираются (выставляются) оценки за экзамены и курсовую работу, а из алфавита B – оценки за зачет. При этом наборы (кортежи) оценок, выбираемых из алфавита A, могут, очевидно, включать в себя одинаковые элементы (буквы), так как оценки за разные экзамены (в том числе и за курсовую работу) могут совпадать.

Более того, так как длина любого кортежа равна 5 (в него входят 4 оценки за экзамены и 1 оценка за курсовую работу), а мощность алфавита | A | = 4, то в кортеже, по крайней мере, два элемента будут совпадать. То же самое можно сказать и о наборах (кортежах) оценок за сдачу трех зачетов.

Таким образом, решение задачи сводится к определению числа размещений с повторениями (нахождению мощностей декартовых степеней). В частности, используя формулу (3.2), вычислим количество различных наборов оценок:

- за сдачу зачетов

- за курсовую работу и экзамены .

Так как по условиям задачи оценки за экзамены и курсовую работу никак не зависят от результатов сдачи зачетов, и наоборот (на самом деле студент, не сдавший зачеты или не защитивший курсовую работу, как правило, не допускается к экзаменам), то искомое общее число возможных результатов (наборов оценок) за все предметы и курсовую работу будет (по правилу умножения) равно

Пример 3.3. Сколькими различными способами можно расположить на традиционной (64-клеточной) шахматной доске 8 ладей так, чтобы они не могли бить друг друга?

Любой, кто имеет хоть какое-то представление об игре в шахматы, знает – ладьи могут бить друг друга, если они находятся либо на одной горизонтали, либо на одной вертикали шахматной доски (по форме доска является квадратной и имеет 8 строк-горизонталей и 8 столбцов-вертикалей, которые обозначаются десятичными цифрами и латинскими буквами).

Одно из правильных (удовлетворяющих условиям задачи) расположений ладей можно формально записать в виде списка бинарных кортежей

(d8, a7, h6, e5, b4, g3, c2, f1),

элементы (буква и цифра) каждого из которых соответствуют порядковым номерам вертикали и горизонтали шахматной доски, на пересечении которых находится одна из восьми ладей. Этот способ (вариант) расположения представлен ниже в таблице, иллюстрирующей шахматную доску.

			Д
Д
							Д
				Д
	Д
						Д
		Д
					Д
a	b	c	d	e	f	g	h

Для получения нужного результата будем последовательно (построчно) размещать ладьи:

первую ладью поместим на любую, произвольным образом выбранную позицию 1 горизонтали доски – число вариантов (способов) такого выбора будет, очевидно, совпадать с количеством вертикалей доски, т.е. равно 8;

так как позиции ладей, обозначаемые в таблице буквами латинского алфавита, на разных горизонталях не должны совпадать (иначе ладьи окажутся на одной вертикали), то для размещения следующей ладьи на 2 горизонтали число возможных (альтернативных) позиций уменьшится на единицу и будет равно 7;

по аналогии число возможных позиций (пока свободных от ладей вертикалей) для размещения очередной ладьи на 3 горизонтали будет равно 6, на 4 горизонтали – 5, …, на 7 – 2;

наконец, на 8 горизонтали для установки последней ладьи альтернативность отсутствует, так как свободна только 1 позиция строки (все остальные уже заняты другими ладьями).

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

Np = 8! = 8∙7∙6∙5∙4∙3∙2∙1 = 40320.

Полученный результат несложно распространить и на более общую (по сравнению с разобранной) комбинаторную ситуацию, когда число строк и столбцов шахматной доски равно произвольному натуральному числу n. Для данной ситуации число способов размещения (расположения) n ладей в клетках доски так, чтобы они не могли бить друг друга, соответствует перестановкам из n предметов и, следовательно, равно n!.

Так, например, иногда для игры используется 100-клеточная шахматная доска. В этом случае искомое число расположений 10 ладей в клетках шахматной доски будет, очевидно, равно 10!.

Комбинаторные ситуации, подобные рассмотренной, возникают и в других задачах. Это, в частности, относится к задаче линейной алгебры, связанной с полным разложением (развертыванием) определителя (детерминанта) квадратной матрицы An n -го порядка, т.е. с представлением определителя Dn = det An в виде формулы полного разложения, выражающей Dn через элементы матрицы An. В качестве простейших примеров таких формул могут служить выражения для определителей второго и трeтьего порядков

,

Как известно, в общем случае формула полного разложения может быть записана (что подтверждают приведенные выше ее частные случаи) в виде знакочередующейся суммы произведений, обладающих следующими свойствами:

все произведения имеют одинаковое число, но разный состав сомножителей, роль которых выполняют n элементов матрицы, расположенных на пересечениях разных строк и столбцов;

всякое произведение содержит (в качестве сомножителей) по одному элементу из каждой строки и по одному элементу из каждого столбца матрицы;

любые два сомножителя (элемента матрицы) не могут принадлежать одной и той же строке или одному и тому же столбцу.

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

Таким образом, два множества (произведений элементов и расположений ладей) в силу их взаимно однозначного соответствия являются эквивалентными.Следовательно, число различных произведений в формуле полного разложения определителя n- го порядка, совпадающее с числом возможных расположений ладей на шахматной доске размерности n, будет равно n!.

Пример 3.4. На волейбольной площадке 6 позиций. Перед игрой (каждой партией) тренер заявляет состав и расстановку игроков, т.е. указывает, на какой позиции каждый из 6 заявленных игроков начинает игру. В зависимости от амплуа (возлагаемых функций) шестерка игроков делится на 3 пары - 2 распасующих (разводящих), 2 основных и 2 вспомогательных нападающих. Сколькими способами тренер может расставить 6 игроков на площадке, если принять, что расстановки равноценны (не отличаются), если двух игроков одного амплуа поменять местами?

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

Np = 6! = 6∙5∙4∙3∙2∙1 = 720.

На самом деле, в соответствии с формулировкой задачи стартовая шестерка игроков разделена на три группы (класса) однотипных игроков - распасующие, основные и вспомогательные нападающие - и игроки каждой группы равноценны с точки зрения их игровых возможностей.

Следовательно, решение данной задачи сводится к нахождению числа перестановок с повторениями. Так как в каждую группу однотипных игроков входят два волейболиста с одинаковым амплуа, то применяя формулу (3.4), будем иметь

.

Пример 3.5. Сколькими способами из 90 пронумерованных бочонков лото можно отобрать 10 бочонков так, что среди 10 чисел (номеров) на бочонках:

a) ровно 3 меньше 41 и ровно 5 больше 50, причем среди этих пяти ровно 2 делятся на 6?

б) ровно 4 делятся на 8 и ровно 3 делятся на 9?

a) Исходя из анализа комбинаторной ситуации, соответствующей первому вопросу, разобьем все множество бочонков на 4 класса, каждый из которых содержит бочонки с уникальными свойствами, и разложим их в 4 урны, а именно:

в первую урну поместим 40 бочонков с номерами, меньшими 41;

во вторую урну - 7 бочонков, номера которых больше 50 и делятся без остатка на 6 (бочонки с числами 54, 60, 66, 72, 78, 84, 90);

в третью урну – 33 бочонка, номера которых больше 50 и не делятся на 6;

в четвертую (последнюю) урну - оставшиеся 10 бочонков, т.е. бочонки с номерами, попадающими в сегмент [ 41,50 ].

Отберем 10 бочонков, удовлетворяющих условиям задачи. Для этого извлечем произвольным образом (по схеме случайного выбора):

из первой урны - 3 бочонка; из второй урны - 2 бочонка;

из третьей урны - 3 бочонка; из четвертой урны - 2 недостающих бочонка.

Используя формулу (3.8), запишем выражение для искомого числа возможных способов извлечения (отбора) бочонков

.

б) В результате анализа комбинаторной ситуации получаем, что среди 90 номеров бочонков:

делятся только на 8 (кратны восьми) 10 номеров (8, 16, 24, 32, 40, 48, 56, 64, 80, 88);

делятся только на 9 (кратны девяти) 9 номеров (9, 18, 27, 36, 45, 54, 63, 81, 90);

делится и на 8 и на 9 один номер (72).

Разобьем 90 бочонков на четыре класса и разложим их в 4 урны, а именно:

в первую урну поместим 10 бочонков (номера делятся только на 8);

во вторую урну - 9 бочонков (номера делятся только на 9);

в третью урну - 1 бочонок с номером 72;

в четвертую урну - оставшиеся 70 бочонков.

Особенностью рассматриваемой комбинаторной ситуации является то, что извлечение (отбор) 10 бочонков из урн можно осуществить двумя альтернативными вариантами. Появление альтернативности обусловлено тем, что среди бочонков имеется один уникальный бочонок (с номером 72), принадлежащий сразу двум набираемым группам бочонков – его номер делится без остатка и на 8 и на 9.

Применительно к каждому из двух вариантов отбор 10 бочонков осуществляется следующим образом:

для первого варианта:

из первой урны извлекаем 3 бочонка; из второй урны - 2 бочонка;

из третьей урны - 1 бочонок; из четвертой урны - 4 недостающих бочонка;

для второго варианта:

из первой урны извлекаем 4 бочонка; из второй урны – 3 бочонка;

из третьей урны – 0 бочонков (из этой урны извлечение не происходит); из четвертой урны - 3 недостающих бочонка.

Применяя формулу (3.8) для каждого варианта и правило сложения, получаем выражение для искомого числа способов отбора 10 бочонков

,

в котором первое слагаемое соответствует первому варианту отбора, а второе - второму.

Пример 3.6. Чему равно количество всевозможных подмножеств n –элементного множества ?

Рассмотрим произвольное k –элементное подмножество (0 < k < n) множества . Ясно, что последовательность его элементов (предметов) представляет собой некоторую k –расстановку из элементов множества , обладающую определенными свойствами. Эти свойства (ввиду того, что - тоже множество) ничем не отличаются от известных свойств множеств. К ним относятся:

1) все элементы, составляющие k –расстановку (подмножество ), различны, т.е. относятся к предметам разных видов;

2) порядок элементов в k –расстановке может быть любым, так как множества с одинаковым составом элементов и различным порядком их расположения (следования) равны.

Из свойств вытекает - описанная k –расстановка относится к сочетаниям из n по k и, как следствие число различных k –элементных подмножеств множества будет равно . Учитывая предельные случаи подмножеств (исходное множество и пустое множество ) и применяя правило сложения, выражение для общего числа различных подмножеств можно записать в виде суммы N = .

В соответствии с формулой (3.10), вытекающей из связей сочетаний с биномом Ньютона, эта сумма, как и в примере 2.5, будет равна .

Пример 3.7. Рассмотрим еще один способ решения комбинаторной задачи, разобранной в примере 2.1. Необходимо было найти число различных путей, ведущих путника из пункта AК,М в пункт C0,0 в соответствии с изображенным в примере планом дорог.

Ясно, что, каким бы путем ни шел путник, он пройдет через одно и то же число N = K + M перекрестков, к каковым относятся все пункты, в которых приходится делать выбор направления движения - либо снизу вверх, либо слева направо (пример одного из таких путей для случая, когда K = 3, M = 6, N = 9, представлен на рисунке).

С 0,0

А 3,6

Сопоставим с последовательностью N перекрестков, однозначно представляющих конкретно выбранный путь (маршрут), двоичное слово (длиной N)

по правилам:

, если путник, проходя i -й перекресток (в порядке следования), выбирает направление движения снизу вверх;

в противном случае (если выбирается направление слева направо).

Так, например, изображенному на рисунке маршруту будет соответствовать двоичное слово E = 010010001. Очевидно, каждому пути из множества возможных будет соответствовать единственное двоичное слово, и наоборот: каждому слову - единственный путь, т.е. соответствие между множествами путей и двоичных слов взаимно однозначное.

Таким образом, исходная задача, связанная с выбором всевозможных путей, идентична задаче составления различных двоичных слов длиной N, каждое из которых содержит ровно K единиц (предметов первого типа) и ровно M нулей (предметов второго типа), т.е. является одной из множества перестановок из N предметов с повторениями.

Следовательно, число таких двоичных слов, а значит и искомое число путей будет удовлетворять формуле (3.4) и равно

.

В частности, применительно к исходным данным, использованным в задаче примера 2.1 (K = 3, M = 4), получаем

.

Учитывая формулу (3.12), связывающую число сочетаний и перестановок с повторениями, для расчета искомого числа различных путей можно использовать равенства

.

Пример 3.8. При игре в домино 4 игрока делят поровну 28 костяшек. Сколькими способами они могут это сделать?

Сформулированная задача относится к классу задач на раскладывание (распределение) предметов по ящикам. Роль предметов в данном случае выполняют костяшки домино, а роль ящиков - игроки.

Используя формулу (3.13), получим искомое число возможных способов

.