Плоскость разбита на клеточки (то есть
, бесконечная шахматная доска), на ней дана фигура - конечное число клеточек. Вопрос - можно ли этой фигурой замостить плоскость? То есть придумать алгоритм, позволяющий по фигуре определить, можно ли ее копиями покрыть всю плоскость без наложений (или доказать, что алгоритма не существует
). Фигуру можно двигать, поворачивать, переворачивать.
Дальше - вопросы как всегда: типа неужели до меня никто такую задачу не придумал итп. Пробовал искать в интернете, но удачно составить запрос не получилось - речь шла либо о разбиении "непрерывной" плоскости на многоугольники итп, либо о задачах по программированию о разбиении конечных фигур на более мелкие.
Возможны варианты: та же задача на прямой, в многомерном пространстве, запретить повороты, отражения, требовать от фигуры, чтобы она была связной, односвязной, полиомино, в-некотором-смысле-выпуклой, итп. Просто первый вариант мне кажется наиболее естественным.
Вот несколько простых примеров. Звездочками обозначены клетки фигуры, точками - пустые клетки.
1. Фигура, которой нельзя замостить плоскость:
Код:
.....
..**.
.*.*.
.**..
.....
После того, как мы поставили первую такую фигуру, ее центральную клетку уже никак накрыть не удастся. Шесть клеточек - кто меньше?
2. Наименьшая фигура, для которой я еще не знаю ответа - всего четыре клеточки!
Код:
........
.*..***.
........
3. Односвязное полиомино, которым нельзя замостить плоскость (это не я придумал)
Код:
.......
.*...*.
.*...*.
.*...*.
.*****.
.......
(P.S. Товарищи модераторы! А слово "Код" убрать можно как-нибудь?)
Тривиальное, но обнадеживающее соображение: если из какой-нибудь фигуры A удалось сложить фигуру, подобную фигуре B, то есть отличающуюся от нее растяжением по осям в целое число раз (возможно, в разное по разным осям), и про фигуру B известно, что ей можно замостить плоскость, то то же можно сказать и о фигуре A. Может, удастся найти "достаточно маленькое" количество таких фигур B, к которым все можно сводить?
Ну и так далее. Я этим не занимаюсь
, но вроде красивая задачка по дискретной математике.
