Разбиение плоскости

[AD]

Плоскость разбита на клеточки (то есть \mathbb{Z}^2, бесконечная шахматная доска), на ней дана фигура - конечное число клеточек. Вопрос - можно ли этой фигурой замостить плоскость? То есть придумать алгоритм, позволяющий по фигуре определить, можно ли ее копиями покрыть всю плоскость без наложений (или доказать, что алгоритма не существует ). Фигуру можно двигать, поворачивать, переворачивать.

Дальше - вопросы как всегда: типа неужели до меня никто такую задачу не придумал итп. Пробовал искать в интернете, но удачно составить запрос не получилось - речь шла либо о разбиении "непрерывной" плоскости на многоугольники итп, либо о задачах по программированию о разбиении конечных фигур на более мелкие.

Возможны варианты: та же задача на прямой, в многомерном пространстве, запретить повороты, отражения, требовать от фигуры, чтобы она была связной, односвязной, полиомино, в-некотором-смысле-выпуклой, итп. Просто первый вариант мне кажется наиболее естественным.

Вот несколько простых примеров. Звездочками обозначены клетки фигуры, точками - пустые клетки.

1. Фигура, которой нельзя замостить плоскость:

.....
..**.
.*.*.
.**..
.....

После того, как мы поставили первую такую фигуру, ее центральную клетку уже никак накрыть не удастся. Шесть клеточек - кто меньше?

2. Наименьшая фигура, для которой я еще не знаю ответа - всего четыре клеточки!

........
.*..***.
........

3. Односвязное полиомино, которым нельзя замостить плоскость (это не я придумал)

.......
.*...*.
.*...*.
.*...*.
.*****.
.......

(P.S. Товарищи модераторы! А слово "Код" убрать можно как-нибудь?)

Тривиальное, но обнадеживающее соображение: если из какой-нибудь фигуры A удалось сложить фигуру, подобную фигуре B, то есть отличающуюся от нее растяжением по осям в целое число раз (возможно, в разное по разным осям), и про фигуру B известно, что ей можно замостить плоскость, то то же можно сказать и о фигуре A. Может, удастся найти "достаточно маленькое" количество таких фигур B, к которым все можно сводить?

Ну и так далее. Я этим не занимаюсь , но вроде красивая задачка по дискретной математике.

[Someone]

Ключевые слова для поиска: Голомб, полимино (полиомино).

[AD]

Спасибо Someone! Это книжка такая? Пока не нашел. Там эта задача разбирается?

[Someone]

AD писал(а):

Спасибо Someone! Это книжка такая? Пока не нашел. Там эта задача разбирается?

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

[AD]

Фигурой, про которую я в начале темы не знал решения, замостить плоскость

11.05.2010:

Не скажу, можно или нельзя, потому что предложил этот вопрос как задачку в одну онлайн-олимпиаду.

Но к ответу на основной вопрос "существует ли алгоритм ..." это не приблизило. Наверное, стоит попробовать написать поисковую програмку?... Хотя, наверное, "всё уже украдено до нас" ...