Примеры решения простейших комбинаторных задач

Решение. Типичная задача на принцип умножения. Представим себе, что из города A в город B ведут 7 дорог, на каждой из которых продают разные виды чашек. А из города B в город C ведут 5 дорог, на каждой из которых продают один вид блюдец. Таким образом, чайный набор покупается при проезде из A в C, что можно сделать 35-ю способами.

Задача 2.Монета бросается 10 раз и получается набор длины 10 из выпавших результатов: орёл или решка. Сколько различных наборов с четырьмя орлами получится ?

Ответ: = 1260.

Задача 3.Сколько слов (произвольных последовательностей) длины 1000 можно составить из букв русского алфавита ?

Ответ: 33¹⁰⁰⁰ .

Решение. В русском алфавите 33 буквы. Так что .

Задача 4.Простейшая молекула белка, как утверждают учёные-биологи, представляет собой последовательность длины 50 из основных 20-ти аминокислот. Оцените, сколько лет потребуется, чтобы перебрать все возможные комбинации таких последовательностей, если в каждом кубическом миллиметре шарового слоя Земли высоты 10 км. за одну секунду осуществляется независимый перебор 1000000 вариантов ?

Ответ: более 10 ²¹лет.

Решение. Всего последовательностей длины 50 из 20 аминокислот будет 20⁵⁰ = 2⁵⁰·10⁵⁰ .

Объём шара V = ·p·R³ , поэтому объём шарового слоя высоты h вычисляется так: V_h = ·p·[(R + h)³ – R³]. Учитывая, что радиус Земли примерно равен 6400 км., получим объём рассматриваемого в задаче шарового слоя

·p·[6410³ – 6400³] = ·p·10⁶·[64,1³ – 64³] =

= ·p·10⁶·[0,1·(64,1² + 64,1·64 + 64²)] £

£ ·p·10⁵·3·64,1² < 4·4·10⁵·100² < 10¹¹ (км³).

Далее, 1 км³ = 10⁹ м³ = 10⁹·10⁶ см³ = 10¹⁵·10³ мм³ . Значит, объём рассматриваемого шарового слоя меньше 10²⁹ мм³.

Даже, если перебор комбинаций будет вестись в 10²⁹ мм³, то одному из этих кубических миллиметров нужно перебрать не менее = 2⁵⁰·10²¹ 10¹⁵·10²¹ = 10³⁶ комбинаций.

В одном году менее 60·60·24·366 < 100·100·100·1000 = 10⁹ секунд. Значит, понадобится более = 10²⁷ лет. Учитывая, что в каждую секунду производится перебор 10⁶ вариантов, время перебора сокращается до 10 ²¹ лет.

А как же возраст Вселенной, оцениваемый учёными-астрофизиками в 20 миллиардов лет (20·10⁹ = 2·10¹⁰ лет) ?! Могла ли случайная эволюция за это время создать не только простейшую молекулу белка, но и гораздо более сложные структуры ? Например, геном человека, как утверждают те же учёные-биологи, является последовательностью из » 25000 генов, а каждый ген сам обладает сложной структурой ! Думайте сами, решайте сами…

Задача 5.Каждую клетку таблицы 3´3 можно раскрасить в 3 цвета. Сколькими способами можно раскрасить таблицу, чтобы в ка­ж­дой строке и в каждом столбце встречались все три цвета ?

Ответ: 12.

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

Учитывая, что допускаются произвольные перестановки цветов, т.е. вместо порядка (б, с, к) можно рассматривать произвольный другой порядок – перестановку этих букв, получим 2×3 ! = 12 раскрасок.

Задача 6.Сколько можно сшить трёхцветных флагов из полосок материи шести цветов, если флаги с одинаковыми цветами, но различными их расположениями считать разными ?

Ответ: = 120.

Решение. Типичная задача на размещения шести элементов по трём местам. А если не учитывать расположение полос ? Тогда = 20.

Задача 7.В стране 30 городов, каждые два из которых соединены авиалиниями. Сколько всего авиалиний ?

Ответ: = 435.

Решение. Авиалиния определяется своими концами, т.е. произвольно выб­ранными двумя городами из 30. Число этих сочетаний равно = 435 .

Задача 8.Игральный кубик бросают шесть раз. Сколько последовательностей из шести результатов бросаний содержат хотя бы одну шестёрку ?

Ответ: 21031.

Решение. Проще вычислить, в скольких случаях совсем нет шестёрки. Это произойдёт в 5⁶ случаях из общего числа 6⁶ случаев. Таким образом, хотя бы одна шестёрка выпадает в 6⁶ – 5⁶ = (6²)³ – (5²)³ = (6²–5²)×(6⁴+6²×5²+5⁴) = = 11×((6²+5²)²–6²×5²) = 11×(61+30)×(61–30) = 11×91×31 = 91×341 = 90×341+341= = 30690 + 341= 31031 случаях.

