Отправляет email-рассылки с помощью сервиса Sendsay

Математический кружок

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Работа и обучение за рубежом для студентов и не только!" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Октябрь 2001   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
Роман Александрович Семизаров

Статистика

2.740 подписчиков
0 за неделю
←   Все выпуски   →

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


Служба Рассылок Subscribe.Ru

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

Несколько замечаний о вчерашней части выпуска. Во-первых, в решении задачи 29 фразу "Сумма десяти нечётных чисел всегда является нечётным числом'', конечно, следует читать "Сумма десяти нечётных чисел всегда является чётным числом''. Во-вторых, в условии задачи 32 можно увидеть
...знаки "$+$" и "$-$"...
Знаки доллара здесь, конечно, лишние. Это издержки полуавтоматическиго перевода из TEX. И, наконец, в задаче 39 возможна такая последовательность действий:
1-2-4-8-16-32-64-46-92-29-58-85-170-17-34-68.
Устно на кружке сообщалось, что ставить 0 на первое место нельзя. Однако, я считаю, что число не может начинаться с 0, то есть нет никаких причин считать "017'' записью числа 17.

Сегодня мы начинаем новую тему, она называется "комбинаторика''. Начнём с примеров задач.

Задача

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

Конечно, мы знаем, сколько будет 5x7. Но ответ всё равно оставим в таком виде. В более сложных задачах в ответе могут получаться выражения, требующие весьма трудоёмких вычислений. Найти в таком случае числовой ответ - задача непростая и совершенно нам сейчас неинтересная.

Задача

Сколько способов выбрать в классе, в котором 18 учеников, старосту и его заместителя?
Решение. Есть 18 способов выбрать старосту. Для выбранного старосты мы можем выбрать одного из оставшихся 17 учеников в заместители. Ответ: 18x17 способов.

Задача

В следующем году в том же классе решили избрать двух равноправных старост. Сколько способов это сделать?
Решение. С первого взгляда кажется, что эта задача не отличается от предыдущей, и ответ - 18x17. Рассмотрим более простую задачу, пусть в классе всего 4 человека (их зовут A, B, C и D). Следуя нашему способу рассуждения, получаем, что ответ в этом случае - 4x3=12. Но попытаемся перечислить возможные пары старост:
  • (A, B)
  • (A, C),
  • (A, D),
  • (B, C),
  • (B, D),
  • (C, D).
Мы перечислили все возможные пары, и всего их оказалось шесть. Тем не менее, если бы выбирали не двух старост, а старосту и заместителя, годилась бы, например, пара (B, A) - считаем, что первый в паре - староста, а второй - заместитель. Теперь очевидно различие между задачами: в задаче про двух старост пара (A, B) - та же пара, что (B, A). Так что, дав ответ 4x3, мы каждую пару посчитали дважды. Правильный ответ на упрощённую задачу - 4 x 3 / 2. Возвращаемся к исходной задаче. В ней ответ - 18 x 17 / 2.

Задача

На следующий год было принято решение избрать двух равноправных старост, но так, чтобы один из них обязательно был мальчиком. Сколько способов сделать это, если мальчиков в классе 10, а девочек - 8.
Решение.

Первый способ. Старостами могут стать два мальчика, а могут - мальчик и девочка. Выбрать двух мальчиков 10 x 9 / 2 способов (вы уже должны понимать, почему), а мальчика и девочку - 10 x 8 способов. Поэтому ответ - 10 x 9/2 + 10 x 8. Этот способ демонстрирует важную идею: возможные способы можно разбить на группы, посчитать число способов в каждой группе и сложить результаты.

Второй способ. Всего способов выбрать двух старост, как мы знаем, 18 x 17 / 2. но некоторые способы запрещены - нельзя выбирать двух девочек. Таких запрещённых способов 8 x 7 / 2. Значит разрешённых способов 18 x 17 / 2 - 8 x 7/2. Этот способ демонстрирует другую важную идею - чтобы посчитать число "хороших'' способов, можно посчитать общее число способов и вычесть из него число "плохих'' способов.

Решая задачу двумя разными способами, мы получили два разных ответа. Разве так бывает? Конечно, нет. Поэтому, на самом деле, мы получили два разных выражения для одного и того же ответа. Если не верите - посчитайте. В обоих случаях получается 125.

Задача

Сколько способов выстроить наш класс в шеренгу?
Решение. На первое место мы можем поставить любого из 18 учеников. На второе - любого из оставшихся 17. Поэтому поставить первых двоих есть 18x17 способов. При любом из этих способов на третье место можно поставить любого из оставшихся 16 человек. Значит поставить первых троих 18x17x16 способов. Продолжая рассуждать так далее, получаем, что ответ - 18 x 17 x 16 x ... x 3 x 2 x 1. Это произведение принято записывать как 18! (восклицательный знак здесь не знак препинания, а математические обозначение). Читается это "восемнадцать факториал''.

Задача

Сколько способов выбрать в нашем классе трёх старост (мальчики они будут, или девочки, нам снова неважно).
Решение. По аналогии со случаем двух старост, хочется сказать, что ответ 18 x 17 x 16 / 2 или 18 x 17 x 16 / 3. Однако, это неверно. Например, вновь рассмотрев класс из четырёх человек A, B, C и D, видим, что способов не 4 x 3 x 2 / 2 = 12 и даже не 4 x 3 x 2 / 3 = 8, а всего 4:
  • (A, B, C),
  • (A, B, D),
  • (A, C, D) и
  • (B, C, D).
Вспомним, как мы рассуждали, когда выбирали двух старост и будем рассуждать так же. Выбрать "первого'' старосту 4 способа, второго - 3 способа, а третьего - 2 способа. Поэтому выбрать таких трёх "пронумерованных'' старост 4 x 3 x 2 способов. Но некоторые способы мы посчитали по нескольку раз. Выясним, например, сколько раз мы посчитали тройку (A, B, C). Вот все способы пронумеровать старост этой тройки:
  • (A, B, C),
  • (A, C, B),
  • (B, A, C),
  • (B, C, A),
  • (C, A, B),
  • (C, B, A).
Значит, мы посчитали эту тройку 6 раз. На самом деле, мы практически перечислили все способы поставить трёх старост в шеренгу, разумеется этих способов оказалось 3!=6. Итак, правильный ответ - 4 x 3 x 2 / 6, то есть действительно 4. Рассуждая так же в исходной задаче, получаем, что её ответ: 18 x 17 x 16 / 6.

Новые задачи

55. Сколькими способами можно зажечь свет в нашем классе? (в классе 4 лампочки, у каждой -- отдельный выключатель).

56. Комбинация из трёх букв на автомобильном номере состоит только из тех русских букв, у которых есть похожие латинские, а именно из А, В, Е, К, М, Н, О, Р, С, Т, У, Х. Сколько всего таких комбинаций?

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

58. а) В магазине "Все для чая" продаются 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить там набор "чашка + блюдце"?

б) В тот же магазин завезли еще 4 вида чайных ложек. Сколькими способами можно купить комплект "чашка + блюдце + ложка"?

в) Известно, что одна из чашек, одно из блюдец и одна из ложек -- золотые. Сколькими способами можно купить набор из 3-х различных предметов, в котором

   в1) нет золотых предметов?

   в2) 1 золотой предмет?

   в3) 2 золотых предмета?

   в4) 3 золотых предмета?

г) Сколькими способами в магазине можно купить комплект из двух предметов?

д) сколькими способами можно купить комплект из 1 предмета?

е) Ясно, что "купить 0 предметов" можно единственным способом. Каков смысл равенства 1+12+47+60=6 x 4 x 5?

59. а) У скольких двузначных чисел все цифры чётные? б) А у скольких трёхзначных?

60. а) У скольких двузначных чисел все цифры разные? б) А у скольких трёхзначных? в) А у скольких 11-значных?

61. На окружности отмечены 5 красных и 7 синих точек. Рассмотрим всевозможные отрезки (хорды) с концами в отмеченных точках. У скольких отрезков концы а) разного цвета; б) одинакового цвета?

62. В обычном домино на половинках доминошек бывает от 0 до 6 точек. Всего в комплекте 28 доминошек. А сколько доминошек будет в комплекте, где на половинке возможно от 0 до 13 точек?

63. Сколькими способами можно поставить на доску черного и белого королей так, чтобы они не били друг друга?

Роман Семизаров
roma7@zaba.ru
http://zaba.ru
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу 		Рейтингуется SpyLog
В избранное