Задача 116677

Темы:    [ Числовые таблицы и их свойства ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 5 Классы: 7,8,9

Условие

Автор: Раскина И.В.

В клетках таблицы m×n расставлены числа. Оказалось, что в каждой клетке записано количество соседних с ней по стороне клеток, в которых стоит единица. При этом не все числа – нули. При каких числах m и n, больших 100, такое возможно?

Решение

  По условию, если в клетке стоит единица, то ровно в одной из соседних клеток написана единица. Это означает, что единицы образуют прямоугольники 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.

Ответ

Для любых.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	75
Год	2012
класс
Класс	8
задача
Номер	6