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

Пример 2.1. Поселок, план которого изображен на рисунке, имеет кварталов, разделенных (K-1) горизонтальными и (M-1) вертикальными улицами. Сколькими путями путник может попасть из пункта A в пункт C, если все время будет двигаться либо слева направо, либо снизу вверх ?

В0,М С 0,0

Е

А К,М F D K,0

Обозначим искомое множество путей через П [K,M] и разобьем его на два подмножества:

П [K,M-1] - пути, проходящие через пункт (перекресток) FK,M-1;

П [K-1,M] - пути, проходящие через перекресток EK-1,M.

Так как эти подмножества не пересекаются, т.е. они определяют разбиение искомого множества, то в соответствии с правилом суммы мощности всех трех множеств, которые обозначим соответственно через N [K,M], N [K,M-1], N [K-1,M] , будут связаны равенством

N [K,M] = N [K,M-1] + N [K-1,M].

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

N [k,m] = N [k,m-1] + N [k-1,m], (k = 1,2,...,K; m = 1,2,...,M).

Это равенство фактически представляет собой рекуррентное соотношение для нахождения искомого числа путей. Для того чтобы им воспользоваться при m = 1 (k = 1), необходимо знать величины N [k,0] (N [0,m]). Так как из любого перекрестка улицы BC (DC) в пункт C ведет только один путь, то указанные величины будут равны

N [k,0] = N [0,m] = 1, ( k = 1,2,...,K; m = 1,2,...,M ).

Проведем расчеты для K = 3, M = 4 ( результаты представлены ниже в таблице ).

1	1	1	1	0
5	4	3	2	1
15	10	6	3	1
35	20	10	4	1

0

1

2

3

4 3 2 1 0

N [0,0] = 0;

N [1,0] = N [2,0] = N [3,0] = N [0,1] = N [0,2] = N [0,3] = N [0,4] = 1;

N [1,1] = N [1,0] + N [0,1] = 2, N [1,2] = N [1,1] + N [0,2] = 3,

N [1,3] = N [1,2] + N [0,3] = 4, N [1,4] = N [1,3] + N [0,4] = 5,

N [2,1] = N [2,0] + N [1,1] = 3, N [2,2] = N [2,1] + N [1,2] = 6,

N [2,3] = N [2,2] + N [1,3] = 10, N [2,4] = N [2,3] + N [1,4] = 15,

N [3,1] = N [3,0] + N [2,1] = 4, N [3,2] = N [3,1] + N [2,2] = 10,

N [3,3] = N [3,2] + N [2,3] = 20,

N [3,4] = N [3,3] + N [2,4] = 35.

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

Пример 2.2. Упавшее дерево после первоначальной обработки (обрубка сучьев и не пригодных для использования частей основания (комля) и вершины) имеет длину 12 метров. Его необходимо распилить на 4 части, длина каждой из которых может быть равна либо 2, либо 3, либо 4 метрам. Сколькими способами это можно сделать, если порядок отпиливания важен (толщина дерева от основания к вершине уменьшается и поэтому отпиленные части могут использоваться для разных нужд) ?

Для решения задачи воспользуемся рекуррентным соотношением (2.3), предназначенным для разбиения натурального числа N на n слагаемых.

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

длина обработанного (подлежащего распиловке) дерева N = 12;

количество частей дерева n = 4 и множество (список) допустимых длин частей (слагаемых разбиения) K = { 2,3,4 };

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

N(1,0) = N(1,1) = 0, N(1,2) = N(1,3) = N(1,4) = 1, N(1,i) = 0 ( i = 5,6,7,…).

Руководствуясь определенным в п. 2.1 порядком действий, выполним следующие операции:

1. Запишем исходное соотношение (2.3) для рассматриваемой комбинаторной ситуации

f (n,N) = f (n-1,N-2) + f (n-1,N-3) + f (n-1,N-4) (n = 4, N = 12).

2. Применим это соотношение для искомой величины f (4,12) и ее составляющих (слагаемых правой части):

f (4,12) = f (3,10) + f (3,9) + f (3,8),

f (3,10) = f (2,8) + f (2,7) + f (2,6),

