Комбинаторные задачи

Здравствуйте, мальчики и девочки! С вами снова я – профессор Циферкин. Наше сегодняшнее занятие будет посвящено решению комбинаторных задач. Я думаю, что у вас возник вопрос: «А что это за задачи такие?». Прежде чем на него ответить, надо сказать, что такое «комбинаторика».

Итак, комбинаторика – это раздел математики, в котором изучаются все возможные способы перестановки цифр, предметов, элементов чего-либо. А комбинаторные задачи – это задачи, которые требуют перебора всех возможных вариантов (а по-другому, комбинаций) и подсчёта их количества.

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

Четверо мальчишек: Вова, Гриша, Дима и Лёша – решили устроить турнир по шахматам. Сколько партий будет сыграно, если каждый из ребят сыграет по одному разу со всеми остальными?

Это и есть пример комбинаторной задачи.

Давайте решим эту задачу. Сделаем это перебором всех возможных вариантов. Сначала обозначим каждого мальчика буквой: Вова – В, Гриша – Г, Дима – Д, Лёша – Л. Теперь будем составлять пары.

Итак, Вова сыграет с Гришей, с Димой и с Лёшей. Гриша уже сыграл с Вовой, а значит, ему осталось сразиться с Димой и с Лёшей. Дима уже соревновался с Вовой и с Гришей, а значит, ему осталось сразиться только с Лёшей. Лёша уже сыграл с каждым из участников турнира.

Получается, что участников турнира – 4, а партий будет сыграно 6.

Ребята, предлагаю вам решить эту задачу с помощью рисунков – графов. Для этого снова обозначим мальчиков буквами В, Г, Д и Л. Для наглядности буквы расставим как бы по кругу. Начнём соединять линиями буквы, обозначающие имена участников турнира. Вова сыграет с Гришей, с Димой и с Лёшей. Мы видим, что Гриша уже сыграл с Вовой. Следовательно, ему осталось сыграть с Димой и с Лёшей. Дима уже соревновался с Вовой и с Гришей. Значит, ему осталось сыграть только с Лёшей. Лёша уже сыграл и с Вовой, и с Гришей, и с Димой. Вот такой граф у нас получился.

Буквы, обозначающие имена мальчиков – это вершины графа, а линии, соединяющие их, – рёбра графа. Каждое ребро соединяет две вершины графа. При этом важно помнить, что точки пересечения рёбер не являются вершинами графа.

У нашего графа 6 рёбер. Это значит, что если каждый из четырёх ребят сыграет по одному разу со всеми остальными, то всего будет сыграно 6 партий.

Ребята, давайте представим, что появился ещё один участник турнира – Петя. То есть теперь в турнире по шахматам участвуют не 4 человека, а 5.

Вову обозначим буквой В, Гришу – буквой Г, Диму – буквой Д, Лёшу – буквой Л, а Петю – буквой П.

Теперь будем составлять пары. Вова сыграет с Гришей, с Димой, с Лёшей и с Петей. Гриша уже сыграл с Вовой, а значит, ему осталось сыграть с Димой, с Лёшей и с Петей. Дима уже соревновался с Вовой и с Гришей, а значит, ему осталось сразиться с Лёшей и с Петей. Лёша сыграл с Вовой, с Гришей и с Димой, следовательно, ему осталось сыграть только с Петей. Петя уже сыграл с каждым из участников турнира.

Добавился один игрок, а партий будет сыграно на 4 больше.

Эту задачу можно решить и с помощью графа. Для этого сначала обозначим мальчиков соответствующими буквами. А затем будем составлять пары.

Вова сыграет с Гришей, с Димой, с Лёшей и с Петей. Гриша уже сыграл с Вовой. Следовательно, ему осталось сыграть с Димой, с Лёшей и с Петей. Дима соревновался с Вовой и с Гришей. Значит, ему осталось сыграть с Лёшей и с Петей. Лёша сыграл и с Вовой, и с Гришей, и с Димой. Получается, что ему осталось сыграть только с Петей. Петя уже сыграл и с Вовой, и с Гришей, и с Димой, и с Лёшей. Вот такой граф у нас получился.

У этого графа 10 рёбер. Это значит, что если каждый из пяти ребят сыграет в шахматы по одному разу со всеми остальными, то всего будет сыграно 10 партий.

Друзья, мы с вами решили каждую из задач и перебором, и с помощью графов. Но есть ещё один способ решения таких задач.

