От монеток до площадей: решаем задачи на комбинаторику и вероятность с помощью невероятных многочленов
Сергей ЮРКИН,
учитель математики и физика МАОУ «Лицей №131» Вахитовского района г. Казани
Мастер-класс по производящим функциям (далее - ПФ) для тех, кто любит когда все складывается.
Представьте инструмент, который превращает сложные комбинаторные вопросы в простые операции с многочленами. Инструмент, который одинаково легко считает способы набрать сумму на кубиках и вероятность попасть в геометрическую фигуру. Мы пройдём путь от базовых примеров к неочевидным применениям.
Нашим инструментом является производящая функция:
где
Часть 1. Одна скромная монетка.
Сколькими способами можно получить ровно 5 орлов бросая монетку 10 раз?
Обычное решение: знакомый биноминальный коэффициент .
Решение с помощью ПФ: рассмотрим один бросок монетки. Его исход можно представить в виде многочлена орёл - , решка - . ПФ - .
Оказывается, что при помощи производящей функции можно узнать количество различных исходов для двух бросков, для этого необходимо рассмотреть квадрат ПФ: Можно заметить, что коэффициенты перед членами квадрата ПФ точь-в-точь означают количество различных способов получить необходимое число исходов: 2 орла - (о,о), 1 орёл - (о, р) и (р, о) и 0 орлов - (р, р).
По аналогии таким образом можно посчитать все возможные способы выпадения различного количества орлов для любого числа бросков, в том числе и для 10. Для 10 бросков мы рассмотрим 10-ю степень ПФ:
.
Коэффициент перед равен 252, что и означает число всех возможных различных способов получения 5 орлов при 10 бросках.
Вывод: ПФ для последовательности независимых испытаний - это произведение ПФ для каждого испытания. ПФ преобразует задачу «сколько есть комбинаций?» в задачу «какой коэффициент при ?». При решении данной задачи была использована формула бинома Ньютона для возведения двучлена в натуральную степень.
Часть 2. Игральный кубик и суммы.
Сколькими способами можно получить сумму очков, равную 13, бросив 3 стандартных игральных кубика?
Обычное решение: перебор всех возможных исходов и всех исходов, удовлетворяющих условию - громоздкий метод, требующий аккуратного перебора всех вариантов с учётом возможных перестановок.
Решение с ПФ: рассмотрим исходы одного кубика - это числа 1,2,3,4,5,6, которые можно представить в виде многочлена - . Три независимых броска приводят нас к идее умножения этого многочлена на самого себя трижды, получаем:
Находим коэффициент перед , откуда сразу становится понятно, что ответ равен 21.
Вывод: можно заметить, что наш метод не только отвечает на точечные вопросы, как тот, на который мы ответили, но и видно, что мы получаем полную картину распределения всех возможных исходов и их частот, в этом примере видим, что самые вероятные суммы, которые можно получить за бросок трех кубиков равен 10 и 11. С другой стороны, несмотря на наглядность метода, ученик может столкнуться со сложностями возведения многочлена в степень большую двух. На обычных уроках в ранних классах далеко не всегда ученики самостоятельно решают подобные задачи, из-за чего может быть совсем непонятно, как решить нашу задачу. Для решения нашей задачи можно использовать такие инструменты как свёртка или табличная интерпретация, хотя данные методы также могут занять некоторое время, но по сложности ничуть не уступают классическим методам.
Часть 3. Геометрическая вероятность: стрелок и мишень.
Стрелок ведёт стрельбу по мишени радиуса , поделённую на 4 кольца толщины и «яблочко» радиуса . За попадание в «яблочко» стрелок получает 5 очков, за попадание в кольца стрелок получает большее число очков от 4 до 1. Необходимо найти вероятность того, что стрелок за 3 выстрела заработает 12 очков, при условии, что вероятность попадания по мишени равномерная, и стрелок независимо от числа попыток попадает в случайную точку на мишени.
Обычное решение: для решения требуется найти вероятность попадания в каждое из всех возможных колец с очками, затем рассмотреть все возможные исходы попадания в количество очков, в сумме дающие 12 очков - громозкое решение требующее аккуратности в переборе и арифметике.
Решение с помощью ПФ: по аналогии с обычным решением, нас сперва интересует вероятность попадания в каждое из всех возможных количество очков, получим:
По аналогии с кубиками, после нахождения всех нужных вероятностей ввиду того, что нам нужно суммировать очки, опять представим распределение всех исходов в виде многочлена:
Теперь видим, что ответ на наш вопрос будет содержать коэффициент от многочлена . Наша задача сводится к возведению в куб многочлена, получим:
Получаем ответ, что за 3 выстрела стрелок получит 12 очков с вероятностью
Вывод: в этой задаче, ПФ показала ответ на наш вопрос и как и в предыдущих случаях заодно дала целостную картину того, как распределяется вероятность каждого события, можно было ответ ответить на любой из всех возможных вопросов касаемо вероятности 1 события, нескольких событий, а ещё можно увидеть самое вероятное количество очков при 3 выстрелах. Очевидной трудностью является процесс возведения многочлена в степень, как уже говорилось, существуют доступные способы, как это можно сделать вручную, однако для демонстрации решения учителем данного примера в классе или для домашней работы, можно использовать электронно-вычислительные ресурсы, например «wolfram alpha».
В заключении подведем итог. ПФ это универсальный метод для решения задач комбинаторики или теории вероятностей при необходимости считать суммы или искать наиболее вероятные исходы, причем для многократных чисел бросков или опытов. ПФ охватывает широкий спектр задач от броска монетки до сложных задач геометрической вероятности.
Задание на перспективу: попробуйте решить задачу: «Сколькими способами можно разменять 100 рублей монетами в 1, 2, 5 и 10 рублей, используя 20 монет?» при помощи ПФ.