Задача 9.Сколько четырёхзначных чисел можно составить из цифр 0, 3, 5, 8 (цифры не повторяются) ?

Ответ: 18.

Решение. P₄ – P₃ = 4 ! – 3 ! = 18 (учесть, что 0 не может быть старшей цифрой).

Замечание.Если цифры могут повторяться, то получится 3·4³ = 192 числа. Если исключать число 0 = 0000, то останется 191 число.

Задача 10.У математика 7 книг, а у поэта – 9. Сколькими способами можно обменять две математические книги на четыре поэтических ?

Ответ: 15876.

Решение. Правило умножения: = 21×756 = 15876.

Задача 11.Сколько различных (в том числе и бессмысленных) слов можно составить из букв слов ТИГР, ПАРА.

Ответ: 24, 12.

Решение.Для слова ТИГР, в котором нет одинаковых букв, ответ 4! = 24. Для слова ПАРА – = 12: ПАРА, ПРАА, ПААР, АПРА, АРПА, ААРП, АПАР, ААПР, АРАП, РПАА, РАПА, РААП. Здесь две буквы А можно менять местами, поэтому и делим на количество перестановок на двух символах.

Для слова ПАРАЛЛЕЛОГРАММ, в котором три буквы А и Л, по две буквы Р и М аналогично получим = 605404800.

Задача 12.Сколько всего результатов бросания трёх одинаковых игральных костей ?

Ответ: 56.

Решение.Сочетания с повторениями: результат бросания представляет собой набор , где . Поэтому количество результатов равно .

Задача 13.Карточная колода из 52 карт раздаётся 4-м игрокам: вначале 13 карт первому, потом – 13 карт второму, и т.д. В скольких случаях каждому из игроков будет роздано по тузу ?

Ответ: 13⁴× ×12!×4! .

Решение.Рассматриваем колоду как слово из 52 различных букв. Если один из тузов, например, туз червей (Ч), попал в первые 13 букв, то он может оказаться на любой позиции с 1-й по 13-ю, а на остальных позициях могут участвовать все буквы, кроме тузов, без повторений, т.е. . Всего вариантов (по принципу сложения) 13× .

Для второго игрока и туза бубён (Б) ситуация аналогична, только уже нельзя использовать карты первого игрока: количество вариантов 13× . Для третьего и туза пик (П) – 13× , а для четвёртого и трефового туза (Т) – 13× = 13×12! .

По принципу умножения получаем 13⁴× × × ×12! . В этих вычислениях был фиксирован порядок тузов: (Ч, Б, П, Т). Ясно, что возможны любые перестановки. Так что ответ: 13⁴× × × ×12!×4! .

Задача 14.Сколько существует автобусных билетов с шестизначными номерами, в которых участвуют только цифры 3, 5, 7, и сумма цифр которых делится на 3 ?

Ответ: 213.

Решение. Общее число автобусных билетов с цифрами 3, 5, 7 подсчитать легко: это просто = 3⁶. Какие из номеров билетов делятся на 3 ? Те, сумма цифр которых делится на 3. Цифру 3 при этом, очевидно, можно не учитывать. Если в номере участвуют k пятёрок и m семёрок, то их сумма k×5+m×7 = k×(5+7)+(m–k)×7 делится на 3 тогда и только тогда, когда делится на 3 разность m–k. Можно перечислить все варианты:

 

троек	пятёрок	семёрок	число билетов
6	0	0	1
0	6	0	1
0	0	6	1
3	3	0	= 20
3	0	3	= 20
0	3	3	= 20
4	1	1	2× = 30
1	4	1	= 15
1	1	4	= 15
2	2	2	= 15×6

 

Всего получается 1+2·20+2·1+30+2·15+90+20 = 213 билетов.

Задача 15.Доказать равенство .

Решение. По формуле бинома Ньютона имеем

Отсюда . С другой стороны, как было отмечено выше, . Сравнивая коэффициенты при одинаковых степенях x, получим требуемое равенство.

Задача 16.Вычислить сумму “арифмо-геометрической” прогрессии

1 + 2×q + 3×q² + … + (n+1)×qⁿ .

Ответ: при q = 1, при q ¹ 1.

Решение. Дифференцируя формулу суммы геометрической прогрессии

1 + x + … + xⁿ⁺¹ = (x ¹ 1),

получим 1+2×x+…+(n+1)×xⁿ = .

Для правильной записи ответа нужно учесть случай q = 1.

 

Предыдущая12345678910Следующая

---

Не нашли, что искали? Воспользуйтесь поиском по сайту:

©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.