1632
правки
Изменения
м
rollbackEdits.php mass rollback
|{{Определение
|definition=
'''Полимино''' (англ. ''polyomino'') - — плоская геометрическая фигура, состоящая из <tex>n</tex> одноклеточных квадратов, соединенных по сторонам.
}}
|[[file:Polyomino_example.png|300px|right]]
{{Определение
|definition=
'''Замощение плоскости''' (англ. ''tiling'') - — представление плоскости в виде множества непересекающихся полимино.
}}
Пусть дана плоскость <tex>S</tex> и набор полимино <tex>P</tex>, если <tex>\exists ~ f: N \times N \to P</tex> (говорящая по клетке, какому полимино она соответствует) тогда считается, что можно замостить плоскость <tex>S</tex> данным набором.
== Замощение четверти плоскости ==
{{Шаблон:Задача
|definition=
Пусть даны некоторые типы полимино, причем экземпляров каждого типа дается бесконечно много.
Верно ли, что используя любое количество полимино можно полностью замостить без пропусков и выступов четверть плоскости? Поворачивать полимино не разрешено.
}}
{{Теорема
На каждой стороне такого полимино находится определенное число выступов/впадин.
Каждому символу из алфавита, состоянию и паре из состояния и символа сопоставим некоторое уникальное число (можно ограничить <tex>k \le leqslant |\Pi| + |Q| + |\Pi \times Q| + 1</tex>) – это и будет количество выступов/впадин, находящихся на одной стороне полимино.
Будем действовать также как и предыдущем доказательстве, только одновременно будем строить еще и зеркально отраженные полимино так, чтобы их нельзя было никак соединить с изначальными.
Например, можно сделать новое количество выступов/впадин <tex>k' = \mathrm{cur_k } + \mathrm{max_k}</tex>, где <tex>\mathrm{cur_k}</tex> {{---}} количество выступов/впадин у полимино, от которого образовалось текущее, <tex>\mathrm{max_k}</tex> {{---}} максимальное число выступов/впадин у полимино в первой четверти.
[[Файл:Polyomino_bad_case.png]]
