Полимино

Полимино, или полиомино (англ. polyomino) — плоские геометрические фигуры, образованные путём соединения нескольких одноклеточных квадратов по их сторонам. Это полиформы, сегменты которых являются квадратами.

Фигуру полимино можно рассматривать как конечное связное подмножество бесконечной шахматной доски, которое может обойти ладья.

Названия полимино

Полимино (n-мино) носят названия по числу n квадратов, из которых они состоят:

n	Название	n	Название
1	мономино	6	гексамино
2	домино	7	гептамино
3	тримино	8	октамино
4	тетрамино	9	нонамино или эннеомино
5	пентамино	10	декамино

История

Полимино использовались в занимательной математике по крайней мере с 1907 года, а известны были ещё в древности. Многие результаты с фигурами, содержащими от 1 до 6 квадратов, были впервые опубликованы в журнале «Fairy Chess Review» в период с 1937 по 1957 г., под названием «проблемы рассечения» (англ. «dissection problems»). Название «полимино» или «полиомино» (англ. polyomino) было придумано Соломоном Голомбом в 1953 году и затем популяризировано Мартином Гарднером.

В 1967 году журнал «Наука и жизнь» опубликовал серию статей о пентамино. В дальнейшем в течение ряда лет публиковались задачи, связанные с полимино и другими полиформами.

Обобщения полимино

В зависимости от того, разрешается ли переворачивание или вращение фигур, различаются следующие три вида полимино:

• двусторонние полимино, или свободные полимино (англ. free polyominoes) — полимино, которые разрешается поворачивать и переворачивать;
• односторонние полимино (англ. one-sided polyominoes) — полимино, которые разрешается поворачивать в плоскости, но не разрешается переворачивать;
• фиксированные полимино (англ. fixed polyominoes) — полимино, которые не разрешается ни поворачивать, ни переворачивать.

В зависимости от условий связности соседних ячеек различаются:

• полимино — наборы квадратов, которые может обойти визирь;
• псевдополимино, или полиплеты — наборы квадратов, которые может обойти король;
• квазиполимино — произвольные наборы квадратов бесконечной шахматной доски.

В следующей таблице собраны данные о числе фигур полимино и его обобщений. Число квази-n-мино равно 1 при n = 1 и ∞ при n > 1.

n	полимино					псевдополимино
	двусторонние			односторонние	фиксированные	двусторонние	односторонние	фиксированные
	все	с отверстиями	без отверстий
	A000105	A001419	A000104	A000988	A001168	A030222	A030233	A006770
1	1	0	1	1	1	1	1	1
2	1	0	1	1	2	2	2	4
3	2	0	2	2	6	5	6	20
4	5	0	5	7	19	22	34	110
5	12	0	12	18	63	94	166	638
6	35	0	35	60	216	524	991	3832
7	108	1	107	196	760	3031	5931	23 592
8	369	6	363	704	2725	18 770	37 196	147 941
9	1285	37	1248	2500	9910	118 133	235 456	940 982
10	4655	195	4460	9189	36 446	758 381	1 514 618	6 053 180
11	17 073	979	16 094	33 896	135 268	4 915 652	9 826 177	39 299 408
12	63 600	4 663	58 937	126 759	505 861	32 149 296	64 284 947	257 105 146

Полиформы

Полиформы — обобщение полимино, ячейками которого могут быть любые одинаковые многоугольники или многогранники. Иначе говоря, полиформа — плоская фигура или пространственное тело, состоящая из нескольких соединённых копий заданной основной формы.

Плоские (двумерные) полиформы включают в себя полиамонды, сформированные из равносторонних треугольников; полигексы, сформированные из правильных шестиугольников; полиаболо, состоящие из равнобедренных прямоугольных треугольников, и другие.

Примеры пространственных (трёхмерных) полиформ: поликубы, состоящие из трёхмерных кубов; полироны (англ. polyrhons), состоящие из ромбододекаэдров.

Полиформы также обобщаются на случай более высоких размерностей (например, сформированные из гиперкубов — полигиперкубы).

Задачи

Покрытия прямоугольников конгруэнтными полимино

Порядок полимино P — минимальное число конгруэнтных копий P, достаточное для того, чтобы сложить некоторый прямоугольник. Для полимино, из копий которых нельзя сложить ни одного прямоугольника, порядок не определён. Порядок полимино P равен 1 тогда и только тогда, когда P — прямоугольник.

Если существует хотя бы один прямоугольник, который можно покрыть нечётным числом конгруэнтных копий P, полимино P называется нечётным полимино; если же прямоугольник можно сложить только из чётного числа копий P, P называется чётным полимино.

Эта терминология была введена в 1968 году Д. А. Кларнером.

Существует множество полимино порядка 2; примером являются так называемые L–полимино.

Нерешённые проблемы математики: Существует ли полимино, порядок которого — нечётное число?

Полимино порядка 3 не существует; доказательство этого было опубликовано в 1992 году. Любое полимино, из трёх копий которого можно составить прямоугольник, само является прямоугольником и имеет порядок 1. Неизвестно, существует ли полимино, порядок которого — нечётное число, большее 3.

Существуют полимино порядка 4, 10, 18, 24, 28, 50, 76, 92, 312; существует конструкция, позволяющая получить полимино порядка 4s для любого натурального s.

Нерешённые проблемы математики: Какова наименьшая возможная нечётная кратность покрытия прямоугольника непрямоугольным полимино?

Кларнеру удалось найти непрямоугольное полимино порядка 2, из 11 копий которого можно составить прямоугольник, причём никакое ме́ньшее нечётное число копий этого полимино не может покрыть прямоугольник. На октябрь 2015 года неизвестно, существует ли непрямоугольное полимино, из 9, 7 или 5 копий которого можно составить прямоугольник; неизвестны также какие-либо другие примеры полимино с минимальной нечётной кратностью покрытия 11 (кроме найденного Кларнером).

Минимальные области

Минимальная область (англ. minimal region, minimal common superform) для заданного набора полимино — полимино наименьшей возможной площади, содержащее каждое полимино из данного набора. Задача нахождения минимальной области для набора двенадцати пентамино была впервые поставлена Т. Р. Доусоном в журнале Fairy Chess Review в 1942 году.

Для набора 12 пентамино существуют две минимальные девятиклеточные области, представляющие собой 2 из 1285 нонамино:

  ###     ###
#####    #####
  #       #

См. также

• Пентамино
• Полиамонды
• Полигексы
• Полиаболо
• Кубики сома
• Танграм

Литература

• Голомб С.В. Полимино = Polyominoes / Пер. с англ. В. Фирсова. Предисл. и ред. И. Яглома. — М.: Мир, 1975. — 207 с.
• Генри Э. Дьюдени. Кентерберийские головоломки = The Canterbury Puzzles and Other Curious Problems / Пер. с англ. Ю.Н.Сударева. — М.: Мир, 1979. — 353 с.
• Гарднер М. Математические головоломки и развлечения = Mathematical Puzzles and Diversions / Пер. с англ. Ю.А.Данилова. — М.: Мир, 1971. — 511 с.
• Гарднер М. Математические новеллы / Пер. с англ. Ю.А.Данилова. Под ред. Я.А.Смородинского. — М.: Мир, 1974. — 456 с.

Ссылки

• Антология Мартина Гарднера [stepanov.lk.net/gardner/hex/hex13.html Полимино]
• Библиотека по математике [mathemlib.ru/books/item/f00/s00/z0000022/index.shtml Полимино]
• RSDN: Этюды для программистов [www.rsdn.ru/forum/etude/211642.all Количество полимино]
• Хайдар Нурлигареев [elementy.ru/problems/1053/Parkety_iz_polimino Паркеты из полимино]
• Michael Reid [cflmath.com/~reid/Polyomino/ Polyomino page]
• Andrew Clarke The Poly Pages [www.recmath.com/PolyPages/PolyPages/Polyominoes.html Polyominoes]
• David Eppstein The Geometry Junkyard [www.ics.uci.edu/~eppstein/junkyard/polyomino.html Polyominoes]
• Miroslav Vicher [www.vicher.cz/puzzle/ Puzzles Pages]
• Kevin L. Gong [www.kevingong.com/Polyominoes/Math.html Polyominoes]

Отрывок, характеризующий Полимино

– Давай сюда. Во важно то!
Дрова наломали, надавили, поддули ртами и полами шинелей, и пламя зашипело и затрещало. Солдаты, придвинувшись, закурили трубки. Молодой, красивый солдат, который притащил дрова, подперся руками в бока и стал быстро и ловко топотать озябшими ногами на месте.
– Ах, маменька, холодная роса, да хороша, да в мушкатера… – припевал он, как будто икая на каждом слоге песни.
– Эй, подметки отлетят! – крикнул рыжий, заметив, что у плясуна болталась подметка. – Экой яд плясать!
Плясун остановился, оторвал болтавшуюся кожу и бросил в огонь.
– И то, брат, – сказал он; и, сев, достал из ранца обрывок французского синего сукна и стал обвертывать им ногу. – С пару зашлись, – прибавил он, вытягивая ноги к огню.
– Скоро новые отпустят. Говорят, перебьем до копца, тогда всем по двойному товару.
– А вишь, сукин сын Петров, отстал таки, – сказал фельдфебель.
– Я его давно замечал, – сказал другой.
– Да что, солдатенок…
– А в третьей роте, сказывали, за вчерашний день девять человек недосчитали.
– Да, вот суди, как ноги зазнобишь, куда пойдешь?
– Э, пустое болтать! – сказал фельдфебель.
– Али и тебе хочется того же? – сказал старый солдат, с упреком обращаясь к тому, который сказал, что ноги зазнобил.
– А ты что же думаешь? – вдруг приподнявшись из за костра, пискливым и дрожащим голосом заговорил востроносенький солдат, которого называли ворона. – Кто гладок, так похудает, а худому смерть. Вот хоть бы я. Мочи моей нет, – сказал он вдруг решительно, обращаясь к фельдфебелю, – вели в госпиталь отослать, ломота одолела; а то все одно отстанешь…
– Ну буде, буде, – спокойно сказал фельдфебель. Солдатик замолчал, и разговор продолжался.
– Нынче мало ли французов этих побрали; а сапог, прямо сказать, ни на одном настоящих нет, так, одна названье, – начал один из солдат новый разговор.
– Всё казаки поразули. Чистили для полковника избу, выносили их. Жалости смотреть, ребята, – сказал плясун. – Разворочали их: так живой один, веришь ли, лопочет что то по своему.
– А чистый народ, ребята, – сказал первый. – Белый, вот как береза белый, и бравые есть, скажи, благородные.
– А ты думаешь как? У него от всех званий набраны.
– А ничего не знают по нашему, – с улыбкой недоумения сказал плясун. – Я ему говорю: «Чьей короны?», а он свое лопочет. Чудесный народ!
– Ведь то мудрено, братцы мои, – продолжал тот, который удивлялся их белизне, – сказывали мужики под Можайским, как стали убирать битых, где страженья то была, так ведь что, говорит, почитай месяц лежали мертвые ихние то. Что ж, говорит, лежит, говорит, ихний то, как бумага белый, чистый, ни синь пороха не пахнет.
– Что ж, от холода, что ль? – спросил один.
– Эка ты умный! От холода! Жарко ведь было. Кабы от стужи, так и наши бы тоже не протухли. А то, говорит, подойдешь к нашему, весь, говорит, прогнил в червях. Так, говорит, платками обвяжемся, да, отворотя морду, и тащим; мочи нет. А ихний, говорит, как бумага белый; ни синь пороха не пахнет.
Все помолчали.
– Должно, от пищи, – сказал фельдфебель, – господскую пищу жрали.
Никто не возражал.
– Сказывал мужик то этот, под Можайским, где страженья то была, их с десяти деревень согнали, двадцать дён возили, не свозили всех, мертвых то. Волков этих что, говорит…
– Та страженья была настоящая, – сказал старый солдат. – Только и было чем помянуть; а то всё после того… Так, только народу мученье.
– И то, дядюшка. Позавчера набежали мы, так куда те, до себя не допущают. Живо ружья покидали. На коленки. Пардон – говорит. Так, только пример один. Сказывали, самого Полиона то Платов два раза брал. Слова не знает. Возьмет возьмет: вот на те, в руках прикинется птицей, улетит, да и улетит. И убить тоже нет положенья.
– Эка врать здоров ты, Киселев, посмотрю я на тебя.
– Какое врать, правда истинная.
– А кабы на мой обычай, я бы его, изловимши, да в землю бы закопал. Да осиновым колом. А то что народу загубил.
– Все одно конец сделаем, не будет ходить, – зевая, сказал старый солдат.
Разговор замолк, солдаты стали укладываться.
– Вишь, звезды то, страсть, так и горят! Скажи, бабы холсты разложили, – сказал солдат, любуясь на Млечный Путь.
– Это, ребята, к урожайному году.
– Дровец то еще надо будет.
– Спину погреешь, а брюха замерзла. Вот чуда.
– О, господи!
– Что толкаешься то, – про тебя одного огонь, что ли? Вишь… развалился.
Из за устанавливающегося молчания послышался храп некоторых заснувших; остальные поворачивались и грелись, изредка переговариваясь. От дальнего, шагов за сто, костра послышался дружный, веселый хохот.
– Вишь, грохочат в пятой роте, – сказал один солдат. – И народу что – страсть!
Один солдат поднялся и пошел к пятой роте.
– То то смеху, – сказал он, возвращаясь. – Два хранцуза пристали. Один мерзлый вовсе, а другой такой куражный, бяда! Песни играет.
– О о? пойти посмотреть… – Несколько солдат направились к пятой роте.


Пятая рота стояла подле самого леса. Огромный костер ярко горел посреди снега, освещая отягченные инеем ветви деревьев.
В середине ночи солдаты пятой роты услыхали в лесу шаги по снегу и хряск сучьев.
– Ребята, ведмедь, – сказал один солдат. Все подняли головы, прислушались, и из леса, в яркий свет костра, выступили две, держащиеся друг за друга, человеческие, странно одетые фигуры.
Это были два прятавшиеся в лесу француза. Хрипло говоря что то на непонятном солдатам языке, они подошли к костру. Один был повыше ростом, в офицерской шляпе, и казался совсем ослабевшим. Подойдя к костру, он хотел сесть, но упал на землю. Другой, маленький, коренастый, обвязанный платком по щекам солдат, был сильнее. Он поднял своего товарища и, указывая на свой рот, говорил что то. Солдаты окружили французов, подстелили больному шинель и обоим принесли каши и водки.
Ослабевший французский офицер был Рамбаль; повязанный платком был его денщик Морель.
Когда Морель выпил водки и доел котелок каши, он вдруг болезненно развеселился и начал не переставая говорить что то не понимавшим его солдатам. Рамбаль отказывался от еды и молча лежал на локте у костра, бессмысленными красными глазами глядя на русских солдат. Изредка он издавал протяжный стон и опять замолкал. Морель, показывая на плечи, внушал солдатам, что это был офицер и что его надо отогреть. Офицер русский, подошедший к костру, послал спросить у полковника, не возьмет ли он к себе отогреть французского офицера; и когда вернулись и сказали, что полковник велел привести офицера, Рамбалю передали, чтобы он шел. Он встал и хотел идти, но пошатнулся и упал бы, если бы подле стоящий солдат не поддержал его.
– Что? Не будешь? – насмешливо подмигнув, сказал один солдат, обращаясь к Рамбалю.
– Э, дурак! Что врешь нескладно! То то мужик, право, мужик, – послышались с разных сторон упреки пошутившему солдату. Рамбаля окружили, подняли двое на руки, перехватившись ими, и понесли в избу. Рамбаль обнял шеи солдат и, когда его понесли, жалобно заговорил:
– Oh, nies braves, oh, mes bons, mes bons amis! Voila des hommes! oh, mes braves, mes bons amis! [О молодцы! О мои добрые, добрые друзья! Вот люди! О мои добрые друзья!] – и, как ребенок, головой склонился на плечо одному солдату.
Между тем Морель сидел на лучшем месте, окруженный солдатами.
Морель, маленький коренастый француз, с воспаленными, слезившимися глазами, обвязанный по бабьи платком сверх фуражки, был одет в женскую шубенку. Он, видимо, захмелев, обнявши рукой солдата, сидевшего подле него, пел хриплым, перерывающимся голосом французскую песню. Солдаты держались за бока, глядя на него.
– Ну ка, ну ка, научи, как? Я живо перейму. Как?.. – говорил шутник песенник, которого обнимал Морель.
Vive Henri Quatre,
Vive ce roi vaillanti –
[Да здравствует Генрих Четвертый!
Да здравствует сей храбрый король!
и т. д. (французская песня) ]
пропел Морель, подмигивая глазом.
Сe diable a quatre…
– Виварика! Виф серувару! сидябляка… – повторил солдат, взмахнув рукой и действительно уловив напев.
– Вишь, ловко! Го го го го го!.. – поднялся с разных сторон грубый, радостный хохот. Морель, сморщившись, смеялся тоже.
– Ну, валяй еще, еще!
Qui eut le triple talent,
De boire, de battre,
Et d'etre un vert galant…
[Имевший тройной талант,
пить, драться
и быть любезником…]
– A ведь тоже складно. Ну, ну, Залетаев!..
– Кю… – с усилием выговорил Залетаев. – Кью ю ю… – вытянул он, старательно оттопырив губы, – летриптала, де бу де ба и детравагала, – пропел он.
– Ай, важно! Вот так хранцуз! ой… го го го го! – Что ж, еще есть хочешь?
– Дай ему каши то; ведь не скоро наестся с голоду то.
Опять ему дали каши; и Морель, посмеиваясь, принялся за третий котелок. Радостные улыбки стояли на всех лицах молодых солдат, смотревших на Мореля. Старые солдаты, считавшие неприличным заниматься такими пустяками, лежали с другой стороны костра, но изредка, приподнимаясь на локте, с улыбкой взглядывали на Мореля.
– Тоже люди, – сказал один из них, уворачиваясь в шинель. – И полынь на своем кореню растет.
– Оо! Господи, господи! Как звездно, страсть! К морозу… – И все затихло.
Звезды, как будто зная, что теперь никто не увидит их, разыгрались в черном небе. То вспыхивая, то потухая, то вздрагивая, они хлопотливо о чем то радостном, но таинственном перешептывались между собой.

