Комментарии 22
2^23
50%, как в анекдоте. А если считать что сценарии из 1 равновероятны (об этом нигде явно не говорится), то тоже 50%
Вот тут уже надо считать.
Вроде просто. Если количество окошек произвольное, то для первого дня число сценариев это сумма биномиальных коэффициентов. Должно получиться 2^23
Вторая задача решается так же, как первая. Только окошко 23 открыто. Итого получаем 2^22/2^23=50%
Третья гораздо интереснее. Можно представить календарь как бусы из 23 частей, которые надо разрезать 23 разрезами, причем два и более разрезов могут проходить между теми же двумя бусинами (ситуация, когда несколько дней подряд ничего нового не открывается). Последний разрез гарантированно после последней бусинки (надо ведь календарь открыть весь!), поэтому можно его отбросить. Остаётся 22 разреза, мест для разреза 24 (22 между бусинами, один в начале и один в конце). Это уже сочетания с повторениями, k=24, n=22. Если я ничего в процессе рассуждений не перепутала, ответ C из 45 по 22.
Тут разрез после последней бусины будет только если в последний день ничего не открывали.
Ну то есть если бусин, например, 3, то разрезов два. И ситуация «по бусине каждый день» будет выглядеть иметь разрезы только внутри бус.
Но вы в правы в том, что это по сути сочетания с повторениями и итоговая формула такая, но там n=23 и k=23. То есть 23 бусины и 22 разреза.
Сейчас подумаю ещё раз. Не могу пока понять, почему "разрез после последней бусины будет только если в последний день ничего не открывали". Может, у нас какой-то разный образ в голове?
Я это вижу так. Упростим. Два дня, две бусины (окошка).
Варианты и как я их интерпретирую. Справа начало, слева конец, разрезы(дни) |, бусинки(окошки) 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 это правильный ответ.
Я делала слева направо, но это тут не должно быть важно.
Но для двух бусин вообще хватит одного разреза.
Тогда «слотов» 3.
00| — обе бусины в перый и ничего во второй
0|0 — одну в первый, одну во второй
|00 — ничего в первый и две во второй
В вашей версии с двумя разрезами второй разрез не обязателен, можно вот так без него.
Для задачи 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)); // 4116715363800Если N количество окошек, K количество дней, то ответ C из (N+K-1) по K-1.
да, согласен
Ворвусь с ноткой духоты, там не k-1, а n-1. Но так как в данном случае и то, и то равно по 23, то разницы почти не видно 😁
То есть там C_{n+k-1}^{n-1} или C_{n+k-1}^{k}
2^23
Тут зависит от вероятностного пространства. Например, если считать, что Аня каждый день выбирает случайное подмножество клеток , которые откроет, то ответ 1/2. Если же Аня заранее для каждой клетки определяет, в какой день она ее откроет, то ответ 1/23.
Тут очевидно. C(55,23) вроде, лень думать
Задача 3.
Итак у нас n=23 дня и столько же окошек.
Пусть мы хотим распаковать календарь за k дней (в смысле ровно в k дней мы что-то открываем). Тогда выбрать k дней есть 
способов, а разбить (с учетом порядка) окошки на k порций 
. Итого имеем полную формулу 
или воспользовавшись https://en.wikipedia.org/wiki/Vandermonde's_identity получаем ответ 
Ну и в конкретном случае это 45!/(23!*22!) = 4116715363800
Первые две задачи решаются элементарно (ответ 2^23 и 50%), а вот над третьей надо подумать.
Для календаря на 1 день есть 1 способ, это тривиально.
Для календаря на 2 дня есть 3 способа, это очевидно.
Для календаря на 3 дня есть 10 способов, это нетрудно прикинуть в уме.
Для календаря на 4 дня есть 35 способов, для этого уже надо поднапрячь мозги.
1, 3, 10, 35...
(2^0), (2^1)+1, (2^3)+2, (2^5)+3...
Видна последовательность (2^(2n-3))+n-1
(2^(46-3))+23-1 = (2^42)+22. Примерно 4,4 триллиона. Вот и ответ.
Что-то с формулой не то, есть проблема при n=1.
Потом ок, но уже для 5 окошек такая поледовательность перестала бы работать, там 126 способов в действительности, а по вашей формуле получается 132.
Но с последовательностями хитро, там же надо в общем виде доказывать, что именно так всегда будет работать.
Сломал мозг
Клёво, надо почаще извилины разминать
Задачка веселая, но причем тут математика не совсем понятно. Математика - это про моделирование и разрешение закономерностей и процессов, в математике вообще считать ничего не надо, как правило)) а числа, перестановки и всякого рода счет - это скорее арифметика)
А посчитать? Задачка для тех, кто влюблен в математику