Loading [MathJax]/jax/output/SVG/jax.js

Республиканская олимпиада по математике, 2016 год, 9 класс


Клетчатую таблицу n×n (где n2) покрывают уголками, состоящими из трёх единичных клеток (уголок можно неоднократно поворачивать на 90) так, чтобы выполнялись следующие условия:
1) каждая клетка таблицы покрыта хотя бы одним из уголков;
2) две соседние по стороне клетки, покрытые одним уголком, не могут быть одновременно покрыты другим.
Каково наибольшее возможное число уголков в таком покрытии? ( Ильясов С. )
посмотреть в олимпиаде

Комментарий/решение:

Комментарии от администратора Комментарии от администратора №1.     Ответ. n(n1).
Будем рассматривать каждый уголок в виде наложения двух доминошек: горизонтального и вертикального (см. рис. ниже).


Тогда можно считать, что таблица покрыта доминошкоми по следующим двум правилам:
1) каждая клетка таблицы покрыта хотя бы одной доминошкой.
2) никакая доминошка полностью не покрывает никакую другую.
При таком условии каждая строка или столбец длины n покрываются не более чем n1 доминошкой 2×1 или 1×2 соответственно. Поэтому всего доминошек не более чем 2n(n1). Но каждому уголку соответствует 2 доминошки, поэтому число уголков не более чем n(n1).
Пример. Строить пример будем по индукции с шагом два.
1) Когда n=2 и n=3 привести не трудно.
2) Пусть для каждого kn мы показали.
3) Покажем для k=n+2.
Рассмотрим ободок ширины 2, полученный из таблицы (n+2)×(n+2) путем вырезания центрального квадрата (n2)×(n2). Поставим уголок (такой как на рис. выше) в нижний левый угол, назовем его первым. Затем переместим его на одну клетку вверх, в новом месте поставим такой же уголок и т.д. В итоге левая часть ободка покрыта n+1 уголками. Затем переместим первый уголок на одну клетку вправо,в новом месте поставим такой же уголок и т.д. В итоге левая и нижняя часть ободка покрыты 2n+1 уголками. Повернем ободок на 180 и проделаем ту же операцию. Таким образом ободок покрыт 4n+2 уголками.
Заметим, что каждый такой уголок покрывает не более одной клетки из центрального квадрата n×n, это означает, что никакой уголок полностью лежащий в центральном квадрате n×n, не противоречит условиям покрытия. Значит в силу предположения индукции центральный квадрат покрывается n2n уголками, т.е. таблицу (n+2)×(n+2) покрыта n2n+4n+2=n2+3n+2=(n+2)(n+1) уголками.

  0
9 года назад #

Две соседние по стороне клетки

Здесь имеется в виду сторона таблицы?

  1
9 года назад #

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