Задача 73782

Темы:    [ Замощения костями домино и плитками ] [ Инварианты ] [ Деление с остатком ] [ Делимость чисел. Общие свойства ]

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

Условие

Автор: Туркевич Э.

Квадрат 6×6 нужно заполнить 12 плитками, из которых k имеют форму уголка, а остальные  12 – k  – прямоугольника. При каких k это возможно?

Решение

  Если k чётно, то квадрат можно заполнить уголками и прямоугольниками: разбиваем его на прямоугольники 2×3, каждый из которых можно разбить как на два уголка, так и на два прямоугольника. При  k = 5, 7, 9 и 11, заполнение также возможно (см. рис. 1).
  Остаётся разобрать случаи  k = 1  и  k = 3. 

  1)  k = 1.  Занумеруем строки квадрата от 1 до 6 снизу вверх и сопоставим каждой клеточке прямоугольника (или уголка) номер строки, в которой она находится. Нетрудно заметить, что сумма номеров строк (по клеточкам) для любого прямоугольника делится на 3, а для любого уголка – не делится. Сумма номеров строк квадрата (по клеточкам) делится на 3, значит, при  k = 1  укладка невозможна.
  2)  k = 3.  Занумеруем строки и столбцы квадрата как в 1), а столбцы – слева направо. Сопоставим каждой из фигур два числа: сумму номеров строк и сумму номеров столбцов, в которых находятся клеточки этой фигуры. Для прямоугольников оба эти числа делятся на 3, а для уголков – не делятся. Остатки, получающиеся при делении на 3 чисел, соответствующих уголкам, определяются лишь видом уголка и не меняются, если передвигать уголок по квадрату не переворачивая.
  Сумма номеров строк и сумма номеров столбцов (по клеткам) для всего квадрата делятся на 3; следовательно, укладка квадрата тремя уголками и девятью прямоугольниками возможна только тогда, когда все три уголка одного вида. В силу симметрии квадрата будем считать, что все уголки такие, как на рис. 2.
  Покажем теперь, что полосу ширины 6 и высоты n невозможно уложить, если использовать прямоугольники и уголки только такого вида (при условии, что хоть один уголок использован).
  Предположим противное. Покажем тогда, что если возможна укладка полосы 6×n, то возможна укладка полосы 6×m, где m – некоторое число, меньшее n.
  Занумеруем строки полосы снизу вверх. Из рис. 3 следует, что если в первых трёх строках полосы нет клетки, принадлежащей уголку, то у полосы можно отрезать первую строку, то есть можно сделать индуктивный шаг.

  Пусть есть уголок, содержащий клетку первой или второй строки. Возьмём самый правый из таких уголков. Ясно, что красная клетка на рис. 4 (уголок, изображенный на нём, – самый правый) покрыта горизонтальным прямоугольником, иначе укладка вылезет за пределы полосы. Синяя клетка либо лежит за пределами полосы, либо покрыта вертикальным прямоугольником – (здесь есть два случая – а) и б)). В случае б) укладка невозможна – это видно из рисунка. В случае а) раз синяя клетка покрыта вертикальным прямоугольником, то чёрная и зелёная клетки тоже покрыты вертикальными прямоугольниками. Перестроив конфигурацию, как показано на рис. 5, мы "поднимем" уголок так, что он уже не будет содержать клеток первых двух строк.

  Итак, нам осталось рассмотреть, что будет в том случае, когда клетки первой и второй строк покрыты только прямоугольниками. Из рис. 3 следует, что во всех случаях, кроме изображённых на рис. 6, индуктивный переход возможен. Рассмотрим эти два случая.
  Ясно, что красная клетка покрыта вертикальным прямоугольником. Но тогда и чёрная клетка тоже покрыта вертикальным прямоугольником. Тогда зелёная клетка покрыта вертикальный прямоугольником. После этого легко сообразить, что жёлтые клетки также покрыты вертикальными прямоугольниками. Значит, уголок можно поднять (рис. 7).

  Таким образом, нам удалось убрать все уголки из первых трёх строк полосы. Мы уже убедились, что в этом случае от полосы 6×n можно перейти к полосе 6×m, где  m < n.
  Остаётся убедиться, что при достаточно малых m такое покрытие невозможно. Это очевидно, если  m < 3.

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

журнал
Название	"Квант"
год
Год	1974
выпуск
Номер	2
Задача
Номер	М247