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}$

Answer 2

Для решения данной задачи посчитаем количество способов раскрасить прямоугольник 2x2019 в два цвета (назовем их, например, черный и белый) без образования уголка из трех клеток одного цвета.

Предположим, что верхняя левая клетка (позиция [1, 1]) квадрата раскрашена в черный цвет. Тогда у нас есть два варианта раскрасить соседнюю клетку ([2, 1]): белым или черным. После этого, для каждой следующей клетки ([1, 2], [2, 2], [1, 3], [2, 3], и так далее), мы будем иметь по два варианта выбора цвета. Таким образом, первые две строки (верхние) прямоугольника имеют 2^2019 возможных раскрасок.

Теперь перейдем к третьей строке ([3, 1] и [3, 2]). Для каждой клетки этой строки у нас есть два варианта цвета, но нам нужно учитывать ограничение, чтобы не образовывался уголок из трех клеток одного цвета. Таким образом, для каждой третьей строки у нас есть только два варианта раскраски, чтобы избежать уголка.

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

Таким образом, общее количество способов раскрасить прямоугольник 2x2019 в два цвета без образования уголка из трех клеток одного цвета будет равно:

2^2019 * 2^2019 = 2^(2019+2019) = 2^4038

Итак, существует 2^4038 способов выполнить раскраску с заданными условиями.