Всем привет! Это Диана, математик и автор команды спецпроектов МТС Диджитал. В День всех влюбленных я опубликовала трехчастную задачу про адвент-календарь и обещала показать решения через 10 дней. Час настал! Спойлер: подходов к решению будет несколько. Первые два пункта несложные, а третий поинтереснее. Смотрите, проверяйте себя и приходите обсуждать в комментарии!
Для удобства скажем, что окошки занумерованы не датами, а числами от 1 до 23.
Первый вопрос
Сколько есть возможных сценариев для первого дня, если можно открывать окошки из любой части календаря?
Порассуждаем. В первый день можно открыть любое количество окошек — от 0 до 23 включительно. Случаи с открытием 0 окошек и 23 окошек уникальны (то есть это можно сделать единственным способом), а вот все остальные количества — нет. То есть если Аня открыла два окошка, это могли быть первое и второе или пятое и седьмое — любая пара окошек. Сколько существует таких пар? А троек? А четверок?
Знатоки комбинаторики сразу опознали — речь идет о количестве сочетаний. Именно сочетания позволяют нам вычислить, сколькими способами можно выбрать, например, пару из 23 элементов, когда порядок не важен.
Общая формула для вычисления количества способов выбрать k элементов из n выглядит так:
Ну а дальше всего делов-то, надо вычислить
в общем, все возможные варианты выбора наборов разной величины. А потом сложить их, не забыв C023 и C2323, которые равны по единичке (можете проверить).
К счастью, делать это вручную не нужно! Есть формула о том, что сумма всевозможных количеств сочетаний Ckn со всеми значениями 0⩽k⩽n всегда равна 2n.
Модная запись:
У этого факта есть несколько доказательств. Можно сказать, что это сумма всех биномиальных коэффициентов в n-ой строке треугольника Паскаля.
Но можно рассмотреть и другой подход, не комбинаторный, а через теорию множеств.
Представьте множество из 23 элементов. В первый день Аня может выбрать ноль элементов или любой один, или любые два и так далее. Те элементы, которые Аня выберет в первый день — это некоторое подмножество исходного множества. Нам подходит абсолютно любое подмножество — включая пустое множество и само исходное множество целиком. Есть известный факт, что если исходное множество состояло из n элементов, то множество всех его подмножеств состоит из 2n элементов. У этой штуки даже специальное название есть — булеан.
В нашем случае это число равно 223 = 8 388 608. Всего-навсего а что так мало! И это только количество сценариев для первого дня, что же будет дальше…
Второй вопрос
Аня этого не знает, но в последнем окошке лежит ее любимый крем. Какова вероятность, что она откроет именно это окошко прямо в первый день?
Сначала смешные рассуждения: нууу в первый день она или откроет последнее окошко, или нет — так что вероятность равна 0.5, расходимся. Вы не поверите, но примерно так все и есть.
Для начала получим результат предыдущего пункта другим способом. Возможно вы считали как раз так.
Там у нас получился булеан, множество всех подмножеств. И его мощность (то есть количество элементов) будет 2n как раз потому, что в первый день каждое из окошек либо будет открыто, либо нет. То есть для любого окошка есть 2 исхода и так для каждого из 23 окошек. Первое или открыто, или нет, второе или открыто, или нет, и так далее.
Перемножаем количество исходов для каждого окошка по правилу произведения и получаем 223 способа прожить первый день:
Можно кстати рассуждать и с помощью двоичной записи. Если открытие окошка обозначается единичкой, а не-открытие — нулем, то нас интересует количество всевозможных двоичных чисел длины 23, при условии, что можно начинать и с нулей.
Окей, это мы посчитали все возможные исходы первого дня, а благоприятные в этом случае — те, в которых обязательно открыто последнее окошко. То есть 23-значное число с единичкой на конце. Таких будет уже 223, ведь исход для последнего окошка уже зафиксирован. И поэтому искомая вероятность равна:
Кстати, если бы любимый крем лежал в каком-то другом окошке, например, 13-ом — вероятность была бы такой же.
Третий вопрос
Сколько есть способов распаковать весь календарь не более чем за 23 дня, если открывать окошки можно только продвигаясь по порядку от первого к последнему? При этом каждый день можно открывать сколько угодно окошек.
Конечно, совершенно не факт, что мы откроем весь календарь за первый день. Более того — скорее всего этого не случится, ведь из 8 388 608 сценариев только один соответствует полному открыванию всего.
Нам надо открыть 23 окошка, движемся мы по порядку. Но сколько окошек открывается в каждый из дней — неизвестно.
Давайте рассмотрим календарь попроще — из 3 окошек. Как его можно открывать? В каждый из 3 дней мы открываем от 0 до 3 окошек. Всего есть 10 способов, я выписала все подходящие «кодировки» по убыванию. Здесь на n-ом месте стоит количество открытых окошек в n-ый день:
300
210
201
120
111
102
030
021
012
003
А теперь рассмотрим другой подход.
Представьте, что вам надо разделить эти 3 окошка палочками-разделителями. Между любыми двумя соседними окошками либо стоит палочка (это означает, что кончился один день и начался другой), либо не стоит палочка (это означает, что еще продолжается текущий день).
Сколько нужно палочек, чтобы разделить 3 дня? 2 штуки. А сколько есть мест, в которые можно ставить эти палочки? Тут интереснее — таких мест 5. Почему так: у вас есть 3 окошка и 2 палочки, в сумме это 5 слотов. В каждом слоте может быть как окошко, так и палочка. Задача, которую мы тут по сути решаем — понимаем, сколько есть способов расположить 2 палочки по 5 слотам.
По формуле это:
Сходится с нашим перебором выше!
В случае большого календаря у нас 23 окошка и 22 палочки, то есть всего 45 слотов. И вот что мы имеем:
Математические эстеты, возможно, заметили: это та же формула, что получается для поиска количества сочетаний с повторениями. Это немного другой подход: например, есть 3 элемента, и тебе надо выбрать 3 из них, при этом каждый элемент может быть выбран несколько раз. Собственно, этот подход хорошо виден, если посмотреть «перебор» трехзначных чисел на картинке выше. И формула там такая:
Но мне нравится именно история с палочками. Она помогает лучше понять ситуацию, чем просто ниспосланная свыше формула — которую, кстати, чаще всего доказывают именно через эти палочки.
Вот и все, спасибо за внимание! А если хочется еще поупражняться в открывании календарей, то вот вам бонусный вопрос: сколько есть способов открыть календарь, если можно «перепрыгивать» и открывать любые окошки в любом количестве в каждый из дней? Пишите ответы в комментариях, все посмотрю.
