Question

Есть прямоугольная доска размером 3х94 клеток. У Марины есть банка с синей краской. Она хочет покрасить 279 клеток доски так, чтобы из каждой клетки доски до любой другой можно было бы добраться, двигаясь только по синим клеткам (можно передвигаться только между клетками, имеющими общую сторону). Сколько способов покраски доски Марине не подойдут?

Answer 1

3·94 = 282

То есть всего 3 клетки не будут закрашены. Не подойдут те вариант покраски доски, при которых непокрашенные клетки будут "блокировать" покрашенные. Это возможно только в 4 случаях. Примеры "блокирования" на рисунке.

Answer 2

Чтобы определить количество способов покраски доски, которые не подойдут Марине, можно воспользоваться принципом дополнения.

Сначала найдем общее количество способов покраски доски. У нас есть 279 клеток, которые нужно покрасить. Каждую клетку можно покрасить в синий или оставить непокрашенной. Таким образом, у нас есть 2 возможности для каждой клетки. Так как клеток на доске 3*94 = 282, то общее количество способов покраски доски будет равно 2^282.

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

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

Если мы покрасим первую клетку в синий цвет, то у нас останется 278 клеток, которые нужно покрасить таким образом, чтобы из каждой клетки до любой другой можно было бы добраться, двигаясь только по синим клеткам. Таких способов покраски будет столько же, сколько способов покраски доски размером 3х93 клетки.

Если же мы оставим первую клетку непокрашенной, то у