ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .