Математический кружок Занятие 8. Комбинаторика-2

Здравствуйте, друзья.

Разбор задач предыдущего занятия

Задача 55. К сожалению, условие задачи можно понять по-разному. Имелось в виду, что каждому способу зажечь свет соответствует 1, 2, 3 или 4 зажжённых лампочки. Каждая лампочка может быть зажжена, а может быть не зажжена, поэтому способов 2 x 2 x 2 x 2=2⁴. Убрав способ, при котором ни одна лампочка ни горит, получаем, что ответ 2⁴-1.

Если же способ включить свет - это последовательность, в которой включаются лампы (все 4), то ответ - 4 x 3 x 2 x 1.

Задача 56. Всего букв 12, на каждом месте может стоять любая буква, поэтому ответ - 12 x 12 x 12=12³.

Задача 57. Где бы ни стояла белая ладья, она бьёт 15 полей (считая то, на котором стоит). Возможных положений белой ладьи 64, поэтому ответ - 64 x 15.

Задача 58. а) по правилу произведения получаем 5 x 3=15.

б) 5 x 3 x 4=60.

в1) Считаем количество незолотых предметов: 4 чашки, 2 блюдца, 3 ложки. По правилу произведения получаем 4 x 2 x 3=24.

в2) Подметим, что 1 золотой предмет - либо чашка, либо ложка, либо блюдце. Если это чашка, то имеем 1 x 2 x 3=6 способов, если это блюдце, то число способов равно 4 x 1 x 3=12, наконец, для ложки получаем 4 x 2 x 1=8 способов. Итого - 26.

в3) Возможны 2 разумных перебора - либо по парам золотых предметов ("чашка+блюдце", "чашка+ложка", "ложка+блюдце"), либо перебор не-золотых предметов. При обоих подходах получаем 1 x 1 x 3 + 1 x 2 x 1 + 4 x 1 x 1 = 9 способов.

в4) 1 способ. Ответ: 1 x 1 x 1. 2 Способ. Так как всего возможностей 60 (см. задачу б)), а в задачах в1)-в3) были найдены 24+26+9=59 из них, то на долю задачи в4) остался последний, единственный, способ.

г) По правилу суммы - 5 x 3 + 5 x 4 + 3 x 4 = 47 способов.

д) 5+4+3 = 12.

е) Смысл состоит в том, что мы добавляем для каждого предмета еще одну возможность - либо покупать его, либо нет. Это значит, что мы как бы вводим шестую "липовую чашку", четвертое "липовое блюдце" и пятую "липовую ложку". Если выбран "липовый" предмет, это означает, что мы данный вид посуды просто не покупаем. Но теперь есть всего 6 x 4 x 5 способов выбрать набор из 3-х предметов (некоторые из которых будут липовыми), а сумма слева представляет собой разбиение на случаи "0 липовых", "1 липовый", "2 липовых", "3 липовых".

Задача 59. а) Ответ: 4 x 5 (на первом месте любая из цифр 2, 4, 6, 8; на втором - любая из 0, 2, 4, 6, 8;

б) Ответ: 4 x 5 x 5.

Задача 60. а) Ответ: 9 x 9=81 (первая цифра - любая, кроме 0, вторая - любая, кроме первой; б) Ответ: 9 x 9 x 8; в) Конечно таких 11-значных чисел нет.

Задача 61. а) Ответ: 5 x 7;

б) Ответ: 5 x 4 / 2 + 7 x 6 / 2.

Задача 62. Первый способ. Всего есть 14 дублей и 14 x 13 / 2 доминошек, не являющихся дублями. Ответ: 14+14 x 13 / 2.

Второй способ. Разрежем каждую доминошку пополам. Всего есть 15 половинок с нулём точек, 15 половинок с одной точкой, 15 половинок с двумя точками, и так далее. Поэтому всего 15 x 14 половинок, а, значит, доминошек 15 x 14 / 2.

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

Задача 63. Если черный король стоит в углу доски (4 поля), то белого короля на доску можно поставить 60 способами. Если черный король стоит на границе доски (но не в углу - 6 x 4=24 поля), то белого короля можно поставить на любое из 58 "незапрещенных" полей. Для всех остальных (их 36) положений черного короля имеется ровно 55 "незапрещенных" положений белого короля. Итого получаем 4 x 60 + 24 x 58 + 36 x 55 способов.

Новые задачи

Задача 64. Сколькими способами можно разменять 50 руб монетами в 1 и 2 руб?

Задача 65. В детский сад привезли кубики, красные и синие. Каждому из 100 детей выдали по 3 кубика, и каждый ребенок построил из своих кубиков башню. Какое наибольшее число различно раскрашенных башен могло получиться? А если выдали по 4 кубика? По 5? По 6? По 7?

Задача 66. Сигнальное устройство состоит из пяти одноцветных лампочек, расположенных в ряд. Сколько различных сигналов можно подать с его помощью? А сколько, самое меньшее, надо взять лампочек, чтобы можно было подать 200 различных сигналов? А 1000 сигналов?

Задача 67. Назовем число забавным, если все его цифры делятся на 4. Сколько забавных чисел среди четырёхзначных? А среди шестизначных?

Задача 68. Как известно, компьютер работает с двоичными кодами, которые представляют собой записи, составленные из нулей и единиц (например, 11001011). Количество знаков в коде называется его длиной. Сколько разных символов можно закодировать двоичными кодами длины 5? Длины 6?

Задача 69. Во рту у марсианина есть 10 гнезд для зубов. В каждом гнезде либо есть зуб, либо его нет. Известно, что любые два марсианина отличаются набором зубов (т.е., если взять любых двух, то найдется гнездо, в котором у одного есть зуб, а у другого нет). Каково наибольшее возможно число марсиан?

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

Задача 71. Назовем две цифры близкими, если они отличаются на 1. Кроме того, будем считать близкими цифры 0 и 9. Сколько существует различных десятизначных чисел, у которых любые две соседние цифры - близкие?

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

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