Раскрасочная комбинаторика

[Ktina]

Сколькими способами можно закрасить несколько клеток в квадрате 10х10 так, чтобы у каждой клетки было ровно две соседних по стороне закрашенных клетки?

[chessar]

Одним единственным:
$ \begin{array}{|*{10}{c|}} \hline \times&\times&\times&\times&\times&\times&\times&\times&\times&\times\\ \hline \times&&&&&&&&&\times\\ \hline \times&&\times&\times&\times&\times&\times&\times&&\times\\ \hline \times&&\times&&&&&\times&&\times\\ \hline \times&&\times&&\times&\times&&\times&&\times\\ \hline \times&&\times&&\times&\times&&\times&&\times\\ \hline \times&&\times&&&&&\times&&\times\\ \hline \times&&\times&\times&\times&\times&\times&\times&&\times\\ \hline \times&&&&&&&&&\times\\ \hline \times&\times&\times&\times&\times&\times&\times&\times&\times&\times\\ \hline \end{array} $
Или я задачу не так понял?

[Ktina]

chessar в сообщении #623613 писал(а):

Одним единственным:

Или я задачу не так понял?

Задачу Вы верно поняли.
У меня тоже этот же способ вышел, и интуитивно он кажется единственным, вот только доказать не получается.

[_Ivana]

+1 за один показанный способ. Только что раскрашивал сидел. Выбор варианта угловой клетки однозначно задает нам все дальнейшие цвета всех клеток. Пустая угловая клетка приводит к противоречию, значит варианта не существует. Закрашенная - приводит к единственному варианту, показанному выше.

[chessar]

_Ivana в сообщении #623619 писал(а):

Пустая угловая клетка приводит к противоречию, значит варианта не существует.

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

Я так понимаю, для произвольного квадрата $n\times n$ раскраска либо единственна (для чётных $n$), либо вообще не существует (для нечётных $n$).

[_Ivana]

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

ЗЫ я и так уже сначала пишу а потом думаю, и все равно опаздываю

[chessar]

_Ivana в сообщении #623623 писал(а):

ЗЫ я и так уже сначала пишу а потом думаю, и все равно опаздываю

Да я пока отвечал про путь к единственному варианту, в голове сразу обобщения стал думать и не проверяя записал, потом проверил - и всё верно оказалось.
Можно еще для прямоугольника $m\times n$ подумать (например для $4\times6$ не существует такой раскраски).
Сдаётся мне, что только для квадратов с чётной строной существует по единственному варианту раскрасок.

[_Ivana]

chessar в сообщении #623624 писал(а):

Можно еще для прямоугольника $m\times n$ подумать

С меньшей стороны прямоугольника у нас однозначно заполняются концентрические квадраты, подобные показанным выше. Далее сбоку к ним можно пристроить любое количество таких-же квадратов через столбец пустых клеток. Т.е. если стороны прямоугольника $a = 2n, b = ka + (k-1)$, то вроде должно получиться.