f (3,9) = f (2,7) + f (2,6) + f (2,5),

f (3,8) = f (2,6) + f (2,5) + f (2,4). 

• f (4,12) = [ f (2,8) + f (2,7) + f (2,6) ] +

+ [ f (2,7) + f (2,6) + f (2,5) ] +

+ [ f (2,6) + f (2,5) + f (2,4) ] =

= f (2,8) + 2 f (2,7) +3 f (2,6)] + 2 f (2,5) + f (2,4).

3. Выполним аналогичную операцию для неизвестных величин, содержащихся в правой части последнего равенства:

f (2,8) = f (1,6) + f (1,5) + f (1,4),

f (2,7) = f (1,5) + f (1,4) + f (1,3),

f (2,6) = f (1,4) + f (1,3) + f (1,2).

f (2,5) = f (1,3) + f (1,2).

f (2,4) = f (1,2).

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

f (2,4) = 1, f (2,5) = 2, f (2,6) = 3, f (2,7) = 2, f (2,8) = 1 

 f (4,12) = 1 + 4 + 9 + 4 + 1 = 19.

Таким образом, искомое количество способов распиловки дерева длиной 12 м на 4 определенные в задании части равно 19.

Пример 2.3. Дополним условия примера 2.1: будем считать, что путник не может (или не хочет) появляться на каком-то внутреннем перекрестке Gp,q. Требуется с учетом сформулированного ограничения ответить на вопрос: сколькими путями путник может попасть из пункта A в пункт C, минуя пункт G, если правила движения остаются прежними?

B 0,M C 0,0

			G (p,q)

A K,M D K,0

Один из способов решения задачи предполагает исключение из всего множества путей П [K,M] его собственного подмножества ПG путей, идущих через пункт (перекресток) G. Если обозначить искомое число путей через L [K,M] и мощность подмножества П через L , то в результате будем иметь L [K,M] = N [K,M] - L , где N [K,M] – общее число путей, ведущих из пункта А в пункт В (как и в примере 2.1).

Для нахождения L используем следующие соображения:

1) так как число путей , ведущих из пункта G в пункт C, не зависит от того, каким образом путник попал в пункт G, то в соответствии с правилом умножения , где - число путей из начального пункта A в пункт G;

2) величины , могут быть получены с помощью записанного в примере 2.1 рекуррентного соотношения, при этом первая из них будет совпадать с N [p,q], а вторая - с N [r,s], где r = K - p, s = M - q.

Проведем расчеты для K = 3, M = 4, p = 2, q = 2 (результаты представлены ниже в таблице).

		1	1	0
		3	2	1
1	1	0;6	3	1
3	2	1

0

1

2

3

4 3 2 1 0

N [1,1] = N [1,0] + N [0,1] = 2, N [1,2] = N [1,1] + N [0,2] = 3;

N [2,1] = N [2,0] + N [1,1] = 3, N [2,2] = N [2,1] + N [1,2] = 6;

N [p,q] = N [2,2]  = 6;

N [r,s] = N [1,2] = N [1,1] + N [0,2] = 3  = 3; , L [K,M] = L [3,4] = N [3,4] - = 35 – 18 = 17.

В таблице элемент с номерами (2,2) имеет два значения:

число 0 относится к случаю, когда пункт G является конечным (пути выхода отсутствуют) ;

число 6 определяет число путей из пункта G в пункт C (соответствует случаю, когда пункт G является начальным).

Второй способ предполагает проведение непосредственных расчетов с помощью общего рекуррентного соотношения (или на основе последовательного заполнения таблицы). Так как через перекресток G (p,q) путник не проходит, то число путей N [p,q] не вычисляется, а принимается равным нулю (на месте (p,q)-го элемента в таблице сразу же ставится нуль).

Проведем расчеты и заполним таблицу для рассмотренного выше варианта исходных данных.

N [1,1] = N [1,0] + N [0,1] = 2, N [1,2] = N [1,1] + N [0,2] = 3,

N [1,3] = N [1,2] + N [0,3] = 4, N [1,4] = N [1,3] + N [0,4] = 5,

N [2,1] = N [2,0] + N [1,1] = 3, N [2,2] = 0;

N [2,3] = N [1,3] + N [2,2] = 4, N [2,4] = N [2,3] + N [1,4] = 9,

N [3,1] = N [3,0] + N [2,1] = 4, N [3,2] = N [3,1] + N [2,2] = 4;

N [3,3] = N [3,2] + N [2,3] = 8, N [3,4] = N [3,3] + N [2,4] = 17.

1	1	1	1	0
5	4	3	2	1
9	4	0	3	1
7	8	4	4	1

0

1

2

3

4 3 2 1 0

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

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

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

1. Во-первых, верхняя грань любой костяшки домино разделена пополам на две части - левую и правую, в каждой из которых содержится (изображено) некоторое число очков из множества A = { 0,1,2,3,4,5,6 }, т.е. каждой костяшке поставлена в соответствие некоторая (в общем случае упорядоченная) двойка (пара) чисел (a,b), принадлежащих множеству A. При этом двойки чисел, представляющие разные костяшки, отличаются по составу. Следовательно, две двойки (a,b), (b,a), имеющие одинаковый состав, но разный порядок чисел, представляют одну и ту же костяшку.

2. Во-вторых, возможность приложения двух костяшек одна к другой (составления из них цепочки) появляется в ситуации, когда из двух двоек чисел (a,b), (c,d), соответствующих этим костяшкам, можно (путем перестановки либо самих двоек, либо чисел в двойках) образовать упорядоченную четверку ( f,g,g,h ), у которой числа, стоящие на второй и третьей позициях, совпадают. Такая ситуация будет иметь место тогда и только тогда, когда одно и то же число встречается в обеих двойках чисел (a,b), (c,d), представляющих разные костяшки.

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

Отмеченные обстоятельства позволяют сделать вывод: комплект костяшек домино можно интерпретировать как кортежи (a,b) бинарного отношения ≤ , заданного (определенного) на числовом множестве A = { 0,1,2,3,4,5,6 }. Выпишем все эти кортежи в виде треугольной таблицы

( 0,0 ), ( 1,1 ), ( 2,2 ), ( 3,3 ), ( 4,4 ), ( 5,5 ), ( 6,6 ),

( 0,1 ), ( 1,2 ), ( 2,3 ), ( 3,4 ), ( 4,5 ), ( 5,6 ),

( 0,2 ), ( 1,3 ), ( 2,4 ), ( 3,5 ), ( 4,6 ),

( 0,3 ), ( 1,4 ), ( 2,5 ), ( 3,6 )

( 0,4 ), ( 1,5 ), ( 2,6 ),

( 0,5 ), ( 1,6 ),

( 0,6 ).

В верхней строке таблицы расположено подмножество, состоящее из семи кортежей (a,b), имеющих одинаковые компоненты, т.е. удовлетворяющих равенству a = b. Эти кортежи изображают (интерпретируют) костяшки домино, называемые дуплями.

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

(0,5), (1,5), (2,5), (3,5), (4,5), (6,5).

В нижних строках таблицы (со 2 по 7) расположены кортежи, для которых выполняется строгое неравенство a < b. Эта группа включает 21 кортеж и изображает все остальные (не относящиеся к дуплям) костяшки. Их отличие от дуплей заключается в том, что к каждой из них можно приложить 12 костяшек. Так, согласно таблице, для недупля (2,4) к таким костяшкам относятся

(0,2), (1,2), (2,2), (2,3), (2,5), (2,6), (0,4), (1,4), (3,4), (4,4), (4,5), (4,6).

Таким образом, искомое множество С пар костяшек домино (удовлетворяющих условиям задачи) может быть записано в виде суммы С = А + В, где

А – подмножество пар, в которых первая из двух выбранных костяшек является дуплем;

В – подмножество пар, в которых первая костяшка является недуплем.

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

Na = | A | = 7∙6 = 42, Nb = | B | = 21∙12 = 252.

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

паре костяшек (5,5), (2,5) из множества А соответствует идентичная пара костяшек (2,5), (5,5), принадлежащая множеству В;

паре костяшек (1,3), (3,6) из множества В соответствует идентичная пара костяшек (3,6), (1,3), принадлежащая тому же множеству В.

