Олимпиадная задача: Примеры и контрпримеры с таблицей m×n, классы 7–9

  По условию, если в клетке стоит единица, то ровно в одной из соседних клеток написана единица. Это означает, что единицы образуют прямоугольники 1×2. При этом никакие два прямоугольника не граничат по стороне и не пересекаются.

  Кроме того, клетка, не принадлежащая таким прямоугольникам, не может граничить ровно с одним прямоугольником. Иначе в этой клетке была бы написана единица, и клетка принадлежала бы одному из прямоугольников 1×2.

  Допустим, нам удалось расположить в таблице m×n прямоугольники 1×2 так, что

     1) прямоугольники не граничат по стороне и не пересекаются;

     2) если клетка не принадлежит ни одному из прямоугольников, то она граничит не с одним прямоугольником (то есть с 0, 2, 3 или 4 прямоугольниками).

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

  Если m и n дают остаток 1 при делении на 3, прямоугольники можно расположить так, как изображено на следующем рисунке.

  К такой таблице можно снизу добавить одну или две полоски ширины 5, изображённые на следующем рисунке.

  При этом условия 1 и 2, наложенные на прямоугольники, не нарушатся. Это позволяет заполнить таблицуm×n, еслиnдаёт остаток 1 при делении на 3, аm– произвольное число, большее 14. Действительно, еслиmделится на 3, нужно заполнить таблицу (m–5)×nтак, как показано на верхнем рисунке, и добавить полоску ширины 5, а еслиmдаёт остаток 2 при делении на 3 – заполнить таблицу (m–10)×nкак на верхнем рисунке и добавить две полоски ширины 5.   К любой из полученных таблиц можно справа добавить одну или две полоскиm×5. В зависимости от того, какой остаток даёт числоmпри делении на 3, нужно выбрать одну из полосок, изображённых на трёх нижних рисунках.

  Это позволяет заполнять любые таблицыm×n, где  m, n> 14.