Имеется клетчатая бумага неограниченных размеров со стороной клетки, равной 1. Шаблоном размера k называется всякая плоская фигура, составленная путем соединения концами друг с другом k параллельных или перпендикулярных отрезков длины 1. Если существует отрезок длины 0,5, полностью размещаемый на шаблоне, то точки шаблона, общие с точками между концами этого отрезка, называются внутренними.
Найдите все шаблоны, которыми можно покрыть все линии клетчатой бумаги (шаблоны можно поворачивать и переворачивать). При покрытии разрешается использовать шаблоны одного вида, причем никакие два шаблона не могут иметь общих внутренних точек.
Сначала выясним, какие вообще могут быть шаблоны. Очевидно, что при k = 2 имеется 2 вида шаблонов:
При k=3 имеется 5 видов шаблонов:
Оказывается, все линии клетчатой бумаги можно покрыть любым из перечисленных выше шаблонов, кроме шаблона вида
Докажем последнее. Пусть требуемое покрытие существует. Рассмотрим одно наложение такого шаблона на клетчатую бумагу. Из условия задачи и расположения первого шаблона следует, что пунктирные линии должны быть покрыты двумя другими шаблонами, но тогда волнистые линии без наложения внутренних точек шаблонов покрыть нельзя. Решение для остальных шаблонов показано ниже: