Исследовать самовоспроизводимые полимино и найти для них коэффициент самовоспроизводимости.

Многие из нас хоть раз сталкивались с головоломками в той или иной форме их проявления. У людей они издревле вызывают интерес. Одним из видов головоломок являются полимино. Полимино или n-мино— это односвязная фигура, составленная из n квадратов. Односвязность означает, что каждый входящий в нее квадрат имеет по крайней мере одну сторону, общую с другим входящим в нее же квадратом.

Тема настоящей работы принадлежит к так называемой комбинаторной или дискретной геометрии — раздела геометрии, в котором изучаются комбинаторные свойства геометрических объектов и связанные с ними конструкций. В элементарной геометрии известна задача о самовоспроизводимых или самопорождющих фигурах, из нескольких конгруэнтных копий которых можно сложить такую же фигуру, но большего размера. В моей работе ставится общая задача о нахождении для любого n всех самовоспроизводимых n-мино. Если какое-то конкретное n-мино самовоспроизводимо, то естественно ввести понятие коэффициента самовоспроизводимости k, под которым понимается наименьшее количество копий данного n-мино, из которых можно сложить такое же n-мино, но большего размера. А так же возникает задача о нахождении числа k для разных самовоспроизводимых полимино.

Для частных случаев наша общая задача, несомненно, встречалась и встречается в различных задачах на разрезание. Но в общей постановке задача является новой. При малых значениях n задача ожидаемо оказалась простой и решается простым перебором всех случаев. Для больших значений n наша задача, как и абсолютное большинство задач комбинаторной геометрии, представляется крайне сложной в силу резкого возрастания вариантов перебора и в общем виде вряд ли может быть решена. Задача является сложной даже для конкретных достаточно больших значений n, например, для n=7. В настоящей работе исследование доведено до значения n=6.

В данной работе мною были исследованы самовоспроизводимые полимино и были получены следующие основные результаты:

1. Перечислены все самовоспроизводимые n-мино для n=1,2,3,4,5,6.
2. Для всех найденных самовоспроизводимых полимино вычислены коэффициенты самовоспроизводимости k.
3. Подсчитана доля самовоспроизводимых n-мино, и выяснено, что c увеличением n число самовоспроизводимых n-мино уменьшается.