Привет! Меня зовут Диана, и я математик, поэтому везде вижу числа. Этот текст я подготовила для МТС Диджитал.
Немного обо мне: выпускница мехмата МГУ, несу математику в мир со, страшно подумать, 2007 года. Обожаю находить связи между ежедневными ситуациями и разными математическими теориями. А еще — придумывать задачи с безобидными формулировками, но не всегда простыми решениями. Сегодня как раз принесла вам такие — теперь вам есть чем заняться в романтический вечер много вечеров!
Так что устройтесь поудобнее со своей второй половинкой или в компании себя любимого — и призовите на помощь смекалку! Ответы опубликую через 10 дней — 24 февраля. Погнали!
Вводные
Бренд по уходу за собой выпустил адвент-календарь на 23 отделения: с 14 февраля по 8 марта включительно. В каждом отделении — один продукт. Считается, что нужно открывать по порядку и по одному окошку в день, но кто же следует этим правилам?
Аня купила для себя такой календарь и решила, что можно открывать и по несколько окошек в день. Или ни одного. Или вообще все сразу в один день. А еще — что если открывать несколько окошек в один день, то не важно, в каком порядке.
Три задачки в одной
Ну а теперь предлагаю вам найти ответы на три вопроса:
Сколько есть возможных сценариев для первого дня, если можно открывать окошки из любой части календаря?
Аня этого не знает, но в последнем окошке лежит ее любимый крем. Какова вероятность, что она откроет именно это окошко прямо в первый день?
Сколько есть способов распаковать весь календарь не более чем за 23 дня, если открывать окошки можно только продвигаясь по порядку от первого к последнему? При этом каждый день можно открывать сколько угодно окошек. Например, в первый день — окошки номер 1 и 2, во второй — ни одного, в третий — окошки 3, 4, 5 и 6, и так далее.
Как уже написала выше, подробные решения опубликую через 10 дней — 24 февраля. А пока приглашаю порассуждать в комментариях!
Комментарии (20)
VanillaBerry
14.02.2025 08:43Вроде просто. Если количество окошек произвольное, то для первого дня число сценариев это сумма биномиальных коэффициентов. Должно получиться 2^23
VanillaBerry
14.02.2025 08:43Вторая задача решается так же, как первая. Только окошко 23 открыто. Итого получаем 2^22/2^23=50%
Третья гораздо интереснее. Можно представить календарь как бусы из 23 частей, которые надо разрезать 23 разрезами, причем два и более разрезов могут проходить между теми же двумя бусинами (ситуация, когда несколько дней подряд ничего нового не открывается). Последний разрез гарантированно после последней бусинки (надо ведь календарь открыть весь!), поэтому можно его отбросить. Остаётся 22 разреза, мест для разреза 24 (22 между бусинами, один в начале и один в конце). Это уже сочетания с повторениями, k=24, n=22. Если я ничего в процессе рассуждений не перепутала, ответ C из 45 по 22.
violent_muse Автор
14.02.2025 08:43Тут разрез после последней бусины будет только если в последний день ничего не открывали.
Ну то есть если бусин, например, 3, то разрезов два. И ситуация «по бусине каждый день» будет выглядеть иметь разрезы только внутри бус.
Но вы в правы в том, что это по сути сочетания с повторениями и итоговая формула такая, но там n=23 и k=23. То есть 23 бусины и 22 разреза.
VanillaBerry
14.02.2025 08:43Сейчас подумаю ещё раз. Не могу пока понять, почему "разрез после последней бусины будет только если в последний день ничего не открывали". Может, у нас какой-то разный образ в голове?
Я это вижу так. Упростим. Два дня, две бусины (окошка).
Варианты и как я их интерпретирую. Справа начало, слева конец, разрезы(дни) |, бусинки(окошки) o
||oo (ничего не открыли никогда)
|o|o (в первый день ничего, во второй одну, одна осталась)
|oo| (в первый день ничего, во второй сразу обе)
o|o| (по одной в день)
И тд и тп.
Мне нужно, чтобы в конце был один разрез, потому что открыть надо все. Поэтому последний фиксируем и забываем. Остаётся N-1 "палочек". Мест вокруг бусинок всё ещё K+1 (ничто не мешает другим палочкам попадать в самый конец, если все открыли раньше и в конце несколько дней подряд не открывают, например вариант oo|| допустим). Итого распределить N-1 палочек по K+1 местам с возможностью поставить несколько на одно место. !!!!!(*) Вот здесь я в прошлый раз ошиблась, для стандартной формулы распределений с повторениями взяв k=K+1, n=N-1 (буквы похожие ведь). А надо наоборот. Итого С (N-1 + K+1 - 1) (N-1) = (по свойствам коэффициентов) = C(N+K-1)(K)
Попробую проверить для малых значений. Например, два дня и три бусинки. C_4^3=4. Так и есть
OOOII (в первый день открыли все)
OOIOI (в первый день две, потом одну)
OIOOI (одна, потом две)
IOOOI (открыли все сразу, но во второй день)
Вот теперь вроде сошлось все. Вообще у Ани много свободы (ишь ты, сразу весь адвент открыть), отсюда много вариантов и тревог, при этом относительно простых для подсчёта. Надо этой Анне жизнь усложнить (или упростить?) немного, добавив правил.
(*) Перечитала ещё раз коммент свой ниже, там N окошки, K дни. А в этом комментарии вверху N дни, K окошки. Так что я не ошиблась в прошлый раз, просто другие обозначения использовала. Но, как ни крути, C_45^22=C_45^23 это правильный ответ.
violent_muse Автор
14.02.2025 08:43Я делала слева направо, но это тут не должно быть важно.
Но для двух бусин вообще хватит одного разреза.
Тогда «слотов» 3.
00| — обе бусины в перый и ничего во второй
0|0 — одну в первый, одну во второй
|00 — ничего в первый и две во второй
В вашей версии с двумя разрезами второй разрез не обязателен, можно вот так без него.
VanillaBerry
14.02.2025 08:43Всё правильно, я для задачи один разрез фиксирую (он ограничен тем условием, что окошки-бусины должны быть исчерпаны) и забываю. А на "картинке" рисую как есть. Теперь всё сошлось.
Alexandroppolus
14.02.2025 08:43Для задачи 3 выходит довольно простая рекуррентная формула. Пусть у нас N окошек и K дней в запасе. F(n, k) - искомая формула.
F(0, k) = 1
F(n, 1) = 1
F(n, k) = sum(i = 0...n) F(i, k-1)
Суть в том, что после первого дня может остаться от 0 до n неоткрытых окошек. Ну и можно посчитать это дело методом динамического программирования, т.е. рекурсия+мемоизация
upd: щас подумал, получается что
F(n, k) = (sum(i = 0...n-1) F(i, k-1)) + F(n, k-1) = F(n-1, k-1) + F(n, k-1)Похоже, это и вправду биномиальный коэффициент, как в комментарии выше
function F(n, k) { const arr = [[]]; for(let i = 1; i <= k; i++) { arr.push([]); for(let j = 0; j <= n; j++) { arr[i][j] = i === 1 || j === 0 ? 1 : arr[i-1][j] + arr[i][j-1]; } } return arr[k][n]; } console.log(F(23, 23)); // 4116715363800VanillaBerry
14.02.2025 08:43Если N количество окошек, K количество дней, то ответ C из (N+K-1) по K-1.
kipar
2^23
50%, как в анекдоте. А если считать что сценарии из 1 равновероятны (об этом нигде явно не говорится), то тоже 50%
Вот тут уже надо считать.