Question

Сколькими способами можно раскрасить клетки прямоугольника 2*2019 в два цвета так чтобы никакие три клетки одного цвета не образовали уголок из трёх клеток ?

Answer 1

Пусть мы красим в белый и черные цвета. Заметим, что в любой правильной раскраске должно быть поровну обоих цветов. Иначе в каком-нибудь квадрате 2x2 найдется три клетки одного цвета, что невозможно. Теперь будем по порядку рассматривать квадраты 2x2. Пусть изначально прямоугольника покрашен в шахматную расцветку. Для того, чтобы получать новую раскраску будем двигать черные (без ограничения общности - двигая черные мы, грубо говоря, двигаем и белые) клетки (в квадратах, двигаясь слева направо), причем так, чтобы не возникало уголков. Действительно, если они будут возникать, то их придется устранять и тем самым создавать их в квадратах, расположенных правее и в конце концов упремся. Таким образом, для первого квадрата существует три движения (включая тождественную перестановку). Для второго квадрата существует два варианта - если мы двигали черную клетку, стоящую в пересечении первого и второго квадратов, то движений 2, если нет - то три. Итак, можно построить дерево (см. рис.). При переходе по стрелке мы умножаем числа, стоящие в вершинах. В конце концов, числа до которых нельзя добраться, складываем. Итог - кол-во способов. Докажем по индукции, что искомое количество равно $3\times 5^{n-1}$, где n - номер уровня (ступени).

База очевидна: при n=1 результат 3, что верно.

Переход: пусть для некоторого n=k верно. Докажем, что верно и для n=k+1. Рассмотрим k+1-ый уровень. Количество троек равно количеству двоек. Поэтому каждое слагаемое, входящее в сумму, которая равна $3\times 5^{k-1}$ можно умножить сначала  на тройки, а потом на двойки, что равнозначно $3\times 5^{k-1}\times (3+2)=3\times 5^{k}$, переход доказан.

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

Имеем $2018$ квадратов, а, стало быть, уровней. $K=2\times(3\times 5^{2017})=6\times5^{2017}$;

Ответ: $6\times5^{2017}$