Давайте вернёмся ко второй задаче. Посмотрите на пары, которые образовались при решении методом перебора.

Нам известно, что в турнире по шахматам участвуют 5 человек. Обратите внимание, что пар, где первой стоит буква В, – 4, то есть на одну меньше количества участников. Это потому, что Вова не создаст пары сам с собой.

Пар, где первой стоит буква Г, – 3, то есть на одну меньше, чем пар с буквой А на первом месте. Это потому, что Гриша не создаст пары сам с собой, а пара с Вовой уже создана.

Пар, где первой стоит буква Д, – 2, то есть на одну меньше, чем пар с буквой Г на первом месте. Это потому, что Дима сам с собой пары не создаст, а пара с Вовой и пара Гришей уже созданы.

Пара, где первой стоит буква Л, всего одна. Ведь Лёша не создаст пары сам с собой, а пары с Вовой, с Гришей и с Димой уже созданы.

А вот пар, где первой стоит буква П, нет. Ведь Петя сам с собой пары не создаст, а со всеми остальными ребятами пары уже созданы.

Итак, участников турнира по шахматам – 5. А партий будет сыграно, если каждый из ребят сыграет по одному разу со всеми остальными: 4 плюс 3 плюс 2 плюс 1 равно 10.

Ребята, а теперь представьте, что в шахматном турнире будет участвовать не 5 человек, а, например, 10. Тогда первое слагаемое на 1 меньше количества участников, то есть 9. Второе слагаемое на 1 меньше первого, то есть 8. Третье слагаемое на 1 меньше второго, то есть 7. Продолжим прибавлять все числа в порядке убывания до 1. Затем вычислим и в результате получим 45.

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

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

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

Даны три цифры – 7, 8 и 9. Сколько различных трёхзначных чисел можно составить, используя в каждом числе все три цифры?

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

Итак, нам даны три цифры. В первую очередь составим все числа с 7 в разряде сотен. Это будут числа 789 и 798.

Составим все числа с 8 в разряде сотен. Это будут числа 879 и 897.

Теперь ставим в разряд сотен 9. Это будут числа 978 и 987.

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

Следующая задача. Даны четыре цифры – 2, 4, 6 и 8. Сколько различных трёхзначных чисел можно составить, используя в каждом числе три разные цифры?

У нас есть четыре цифры. Давайте поставим в разряд сотен цифру 2 и составим все возможные трёхзначные числа. Сначала возьмём цифры 4 и 6. Это будут числа 246 и 264. Возьмём цифры 4 и 8. Получаем числа 248 и 284. Возьмём цифры 6 и 8. Получаем числа 268 и 286. Таким образом, мы перебрали все возможные числа с 2й в разряде сотен. Их 6.

Теперь поставим в разряд сотен цифру 4 и составим все возможные трёхзначные числа. Сначала возьмём цифры 2 и 6. Это будут числа 426 и 462. Возьмём цифры 2 и 8. Получаем числа 428 и 482. Возьмём цифры 6 и 8. Получаем числа 468 и 486. Мы перебрали все возможные числа с 4 в разряде сотен. Их, как и чисел с 2 в разряде сотен, получилось 6.

Ребята, я думаю, вы догадались, что чисел с 6 в разряде сотен тоже получится 6. Также получится 6 чисел с 8 в разряде сотен.

Таким образом, с каждой из четырёх цифр в разряде сотен, мы составили по 6 трёхзначных чисел. Тогда всего получилось 6 умножить на 4, то есть 24 трёхзначных числа. Причём в каждом из них все три цифры разные.

Получается, что, переставляя между собой три предмета, можно получить 6 комбинаций. Если бы в двух последних задачах среди предложенных цифр был 0, то конечно чисел получилось бы меньше.

Например, возьмём цифры 0, 5 и 9. Составим из них двузначные числа, используя в каждом числе две разные цифры. Итак, 50, 59, 90 и 95.

Давайте составим из этих цифр трёхзначные числа. Причём в каждом числе будем использовать три разные цифры. Итак, 509, 590, 905 и 950.

У нас получилось 4 двузначных числа и 4 трёхзначных числа, так как цифра 0 не может стоять в наибольшем разряде числа.

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

Друзья, на этом время, отведённое на нашу встречу, заканчивается. Пора прощаться. До свидания. До новых встреч.