Из отмеченного свойства следует - искомое число Nc пар костяшек домино, которые можно приложить друг к другу, будет равно

Nc = | С | = ( Na + Nb ) / 2 = (42 + 252) / 2 = 147.

Пример 2.5. Сколько шестизначных телефонных номеров можно составить, если в этих номерах третья цифра не может быть нулем, а в качестве первых двух цифр допускается использование чисел 31, 33, 36, 42, 44, 48, 55 ?

Так как на последние три цифры нет никаких ограничений,

то каждая из них может быть любым элементом множества

A = { 0,1,2,3,4,5,6,7,8,9 }, выполняющего роль алфавита.

В соответствии с правилом умножения число всевозможных

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

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

Таким образом, применяя еще раз правило умножения, искомое число N шестизначных номеров будет равно .

Пример 2.6. Из игральной колоды, содержащей 36 карт, по схеме случайного выбора вынимается одна карта. Во скольких случаях:

a) выбранная карта будет либо королем, либо картой крестовой масти;

б) выбранная карта не будет ни королем, ни картой крестовой масти ?

В соответствии с формулировкой в задаче фигурируют два свойства:

свойство α – принадлежность (или непринадлежность) вынутой карты подмножеству A королей;

свойство β – принадлежность (или непринадлежность) вынутой карты подмножеству B крестей.

Анализ комбинаторной ситуации показывает: для выбора из колоды короля имеется 4 альтернативных способа (в игральной колоде, как известно, 4 разномастных короля, т.е. | A | = M = 4 ), а карты крестовой масти – 9 альтернативных способов (в колоде 9 разных крестей, т.е.

| B | = N = 9 ). Имеется также единственный (уникальный) способ выбора (король крестовый), когда одновременно вынимаются и король, и крестовая карта (т.е. число совпадений | AB | = K = 1).

a) Чтобы ответить на первый вопрос, необходимо найти число Nc различных (альтернативных) способов выбора (вынимания из колоды) карты “либо король, либо крестовая масть ”, т.е. карты, обладающей хотя бы одним из свойств α, β. Применяя равенство ( 2.8 ), будем иметь

Nc = | C | = | A + B | = M + N – K = 4 + 9 – 1 = 12.

б) Ответом на второй вопрос будет число Lc альтернативных способов выбора (вынимания из колоды) карты “не король и не крестовая масть”, т.е. карты, не обладающей ни одним из свойств α, β. Так как для рассматриваемой ситуации полное множество предметов (универсальное множество) U есть не что иное, как вся колода карт ( | U | = 36), то искомое число будет, очевидно, равно

Lc = |U | - | C | = 36–12 = 24.

Пример 2.7. В потоке студентов, состоящем из 39 человек, положительные оценки за три контрольные работы получили: за 1 контрольную - 25 студентов, за 2 контрольную - 31 студент, за 3 контрольную - 31 студент, за 1 и 2 контрольные – 22 студента, за 1 и 3 контрольные - 22 студента, за 2 и 3 контрольные - 27 студентов, за все три контрольные - 21 студент. Сколько студентов не получило ни одной положительной оценки?

Введем следующие обозначения: A - множество студентов в потоке; B,C,D - подмножества студентов, получивших положительные оценки соответственно за 1, 2, 3 контрольные. Из исходных данных имеем:

|A|=39, |B|=25, |C|=31, |D|=31, |BC|=22, |BD|=22, |CD|=27, |BCD|=21.

Данный пример относится к классу задач, связанных с применением принципа включения и исключения. Роль предметов в данном случае играют студенты, а роль свойств, которыми они обладают, - положительные оценки за контрольные.

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

| | = |B+C+D| = 87 - |BC| - |BD| - |CD| + |BCD| = 37.

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

Пример 2.8. Дано n-элементное множество . Требуется с помощью принципа взаимно однозначного соответствия найти аналитическое выражение для количества всевозможных подмножеств множества .

Пронумеруем последовательно элементы и рассмотрим эквивалентное множество N = {1,2,...,n}, составленное из номеров элементов. Ясно, что множества и N имеют одинаковое число различных подмножеств.

