6. Баба Яга готовит зелье. Рецепт подразумевает, что в зелье должны попасть:
• не более 5 лягушек (возможно, 0);
• чётное число волчьих зубов (возможно, 0);
• кратное шести число драконьих чешуек (возможно, 0);
• ровно 2025 ингредиентов.
Сколькими способами Баба Яга может приготовить зелье? Порядок добавления
ингредиентов неважен
Задача: найти количество способов приготовить зелье при следующих условиях:
- не более 5 лягушек: f ∈ {0,1,2,3,4,5}
- чётное число волчьих зубов: w чётное, w ≥ 0
- кратное шести число драконьих чешуек: s = 6b, b ≥ 0
- всего ингредиентов ровно 2025: f + w + s + t = 2025, где t ≥ 0 — оставшиеся ингредиенты
Пояснение и решение
1) Переобозначения
- Пусть w = 2a (a ≥ 0)
- Пусть s = 6b (b ≥ 0)
- Тогда условие равно f + 2a + 6b ≤ 2025, а остаток ингредиентов t = 2025 − (f + 2a + 6b) автоматически неотрицателен.
2) Для каждого фиксированного f подсчитать количество неотрицательных пар (a, b) таких, что
f + 2a + 6b ≤ 2025.
Перепишем через N = 2025 − f:
2a + 6b ≤ N.
Так как левая часть чётна, а правая может быть нечетной, эквивалентно
a + 3b ≤ ⌊N/2⌋. Пусть
M = ⌊N/2⌋.
Для фиксированного f число пар (a, b) равно
C(M) = количество неотрицательных решений a, b проектающих a + 3b ≤ M.
Это можно посчитать по слоям b: для каждого b ≥ 0 с 3b ≤ M допускается a от 0 до M − 3b, всего (M − 3b + 1) вариантов.
Значит
C(M) = ∑_{b=0}^{⌊M/3⌋} (M − 3b + 1).
3) Вычисление по f = 0..5
- f = 0:
N = 2025, M = ⌊2025/2⌋ = 1012, ⌊M/3⌋ = 337.
C = ∑_{b=0}^{337} (1012 − 3b + 1) = ∑_{b=0}^{337} (1013 − 3b)
= (338)(1013) − 3·(337·338)/2 = 342 394 − 170 859 = 171 535.
- f = 1:
N = 2024, M = ⌊2024/2⌋ = 1012, то же, что и для f = 0.
C = 171 535.
- f = 2:
N = 2023, M = ⌊2023/2⌋ = 1011, ⌊M/3⌋ = 337.
C = ∑_{b=0}^{337} (1011 − 3b + 1) = ∑_{b=0}^{337} (1012 − 3b)
= (338)(1012) − 3·(337·338)/2 = 342 056 − 170 859 = 171 197.
- f = 3:
N = 2022, M = 1011, та же величина, C = 171 197.
- f = 4:
N = 2021, M = ⌊2021/2⌋ = 1010, ⌊M/3⌋ = 336.
C = ∑_{b=0}^{336} (1010 − 3b + 1) = ∑_{b=0}^{336} (1011 − 3b)
= (337)(1011) − 3·(336·337)/2 = 340 707 − 169 848 = 170 859.
- f = 5:
N = 2020, M = 1010, та же величина, C = 170 859.
4) Суммарно по всем f
Сумма = 171 535 + 171 535 + 171 197 + 171 197 + 170 859 + 170 859
= 1 027 182.
Ответ: Баба Яга может приготовить зелье 1 027 182 способами (с учётом того, что порядок добавления ингредиентов не важен).
Дополнение
- Мы считаем различными именно разные целочисленные сочетания количества каждого типа ингредиентов (f, w = 2a, s = 6b, t). В рамках задачи это и есть «различные способы приготовления» (различные количества разных видов).
- Если порядок добавления не важен и сами ингредиенты внутренне не идентичны, данный подход корректно даёт количество вариантов по количествам.
