2. (13 баллов) Петя раскрашивает клетчатый прямоугольник размером 6х14. У него 3 краски: белая, серая, черная. Он должен раскрасить клетки так, чтобы соседние клетки были разного цвета, но при этом не было резкой смены цвета, то есть белая и чёрная клетки не могут быть соседними. (Клетки – соседние, если у них есть общая сторона). Сколько способов у Пети раскрасить доску?

Рассмотрим раскраску одной строки. Каждая клетка должна отличаться по цвету от соседней. Так как белая и черная клетки не могут быть соседними, то они должны быть разделены серыми клетками. Для первой клетки у нас есть 3 варианта цвета. Для второй клетки остается 2 варианта, так как цвет не должен совпадать с цветом первой клетки. Для каждой следующей клетки цвет также должен отличаться от предыдущей. Так как черная и белая клетки не могут быть соседними, то каждая следующая клетка должна иметь цвет, который отличается от предыдущей клетки и также должен быть не черным, если предыдущая клетка белая, или не белым, если предыдущая клетка черная. Если соседняя клетка была серой, то можно красить в любой цвет, отличный от серого. Таким образом, последовательность цветов в строке может быть, например, БСБСБС..., ЧСЧСЧС..., СБСБСБ... или СЧСЧСЧ.... Т.е. для первой клетки есть 3 варианта, а для всех остальных - только 2. Для доски 6x14 получается 6 строк. Для первой строки есть 3 варианта выбора цвета первой клетки, а дальше 2 варианта. Всего для одной строки есть $$3*2^{13}$$ варианта. Для каждой строки варианты независимы, поэтому итоговое количество способов равно $$(3 * 2^{13})^6 = 3^6 * 2^{78}$$. $$3^6=729$$, значит, способов раскраски $$729 * 2^{78}$$ Ответ: $$729 * 2^{78}$$