Рассмотрим любое подмножество множества N и поставим ему в соответствие двоичное слово (слово, состоящее из кортежа нулей и единиц) по правилу: , если ; , если (i=1,2,…,n). Очевидно, что это соответствие взаимно однозначное.

Так как согласно правилу умножения количество K слов длиной n, составленных с помощью двухэлементного алфавита A={0,1}, удовлетворяет равенству K = , то именно это равенство как раз и будет определять искомый результат (аналитическое выражение).

Пример 2.9. Чему равно количество двоичных слов (последовательностей из нулей и единиц) длиной n, если в этих словах никакие две единицы не стоят на соседних местах (не идут подряд) ?

Обозначим искомое множество таких последовательностей через F (n), а их число (мощность множества) - через f (n). Ясно, что подмножество F (1) содержит две последовательности {0},{1}, а подмножество F (2) - три последовательности {00}, {01}, {1,0}, т.е.

f (1) = 2, f (2) = 3. Для того чтобы найти f (n) при произвольном n, разобьем множество F (n) последовательностей

,

удовлетворяющих условиям задачи, на два класса:

1) подмножество (n) последовательностей 0, оканчивающихся нулем (у которых = 0);

2) подмножество (n) последовательностей 1, оканчивающихся единицей (у которых = 1).

Каждой последовательности из первого класса поставим в соответствие последовательность . В итоге будет иметь место взаимно однозначное соответствие между подмножеством (n) и множеством F (n-1), содержащим все последовательности длиной (n-1), удовлетворяющие условиям задачи. Следовательно,

| (n) | = | F (n-1) | = f (n-1).

Рассмотрим произвольную последовательность из второго класса - подмножества (n).

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

| (n) | = | F (n-2 | = f (n -2).

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

f (n) = f (n-1) + f (n-2).

Так как f (2) = 3 и f (1) = 2, то из уравнения при n = 2 имеем f (0) = 1.

Таким образом, искомое число f (n) (n = 2,3,4,…) двоичных слов длиной n, в которых единицы не стоят рядом, может быть найдено с помощью рекуррентного уравнения f (n) = f (n-1) + f (n-2) и необходимых для его реализации (последовательного применения) начальных условий задачи: f (0) = 1, f (1) = 2.

Пример 2.10. Обоснуйте правомерность использования рекуррентного уравнения

f (n) = f (n-1) + f (n -2)

с начальными условиями f (0) = 1, f (1) = 2, полученного в примере 2.9, для решения известной задачи Фибоначчи.

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

Установим связь между двумя, на первый взгляд совершенно разными задачами: задачей Фибоначчи и задачей о двоичных числах, разобранной в примере 2.9.

Для этого возьмем любую пару кроликов (из множества имеющихся на момент окончания n-го месяца ) и сопоставим с этой парой последовательность E = { } из нулей и единиц, удовлетворяющую следующему требованию: индексам (номерам) единичных элементов последовательности соответствуют номера месяцев появления на свет одной из пар "предков" пары кроликов (включая и выбранную), а индексам нулевых элементов - номера всех остальных месяцев.

Так, например, последовательность {010010010100} будет соответствовать такой "генеалогии": сама пара появилась в 10 месяце, ее родители - в 8 месяце, "дед" - в 5 месяце, "прадед" - во 2 месяце. Исходной паре кроликов, которая появилась до начала отсчета времени (раньше первого месяца) будет, очевидно, сопоставлена нулевая последовательность {000000000000}.

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

В силу принципа взаимно однозначного соответствия, которое нами установлено, искомое число пар кроликов будет совпадать с числом f (n) двоичных чисел, удовлетворяющих условиям примера 2.9 и, как следствие, полученному в этом примере рекуррентному уравнению.

Легко также убедиться, что будут совпадать и начальные условия уравнения, а именно: f (0) = 1, так как в начальный момент времени была одна пара кроликов; f (1) = 2, так как на конец первого месяца стало две пары кроликов.

Применяя, в частности, рекуррентное уравнение (теперь уже обоснованное) и начальные условия для расчетов, получим, что через год (12 месяцев) число пар кроликов достигнет величины f (12) = 377.