Обобщение задачи Р.Г. Женодарова

[Alexander Evnin]

В 1996 г. на турнире Савина и в 2006 г. на Заочном конкурсе учителей математики
предлагалась задача Р.Г. Женодарова (несколько в иной формулировке):

В некоторых клетках поля размером $100\times100$ расставлены мины,
при этом каждая клетка (в том числе и заминированная) граничит по стороне
ровно с одной заминированной клеткой. Сколько расставлено мин?

Авторское решение годилось и для квадратного поля $4k\times4k$

Я предложил участникам математического конкурса в ЮУрГУ (https://vk.com/topic-6779920_28792598)
рассмотреть общий случай доски $m\times n$.

Кое-какие результаты были получены. Например, уcтановлено, что можно расставить мины для полей размером

$4\times(5k+1)$, $4\times(5k+2)$, $8\times(9k+1)$, $8\times(9k+6)$, $8\times(9k+8)$, $(5k+4)\times(5n+4)$.

Есть предположение о том, что если мины расставить можно, то
их количество определено однозначно.

Итак, для каких $m$ и $n$ можно расставить требуемым образом мины?

[svv]

С периодом $7$ ещё ничего не было?

Картинка показывает, как расставить мины на полях $6\times(7k+1)$ (жёлтый прямоугольник).
Если прямоугольник обрезать слева на две клеточки, как показывают стрелки, получим расстановку для полей $6\times(7k+6)$, а если и слева, и справа, то для $6\times(7k+4)$.

[12d3]

Alexander Evnin в сообщении #1145889 писал(а):

$(5k+4)\times(5n+4)$.

Не могли бы вы показать, как на доске $9 \times 9$ расставляется? А то у меня выходит, что нельзя расставить.

[Alexander Evnin]

Да, с полем $(5k+4)\times(5n+4)$ я ошибся. Пример был неверный.

Мне удалось доказать, что для поля $n\times n$ расстановка мин возможна тогда и только тогда, когда $n$ чётно.

Кроме того, есть примеры для следующих полей:
$4\times (5i+j)$, $j=1, 2, 4$;
$6\times (7i+j)$, $j=1, 4, 6$;
$8\times (9i+j)$, $j=1, 6, 8$.

[Alexander Evnin]

Павел Хворых на основе результатов компьютерных экспериментов выдвинул следующую гипотезу.

Пусть $2\le n \le m$.
Тогда расстановка мин на поле $n\times m$ возможна тогда и только тогда, когда:
1) $n$ - чётно.
2) $m$ представляется в виде $(n+1)k + d$, где $k$ - натуральное, $d = -3, -1, 1$.

Как видно, эта гипотеза обобщает представленные выше наблюдения.

Доказательство п. 1 не слишком сложное.

Мне удалось также доказать достаточность в п.2. Схема здесь такая.

Поле $n\times m$ собирается из одинаковых блоков размером $n\times (n-2)$,
между которыми вставки размером $n\times 3$, а по краям могут быть окантовки размером $n\times 2$.
Блок $(n+2)\times n$ получается из блока $n\times (n-2)$ добавлением окантовок слева и справа
и последующим поворотом на 90 градусов.

Осталось доказать необходимость п.2!