МАЛЫЙ МЕХМАТ МГУ

Кружок 7 класса

Занятие 12. Телефонная комбинаторика

При решении задач этого занятия (да и всех остальных тоже) запрещается использовать телефоны и калькуляторы.

0.

28 ноября у преподавателей 7 класса Малого Мехмата школьники позаимствовали конфеты, оставленные на столе. Сколькими способами это могли сделать 6 учеников аудитории 1403, если они забрали 10 конфет? (Считается, что каждый взял хотя бы одну конфету и что школьники между собой не различаются.)

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

Ответ Решение

Ответ. Пятью способами.

Решение. Итак, шесть конфет распределены между школьниками по одной на человека. Осталось распределить оставшиеся четыре. Вопрос в том, между сколькими школьниками они распределяются. Возможны случаи: либо все четыре достались кому-то одному, либо четверым досталось по одной конфете, либо одному досталось две конфеты и еще двоим по одной, либо конфеты достались двоим (поровну или по 1 и 3 конфеты соответственно). Значит, всего пять способов.
Можно усложнить задачу, различая школьников по именам и допуская, что кто-то из шести «подозреваемых» вовсе не брал конфет.

Предупреждение: «заимствование» чужих вещей без согласия на то их владельца строго карается, вплоть до исключения с Малого Мехмата!

1.

У завхоза Петра Ивановича есть 5 сим-карт и 5 мобильных телефонов. Сколькими способами Большой Начальник может выбрать себе мобильный телефон и сим-карту?

Ответ Решение

Ответ. 25 способами.

Решение. Есть 5 способов выбрать телефон. Если телефон уже выбран, то существует 5 способов выбрать к нему сим-карту. Поэтому число способов выбрать мобильный телефон и сим-карту равно 5·5=25.

2.

А еще у Петра Ивановича есть четыре подставки под мобильный телефон. Сколькими способами может Большой Начальник выбрать себе мобильный телефон, сим-карту и подставку под телефон?

Ответ Решение

Ответ. 100 способами.

Решение. Продолжаем рассуждения, начатые в решении задачи 1. Как мы установили, существует 25 способов выбрать телефон и сим-карту. Если уже выбраны телефон и сим-карта, то есть 4 способа выбрать к ним подставку. Значит, всего существует 25·4=100 способов выбрать телефон, сим-карту и подставку.

3.

В фирме «Задачи дня» есть три Начальника. Из кабинета Первого Начальника в кабинет Второго ведет 6 коридоров, а из кабинета Второго Начальника в кабинет Третьего Начальника — 4 коридора. Сколькими способами Первый Начальник может пройти в кабинет Третьего Начальника?

Ответ Решение

Ответ. 24 способами.

Решение. Есть 6 способов дойти от кабинета Первого Начальника до кабинета Второго Начальника. Для каждого из этих способов есть еще по 4 способа дойти от кабинета Второго Начальника до кабинета Третьего Начальника. Значит, способов дойти от кабинета Первого Начальника до кабинета Второго Начальника 4·6=24.

4.

В фирме «Задачи дня» назначили еще Четвертого Начальника, из его кабинета в кабинет Третьего Начальника ведет 5 коридоров. Сколькими способами может Первый Начальник дойти до Четвертого начальника?

Ответ Решение

Ответ. 120 способов.

Решение. Аналогично решению задачи 3, 24·5=120.

5.

У завхоза Петра Ивановича все еще есть 5 сим-карт, 4 подставки и 5 мобильных телефоонв. Сколькими способами Большой Начальник может выбрать себе два предмета с различными названиями?

Ответ Решение

Ответ. 65 способами.

Решение. Есть 5·5=25 способов выбрать телефон и сим-карту, 5·4=20 способов выбрать сим-карту и подставку и 5·4=20 способов выбрать телефон и подставку (см. задачу 1). Поэтому всего способов выбрать два предмета с различными названиями будет 25+20+20=65.

6.

Сколькими способами Петр Иванович может раздать

1. 3 важных документа 3 менеджерам;
2. 5 важных документов 5 менеджерам;
3. 8 важных документов 8 менеджерам;
4. 2009 важных документов 2009 менеджерам?

Ответ Решение

Ответ.

1. 6 способами;
2. 120 способами;
3. 40320 способами;
4. 2009!=1·2·3·…·2008·2009 способами.

Решение. Рассмотрим случай а. Сначала выберем, кому из трех менеджеров отдать первый документ. Есть 3 способа это сделать. Теперь выберем, кому отдать второй документ. Это уже можно сделать только двумя способами, так как один менеджер уже занят. Ну а последний документ можно отдать только последнему свободному менеджеру. Значит, всего способов раздать три документа трем менеджерам будет 3·2·1=3!. Аналогично решаются остальные пункты. 5!=120, 8!=40320. Полезно сравнить эту задачу с задачей 1 и понять, что это две абсолютно разные задачи.

7.

В фирме «Задачи дня» много менеджеров. Любые два соединены телефонной линией. Сколько телефонных линий в фирме «Задачи дня», если в ней

1. 5 менеджеров;
2. 15 менеджеров;
3. 2009 менеджеров?

Ответ Решение

Ответ.

1. 10 линий;
2. 105 линий;
3. 2017036 линий.

Решение. Рассмотрим случай а. Количество линий равно количеству всевозможных пар менеджеров, то есть количеству способов выбрать двух менеджеров из пяти (причем неважно, кто в каждой паре будет первым, а кто вторым). Есть 5 способов выбрать одного из менеджеров, а после этого 4 способа выбрать ему пару. То есть способов выбрать пару менеджеров вроде бы 20. Но мы не учли, что каждую пару мы посчитали два раза (сначала один из менеджеров был выбран первым, а потом другой). Значит, надо полученное число поделить пополам. Аналогично рассматриваются остальные случаи (не поленитесь произвести вычисления в столбик!).

Замечание. Количество способов выбрать k элементов из n элементов, если их порядок неважен, называется числом (неупорядоченных) сочетаний из n по k и обозначается C_n^k. Применяя рассуждения, аналогичные проведенным при решении этой задачи, можно получить, что C_n^k=^{n·(n − 1)·…·(n − k + 1)}/_k!. На k! нужно делить потому, что каждую комбинацию из k элементов можно получить k! способами (k способов выбрать первый элемент, k-1 способ выбрать второй, ..., 1 способ выбрать k-й элемент). Теперь заметим, что n!=1·2·…·(n-k)·(n-k+1)·n, a (n-k)!=1·2·…·(n-k). Поэтому n·(n − 1)·…·(n − k + 1)=^n!/_{(n − k)!}, и формулу числа сочетаний обычно записывают в таком виде:
C_n^k=^n!/_{k!(n − k)!}.
C помощью этой формулы можно доказывать различные утверждения о числе сочетаний (например, такие: C_n^k=C_nⁿ − k; C_n^k − 1 + C_n^k=C_n + 1^k и др.), хотя часть из них нетрудно доказать, пользуясь только определением. Для вычислений удобнее использовать способ записи этой формулы, приведенный выше (тогда не приходится вычислять факториалы от больших чисел).

8.

В фирму «Задачи дня» к новому году привезли 3 светло-зеленых и 5 темно-зеленых елок. Сколькими способами Петр Иванович может раcставить эти елки в восьми конференц-залах фирмы «Задачи дня»?

Ответ Решение

Ответ. 56 способами.

Решение. Чтобы расставить елки в восьми конференц-залах, нужно решить, в какие залы поставить светло-зеленые елки (а в оставшиеся залы поставить темно-зеленые елки). Способов сделать это столько же, сколько способов выбрать три зала из восьми. Руководствуясь соображениями, описанными в решении задачи 7, подсчитаем, что C₈³=^8·7·6/_3!=8·7=56.

9.

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

