Question

У мамы 2 одинаковых апельсина, 3 одинаковых банана и 4 одинаковых ананаса. Каждый день в течение девяти дней она выдавала дочери по одному фрукту. Сколькими способами она могла это сделать, так чтобы фрукты не повторялись более трех раз подряд?

Answer 1

Ответ: В первый день мама могла дать любой из фруктов. То есть максимум 3 варианта. Такое же количество вариантов будет сохраняться если мама будет давать дочери тот фрукт, количество которого преобдладает. 3 ананаса, 2 банана и 1 апельсин - 6 дней. На седьмой она также дает один из 3 фруктов, но количество дальнейших вариантов снижается до 2. На восьмой день она дает 1 из 2 фруков, а на девятый день уже последний оставшийся. Имеем:

3*3*3*3*3*3*3*2*1=4374 варианта

Пошаговое объяснение:

Answer 2

Чтобы решить эту задачу, мы можем воспользоваться методом динамического программирования. Обозначим количество способов, которыми мама может выдавать фрукты дочери в течение n дней так, чтобы фрукты не повторялись более трех раз подряд, как dp[n].

Построим рекуррентное соотношение для dp[n]. Для этого рассмотрим два случая:

1. Если на n-й день мама выдает тот же фрукт, что и на (n-1)-й день, то на (n-1)-й день она выдала разные фрукты, и тогда dp[n] = dp[n-1] (так как нарушение условия не более трех фруктов подряд).
2. Если на n-й день мама выдает другой фрукт, то на (n-1)-й день она также выдала другой фрукт, и на (n-2)-й день она выдала разные фрукты. Тогда dp[n] = dp[n-1] + dp[n-2] (так как нарушение условия не более трех фруктов подряд).

Исходные значения: dp[1] = 9 (9 дней, 9 разных фруктов); dp[2] = 9 * 8 = 72 (9 дней, на 2-й день должен быть другой фрукт).

Теперь вычислим dp[n] для n = 3, 4, ..., 9, используя рекуррентное соотношение:

dp[3] = dp[2] + dp[1] = 72 + 9 = 81 dp[4] = dp[3] + dp[2] = 81 + 72 = 153 dp[5] = dp[4] + dp[3] = 153 + 81 = 234 dp[6] = dp[5] + dp[4] = 234 + 153 = 387 dp[7] = dp[6] + dp[5] = 387 + 234 = 621 dp[8] = dp[7] + dp[6] = 621 + 387 = 1008 dp[9] = dp[8] + dp[7] = 1008 + 621 = 1629

Таким образом, мама может выдавать фрукты дочери в течение 9 дней так, чтобы фрукты не повторялись более трех раз подряд, 1629 способами.