338
правок
Изменения
Нет описания правки
[[file:Tiling_example.png|300px]]
== Постановка задачи Замощение четверти плоскости ==
Пусть даны некоторые типы полимино, причем экземпляров каждого типа дается бесконечно много.
Верно ли, что используя любое количество полимино можно полностью замостить без пропусков и выступов четверть плоскости? Поворачивать полимино не разрешено.
}}
== Замощение половины плоскости ==
{{Теорема
|statement=
Задача о замощении половины плоскости полимино неразрешима.
|proof=
Будем действовать также как и предыдущем доказательстве, только одновременно будем строить еще и зеркально отраженные полимино так, чтобы их нельзя было никак соединить с изначальными.
Например, можно покрасить стороны новых полимино в другой цвет и ввести правило, по которому можно соединять полимино, только если цвета их общей стороны совпадают.
[[Файл:Polyomino_bad_case.png]]
Сделаем так для всех полимино кроме первого ряда. Для него добавим специальное соединение, к которому подходит только зеркально отраженное полимино.
[[Файл:Polyomino_init_2.png]]
}}
== Замощение целой плоскости ==
{{Теорема
|statement=
Задача о замощении половины плоскости полимино неразрешима.
|proof=
Аналогично замощению половины плоскости.
}}
== Ссылки ==
* [http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%B8%D0%BC%D0%B8%D0%BD%D0%BE Полимино — Википедия]
* [https://www.cs.duke.edu/courses/fall08/cps234/projects/tilings.pdf The tiling problem]
* [http://www.univ-orleans.fr/lifo/Members/Nicolas.Ollinger/talks/2008/03/turku.pdf The domino problem]