1. МАЛЫЙ;
2. МЕХМАТ?

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

Ответ Решение

Ответ.

1. 120 слов;
2. 360 слов.

Решение. Рассмотрим сначала пункт а. Можно пятью способами выбрать первую букву слова, после этого четырьмя — вторую, тремя — третью, двумя — четвертую и одним — пятую (похожие соображения использовались нами при решении задачи 6). Итого 5!=120 различных слов.
В пункте b ситуация осложняется тем, что в слове «МЕХМАТ» две буквы М: «первая» и «вторая». Поэтому, если подсчитывать число возможных слов так же, как в пункте а, то каждое слово будет посчитано два раза (в зависимости от того, какая из букв М «первая», а какая «вторая»). Таким образом, для получения окончательного ответа надо полученное число разделить пополам. У нас получится ^6!/₂=⁷²⁰/₂=360.
Можно еще больше усложнить задачу. Например, поставить такой вопрос: сколько слов можно составить из букв тех же самых слов, что и раньше, если не обязательно задействовать все буквы? Подумайте, как свести эту задачу к исходной, и решите ее.

10.

Чтобы сохранить переговоры Больших начальников в секрете, Самый Большой Начальник придумал новый язык: в нем 6 гласных и 8 согласных, причем двух одинаковых букв в слове быть не может, а гласные и согласные в слове непременно чередуются. Сколько слов из девяти букв может быть в этом языке?

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

Ответ Решение

Ответ. 3628800 слов.

Решение. Все слова нового языка делятся на две группы: те, которые начинаются с гласной, и те, которые начинаются с согласной. Отметим сразу, что в словах из первой группы 5 гласных и 4 согласных, а в словах второй группы — наоборот. Подсчитаем количество слов в каждой из этих групп.
Начнем с первой группы. чтобы составить слово, нужно выбрать 5 гласных и 4 согласных (порядок выбираемых гласных и выбираемых согласных важен!).

Количество способов выбрать k элементов из n элементов назвается числом упорядоченных сочетаний из n по k и обозначается A_n^k. Вспоминив доказательство формулы для числа неупорядоченных сочетаний из задачи 7, докажите самостоятельно, что A_n^k=^n!/_{(n − k)!} (можно это доказать и непосредственно по определению).

Итак, есть 720 способов упорядочить 5 гласных из 6 и 1680 способов упорядочить 4 согласных из 8 (проверьте это самостоятельно!). Итого будет 720·1680=1209600 слов.
Аналогично подсчитываем число слов из второй группы. Есть 360 способов упорядочить 4 гласных из 6 и 6720 способов выбрать 5 согласных из 8. Итого 360·6720=2419200 способов. Осталось сложить два полученных результата. Всего в новом языке 1209600+2419200=3628800 слов.
Кстати, автор этих строк честно проделал все вычисления в столбик. Не поленитесь и вы это сделать.

11.

Бухгалтер Лидия Николаевна фирмы «Задачи дня» решила выдать необычную зарплату. Она решила как можно большему числу сотрудников выдать зарплату, которая записывалась бы только трехзначными числами и нечетными цифрами. Скольким сотрудникам она сможет выдать такую зарплату, чтобы не было двух сотрудников с одинаковой зарплатой?

Ответ Решение

Ответ. 125 сотрудникам.

Решение. Нечетных цифр всего 5. Любая из них может стоять в числе на первом месте, любая на втором и любая на третьем. Итого 5·5·5=125 способов выдать зарплату.

12.

А если она будет выдавать пятизначную зарплату только из четных цифр?

Ответ Решение

Ответ. 2500 сотрудникам.

Решение. Задача в целом решается так же, как задача 11. Разница только в том, что среди четных цифр есть 0, и если он окажется в начале числа из пяти цифр, то число уже не будет пятизначным. Поэтому на первом месте может стоять одна из четырех цифр, а на каждом из остальных — одна из пяти. Всего будет 4·5·5·5·5=2500 способов выдать зарплату.

13.

А если шестизначную зарплату, из чисел кратных пяти, составленных из цифр 0, 1, 2, 3 и 5?

Ответ Решение

Ответ. 5000 сотрудников.

Решение. Решение аналогично решению задачи 12. Добавляется еще одно требование: чтобы число делилось на 5, на конце должен стоять 0 или 5. На первом месте по-прежнему может быть любая цифра, кроме нуля. Всего 4·5·5·5·5·2=5000 способов.

14.

Для регистрации на сайте фирмы «Задачи дня» ведущий программист Вася решил придумать логин из трех цифр и пароль — из четырех, причем таким образом, чтобы логин получался из пароля вычеркиванием одной цифры. Сколькими способами он может придумать себе пароль, если он уже придумал себе логин?

Ответ Решение

Ответ. 37 способами.

Решение. Вопрос в том, сколько способов получить четырехзначное число из трехзначного добавлением одной цифры (добавлять ее можно в том числе в начало и конец). Сначала ответим на этот вопрос для конкретной добавляемой цифры. Здесь все зависит от того, встречается ли уже эта цифра в логине и если да, то сколько раз. Если выбранная цифра в логине отсутствует, то, вставляя ее в разные места, каждый раз будем получать новый результат. Это четыре различных пароля. Если цифра в логине встречается ровно один раз, то добавление новой цифры справа и слева от уже имеющейся даст один и тот же результат. Значит, в этом случае имеем только три логина. В случае, когда выбранная цифра встречается в числе дважды, есть только два различных способа получить пароль (проверьте все ситуации самостоятельно!). И наконец, если логин состоит из таких же цифр, как выбранная, то, вставляя ее в любое место, мы будем получать один и тот же результат.
Если в числе вовсе нет повторяющихся цифр, то каждую цифру, не входящую в число, можно добавлять в любое место (то есть четырьмя способами), а три оставшиеся — только тремя различными способами. Итого 7·4+3·3=37 способов составить пароль. Если какая-то цифра входит в число дважды, то ее можно добавить лишь двумя способами, другую цифру, входящую в число, лишь тремя способами, а все остальные — четырьмя. Всего 2+3+8·4=37 способов. И наконец, если цифра входит в логин три раза, то ее можно добавить только одним способом, а любую другую — четырьмя. Снова 1+9·4=37 способов.
Кстати, подумайте, почему ответ получился одинаковым во всех трех случаях. Нельзя ли упростить приведенное решение?

15.

Сейчас в фирме «Задачи дня» 25 менеджеров.

1. Сколькими способами Большой Начальник может выбрать трех из них себе на должности главного по персоналу, по продажам и по связям с прессой?
2. А сколькими способами он может выбрать трех менеджеров, чтобы выдать им премию?

Ответ Решение

Ответ.

1. 13800 способами;
2. 2300 способами.

Решение. Эта задача решается аналогично задачам 10 и 7. Различие пунктов а и b в том, что в первом случае важен порядок выбора менеджеров (то есть кто из выбранных какую должность получит), а во втором случае все трое выбранных равноправны. Значит, в первом случае количество способов выбора равно A₂5³=13800 (см. задачу 10), а во втором случае — C₂5³=2300 (см. задачу 7).

16.

В фирме «Задачи дня» у программистов есть 15 телефонов. Один Больной Начальник утверждает, что каждый телефон соединен с тремя другими. Не преувеличивает ли Большой Начальник возможности телефонной сети у программистов?

Ответ Решение

Ответ. Преувеличивает.

Решение. Попытаемся подсчитать количество проводов, соединяющих все телефоны между собой. На каждый телефон приходится три выходящих из него провода, то есть проводов вроде бы 15·3=45. Но каждый провод мы посчитали два раза (для каждого из телефонов, которые он соединяет), значит, это число надо еще поделить пополам. Но 45 — число нечетное, и у нас получится нецелое число проводов, а такого быть не может. Полученное противоречие доказывает, что Большой Начальник ошибается.