Question

Буратино решил покрасить забор из 8 досок тремя красками. При этом он хочет, чтобы любые две соседние доски были покрашены в разные цвета, и все три цвета использовались. Сколькими способами Буратино может покрасить забор?

Answer 1

I - доска

первую красим в любой цвет из 3, другие в один из 2-ух оставшихся

I I I I I I I I

3 2 2 2 2 2 2 2

цифры означают кол-во способов покраски доски

все это перемножаем, получается 2⁷*3=384

Answer 2

Для покраски забора из 8 досок, используя три различные цвета и с условием, что любые две соседние доски должны быть покрашены в разные цвета, можно использовать метод динамического программирования.

Пусть dp[n] - количество способов покрасить забор из n досок с учетом указанных условий.

Для начала, рассмотрим базовые случаи:

1. dp[1] = 3 (так как у нас есть 3 цвета и всего 1 доска).
2. dp[2] = 9 (так как у нас есть 3 цвета для первой доски и 2 оставшихся цвета для второй доски).

Теперь мы можем использовать динамическое программирование для расчета dp[i] для i > 2:

dp[i] = (dp[i-1] + dp[i-2]) * 2

Поскольку для каждой новой доски, добавленной к забору, есть два возможных цвета (первый и второй) и для каждой новой комбинации двух досок, добавленных к забору, также есть два возможных цвета (первый и второй), общее количество способов увеличивается вдвое.

Таким образом, для покраски забора из 8 досок, используя три различных цвета и с условием, что любые две соседние доски должны быть покрашены в разные цвета, количество способов будет:

dp[8] = (dp[7] + dp[6]) * 2 = ((dp[6] + dp[5]) * 2 + (dp[5] + dp[4]) * 2) * 2 = (((dp[5] + dp[4]) * 2 + (dp[4] + dp[3]) * 2) * 2 + ((dp[4] + dp[3]) * 2 + (dp[3] + dp[2]) * 2) * 2) * 2 = (((((dp[4] + dp[3]) * 2 + (dp[3] + dp[2]) * 2) * 2 + ((dp[3] + dp[2]) * 2 + (dp[2] + dp[1]) * 2) * 2) * 2 + ((((dp[3] + dp[2]) * 2 + (dp[2] + dp[1]) * 2) * 2 + (dp[2] + dp[1]) * 2) * 2) * 2) * 2 = 204

Таким образом, Буратино может покрасить забор 8 досок 204 различными способами при условиях, указанных в задаче.