Х
Войска французские равномерно таяли в математически правильной прогрессии. И тот переход через Березину, про который так много было писано, была только одна из промежуточных ступеней уничтожения французской армии, а вовсе не решительный эпизод кампании. Ежели про Березину так много писали и пишут, то со стороны французов это произошло только потому, что на Березинском прорванном мосту бедствия, претерпеваемые французской армией прежде равномерно, здесь вдруг сгруппировались в один момент и в одно трагическое зрелище, которое у всех осталось в памяти. Со стороны же русских так много говорили и писали про Березину только потому, что вдали от театра войны, в Петербурге, был составлен план (Пфулем же) поимки в стратегическую западню Наполеона на реке Березине. Все уверились, что все будет на деле точно так, как в плане, и потому настаивали на том, что именно Березинская переправа погубила французов. В сущности же, результаты Березинской переправы были гораздо менее гибельны для французов потерей орудий и пленных, чем Красное, как то показывают цифры.
Единственное значение Березинской переправы заключается в том, что эта переправа очевидно и несомненно доказала ложность всех планов отрезыванья и справедливость единственно возможного, требуемого и Кутузовым и всеми войсками (массой) образа действий, – только следования за неприятелем. Толпа французов бежала с постоянно усиливающейся силой быстроты, со всею энергией, направленной на достижение цели. Она бежала, как раненый зверь, и нельзя ей было стать на дороге. Это доказало не столько устройство переправы, сколько движение на мостах. Когда мосты были прорваны, безоружные солдаты, московские жители, женщины с детьми, бывшие в обозе французов, – все под влиянием силы инерции не сдавалось, а бежало вперед в лодки, в мерзлую воду.