6. Баба Яга готовит зелье. Рецепт подразумевает, что в зелье должны попасть: • не более 5 лягушек (возможно, 0); • чётное число волчьих зубов (возможно, 0); • кратное шести число…

Задача: найти количество способов приготовить зелье при следующих условиях:

• не более 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). В рамках задачи это и есть «различные способы приготовления» (различные количества разных видов).
• Если порядок добавления не важен и сами ингредиенты внутренне не идентичны, данный подход корректно даёт количество вариантов по количествам.