Назад
Вперёд
Внимание! Предварительный просмотр слайдов используется исключительно в ознакомительных целях и может не давать представления о всех возможностях презентации. Если вас заинтересовала данная работа, пожалуйста, загрузите полную версию.
Полимино
В этой статье мы будем рассматривать полимино – фигуры, составленные из одноклеточных квадратов так, что каждый квадрат примыкает хотя бы к одному соседнему, имеющему с ним общую сторону.
Задачи с полимино очень характерны для комбинаторной геометрии – раздела математики, занимающегося вопросами взаимного расположения и комбинирования геометрических фигур. Это очень красивая, но еще почти не разработанная ветвь математики, поскольку общих методов в ней, по-видимому, очень мало, а известные ныне методы настолько примитивны, что не поддаются усовершенствованию. Многие встречающиеся в практике важные инженерные задачи – в первую очередь те, которые связаны в том или ином смысле с оптимальным расположением фигур заданной формы, – по существу относятся к комбинаторной геометрии.
В последующих комбинаторных задачах предполагается, что полимино можно вращать (то есть поворачивать на 90, 180 или 270) и зеркально отражать (переворачивать), не меняя формы самих фигур.
Домино
Рис. 1
Домино состоит из двух квадратов и может иметь лишь одну форму – форму прямоугольника размером 1×2 (см. рис. 1). Первая связанная с домино задача, вероятно, многим знакома: даны шахматная доска, из которой вырезана пара противоположных угловых клеток, и коробка домино, каждое из которых покрывает ровно две клетки шахматной доски (см. рис. 2). Возможно ли целиком покрыть доску с помощью 31 кости домино (без свободных клеток и наложений)? Ответ на этот вопрос гласит: «НЕТ» и имеет замечательное доказательство. Шахматная доска содержит 64 чередующиеся клетки белой и черной раскраски (имеется в виду обычная шахматная раскраска доски). Каждая положенная на такую доску и покрывающая две соседние клетки кость домино покроет одно белое и одно черное поле, а n костей домино – n белых и n черных полей, т.е. поровну и тех и других. Но изображенная на рисунке шахматная доска содержит больше черных клеток, чем белых, и потому ее нельзя покрыть костями домино. Этот результат есть типичная теорема комбинаторной геометрии.
Рис. 2
Тримино
Рис. 3
Тримино (или триомино) - полимино третьего порядка, то есть многоугольник, полученный путём объединения трёх равных квадратов, соединённых сторонами. Если повороты и зеркальные отражения не считать различными формами, то существует только две «свободных» формы тримино (см. рис.3): прямое (I-образное) и угловое (L-образное).
Тетрамино
Рис. 4
С тетрамино связано множество задач на составление из них разных фигур. Доказано, что сложить какой-либо прямоугольник из полного набора тетрамино невозможно. Доказательство использует раскраску в шахматном порядке. Все тетрамино , кроме Т-образного, содержат 2 чёрные и 2 белые клетки, а Т-образное тетрамино - 3 клетки одного цвета и 1 клетку другого. Поэтому любая фигура из полного набора тетрамино (см. рис.4) будет содержать клеток одного цвета на две больше, чем другого. Но любой прямоугольник, с чётным количеством клеток, содержит равное число чёрных и белых клеток.
Пентамино
Рис. 5
Полимино, покрывающее пять клеток шахматной доски, называются пентамино. Существует 12 видов пентамино , которые можно обозначить прописными латинскими буквами, как указано на рисунке (см. рис. 5). В качестве приема, позволяющего легко запомнить эти наименования, укажем, что соответствующие буквы составляют конец латинского алфавита (TUVWXYZ ) и входят в имя FiLiPiNo . Поскольку всего имеется 12 разных пентамино и каждая из этих фигур покрывает пять клеток, то вместе они покрывают 60 клеток.
Самая распространённая задача о пентамино - сложить из всех фигурок, без перекрытий и зазоров, прямоугольник. Поскольку каждая из 12 фигур включает в себя 5 квадратов, то прямоугольник должен быть площадью 60 единичных квадратов. Возможны прямоугольники 6×10, 5×12, 4×15 и 3×20 (см. рис. 6).
Рис. 6
Для случая 6×10 эту задачу впервые решил в 1965 году Джон Флетчер. Существует ровно 2339 различных укладок пентамино в прямоугольник 6×10, не считая поворотов и отражений целого прямоугольника, но считая повороты и отражения его частей (иногда внутри прямоугольника образуется симметричная комбинация фигур, поворачивая которую можно получить дополнительные решения).
Для прямоугольника 5×12 существует 1010 решений, 4×15 - 368 решений, 3×20 - всего 2 решения (отличающихся вышеописанным поворотом). В частности, существует 16 способов сложить два прямоугольника 5×6, из которых можно составить как прямоугольник 6×10, так и 5×12.
Еще одна интересная задача о пентамино - задача об утроении фигур пентамино (см. рис. 7). Эта задача была предложена профессором Калифорнийского университета Р.М.Робинсоном. Выбрав одну из 12 фигур пентамино, необходимо построить из каких-либо 9 из 11 оставшихся пентамино фигуру, подобную выбранной, но в 3 раза бо́льшей длины и ширины. Решение существует для любого из 12 пентамино , причём не единственное (от 15 решений для Х до 497 для Р). Существует вариант этой задачи, в котором для построения утроенной фигуры разрешается использовать также и саму исходную фигуру. В этом случае число решений от 20 для Х до 9144 для Р-пентамино.
Рис. 7
Мало кто в детстве любил математику, зато математические головоломки в интернете всегда становятся хитами, ведь для их решения обычно не требуется углубленных знаний, зато требуются смекалка и нестандартное мышление. Предлагаем вам проверить себя на пяти главных логических задачках этого года.
Задача №1
Кумар Анкит предложил пользователям Facebook посчитать, сколько треугольников изображено на его рисунке. С простым, казалось бы, заданием подсчитать фигуры не справился практически никто из пользователей. Близки к правильному ответу оказываются многие, но большинству не хватает чуть-чуть внимательности.
Ответ:
Внутри большого треугольника находится 24 треугольника, посчитать это несложно, но большинство пользователей не обратили внимание на еще один треугольник, скрытый в подписи автора. Таким образом, всего на картинке 25 треугольников.
Задача №2
Необычную задачку с двумя решениями предложили пользователям интернета создатели сайта gotumble.com. По их словам, одно решение головоломки более простое, его способны найти около 10% людей, а вот дойти до второго решения получается у одного человека из тысячи. Попробуйте сделать это сами.
Ответ:
Первое решение состоит в том, чтобы прибавлять к каждому следующему примеру результат предыдущего. Так, прибавив 5 к сумме 2 и 5, мы получим 12. Прибавив 12 к сумме 3 и 6, получим 21. И так далее. В таком случае правильным ответом головоломки будет 40.
А вот второе решение , до которого доходит лишь один человек из тысячи, состоит в том, чтобы сложить первую цифру примера с произведением двух цифр:
2 + 2*5 = 12, 3 + 3*6 = 21, 8 + 8*11 = 96.
Задача №3
У нас есть треугольник, состоящий из четырех частей, но если перегруппировать части, то в нем появляется пустой квадрат. Как такое может быть?
Ответ:
Это вовсе не оптический обман. Все дело в разных углах наклона гипотенузы красного и бирюзового треугольника - отсюда и разные размеры фигур.
Задача №4
Колумнист издания The Guardian Алекс Беллос предложил читателям решить задачку, которая является частью выпускного экзамена по математике в некоторых странах. По статистике ее решает всего один человек из 10.
У нас есть цилиндр, вокруг которого симметрично четыре раза обмотана нить. Окружность цилиндра составляет 4 см, а его длина – 12 см. Нужно найти длину нити.
Ответ:
Задача кажется большинству школьников слишком сложной, на самом же деле надо лишь понять, что, развернув цилиндр на плоскость, мы получим обыкновенный прямоугольник со сторонами - 4 и 12 см, который можно разделить на четыре прямоугольника поменьше со сторонами - 4 и 3 см. Нить в этом случае будет гипотенузой прямоугольного треугольника и ее длину в каждой из четырех фигур можно вычислить по простой школьной формуле, она равняется 5 см. В результате общая длина нити равняется 20 сантиметрам.
Задача №5
И наконец, последняя математическая головоломка, взорвавшая соцсети. По словам автора поста, на ней изображена загадка, которую дают в качестве бонусного вопроса студентам в Сингапуре. Составители загадки предлагают изучить числовую последовательность и заполнить четыре свободных окошка недостающими числами.
Ответ:
Пользователи сети долго ломали голову над этой задачкой, но справиться с ней не смогли даже серьезные математики. А министерство образования Сингапура от этого задания открестилось, заявив, что никакого отношения к нему не имеет. Так что скорее всего головоломка была просто чьей-то злой шуткой.
Танграм - старинная восточная головоломка из фигур, получившихся при разрезании квадрата на 7 частей особым образом: 2 больших треугольника, один средний, 2 маленьких треугольника, квадрат и параллелограмм. В результате складывания этих частей друг с другом получаются плоские фигуры, контуры которых напоминают всевозможные предметы, начиная от человека, животных и заканчивая орудиями труда и предметами обихода. Такого рода головоломки часто называют "геометрическими конструкторами", "головоломками из картона" или "разрезными головоломками".
С танграмом ребенок научится анализировать изображения, выделять в них геометрические фигуры, научится визуально разбивать целый объект на части, и наоборот - составлять из элементов заданную модель, а самое главное - логически мыслить.
Как сделать танграм
Танграм можно сделать из картона или бумаги, распечатав шаблон и разрезав по линиям. Вы можете скачать и распечатать схему квадрата танграма, кликнув по картинке и выбрав "печать" или "сохранить картинку как...".
Можно и без шаблона. В квадрате чертим диагональ - получается 2 треугольника. Один из них разрезаем пополам на 2 небольших треугольника. Отмечаем на каждой стороне второго большого треугольника середину. Отсекаем по этим отметкам средний треугольник и остальные фигуры. Есть и другие варианты, как расчертить танграм, но когда вы его разрежете на части, они будут абсолютно те же самые.
Более практичный и долговечный танграм можно вырезать из жесткой офисной папки или пластиковой коробки из под DVD. Можно немного усложнить себе задачу, вырезав танграм из кусочков разного фетра, обметав их по краям, или вовсе из фанеры или дерева.
Как играть в танграм
Каждая фигура игры должна складываться из семи частей танграма, и при этом они не должны перекрываться.
Самый легкий вариант для детей дошкольников 4-5 лет - собирать фигуры по расчерченным на элементы схемам (ответам), как мозаику. Немного практики, и ребенок научится составлять фигуры по образцу-контуру и даже придумывать свои фигуры по такому же принципу.
Схемы и фигуры игры танграм
В последнее время танграм частенько используют дизайнеры. Самое удачное применение танграма, пожалуй, в качестве мебели. Есть и столы-танграмы, и трансформируемая мягкая мебель, и корпусная мебель. Вся мебель, построенная по принципу танграма, довольно удобна и функциональна. Она может видоизменятся в зависимости от настроения и желания хозяина. Сколько всевозможных вариантов и комбинаций можно составить из треугольных, квадратных и четырехугольных полок. При покупке такой мебели вместе с инструкцией покупателю выдаются несколько листов с картинками на разные темы, которые можно сложить из этих полок. В гостиной можно повесить полки в виде людей, в детской из этих же полок можно сложить котов, зайцев и птиц, а в столовой или библиотеке - рисунок может быть на строительную тему - дома, замки, храмы.
Вот такой многофункциональный танграм.
Новый класс игр с пентамино, который мы сейчас рассмотрим, можно охарактеризовать как задачи "совмещения" фигур, то есть задачи о складывании из пентамино двух или более равных между собой фигур. Приведем несколько примеров:
1. Попробуйте составить из 12 различных пентамино два одинаковых прямоугольника размером 5×6 (на каждый будет затрачено по 6 пентамино). На рис. 21 изображены отвечающие этим прямоугольникам наборы пентамино, причем любопытно, что приведенное разбиение наших фигур на два набора по шесть пентамино - единственно возможное. Впрочем, из этого не следует, что задача имеет единственное решение. В самом деле, для изображенного на рисунке справа набора фигур мы можем по-разному соединить F- и N-пентамино, получив при этом одну и ту же фигуру (как?).
Рис. 21. Два набора по 6 пентамино, из которых можно составить прямоугольники 5×6
Заметим, между прочим, что решение этой задачи одновременно служит решением задачи о покрытии 12 пентамино прямоугольников размерами 5×12 и 6×10. Для того чтобы убедиться в этом, достаточно приложить друг к другу двумя способами наши прямоугольники размером 5×6.
2. Найдите такое покрытие 12 разными пентамино шахматной доски размером 8×8 с отверстием размером 2×2 в центре доски, чтобы доску можно было разбить на две одинаковые части, каждая из которых покрыта шестью пентамино. Три типичных решения этой задачи приведены на рис. 22.
Рис. 22. Типичное решение задачи о покрытии шахматной доски 8×8 с центральной "дыркой" 2×2, причем покрытие разбивается на две конгруэнтные части
3. Разбейте 12 пентамино на три группы по четыре фигуры в каждой так, чтобы при этом существовала 20-клеточная "доска", которую можно покрыть четырьмя пентамино, образующими любую из групп. Решение, изображенное на рис. 23, вовсе не единственное; читатель может попытаться найти свое решение.
4. Снова разбейте наши 12 пентамино на три группы по четыре пентамино; каждую группу в свою очередь разбейте на пары пентамино и придумайте три 10-клеточные "доски" (свою для каждой группы), покрываемые любой из входящих в соответствующую группу пар полимино. Одно из решений приведено на рис. 24. Постарайтесь найти другие решения, в частности такие, где ни одна из трех "досок" не имеет отверстий (подобные решения существуют).
5. Еще раз разбейте 12 пентамино на три группы по четыре полимино в каждой. Если теперь ко всем наборам добавить по мономино, можно попытаться сложить из них три прямоугольника размером 3×7. Решение задачи показано на рис. 25. Известно, что других решений нет, если не считать того, что в самом левом прямоугольнике можно переложить мономино и Y-пентамино таким образом, чтобы в целом они составили ту же фигуру.
Рис. 25. Решение задачи о покрытии трех прямоугольников 3×7
Доказательство единственности решения последней задачи было подсказано инженером К. С. Лоренсом из компании "Аэроспейс Корпорейшн" (Лос-Анджелес) Прежде всего, нетрудно видеть, что Х-пентамино необходимо скомбинировать с U-пентамино, приложив их друг к другу так, как показано на рис. 26. Завершая первый прямоугольник, мы, очевидно, уже не сможем воспользоваться ни F-, ни W-пентамино. Легко заметить также, что последние две фигуры заведомо должны принадлежать разным прямоугольникам размером 3×7; иначе говоря, из трех наших прямоугольников размером 3×7 один будет содержать Х- и U-пентамино, другой - W-пентамино и, наконец, третий - F-пентамино. Мы предоставляем читателю возможность самостоятельно закончить решение задачи и с помощью несложного, хотя и довольно скучного разбора всех возможных оставшихся вариантов расположения фигур показать, что решение, изображенное на рис. 25, в самом деле является единственным.
Рис. 26. Единственно возможное положение Х-пентамино в прямоугольнике 3×7
6. Разложите наши 12 пентамино в четыре группы по три фигуры в каждой и придумайте такую 15-клеточную "доску", чтобы ее можно было покрыть всеми пентамино любой из групп.
Эта задача до сих пор не решена, но вместе с тем и не доказано, что такой "доски" не существует.
7. Вырежьте из шахматной доски фигуру наименьшей возможной площади, состоящую из некоторого числа примыкающих друг к другу клеток доски, так, чтобы на этой фигуре разместилось любое пентамино.
Минимальная площадь такой фигуры - 9 квадратов (клеток); два 9-клеточных решения задачи приведены на рис. 27. В самом деле, нетрудно проверить, что любое пентамино уместится на каждой из изображенных на рисунке "досок". С другой стороны, можно доказать, что наименьшая возможная площадь требуемой фигуры есть площадь в 9 квадратов. Действительно, если бы существовала менее чем 9-клеточная фигура, удовлетворяющая требуемым условиям, то, размещая на ней I-, Х- и V-пентамино, мы совместили бы их так, чтобы они вместе покрывали площадь не более чем 8 клеток. Ясно, что I- и Х-пентамино совместятся при этом по трем клеткам: в противном случае мы либо сразу же получим фигуру из 9 клеток, либо (если центральная клетка Х-пентамино совпадет с крайней клеткой I-пентамино) придем к фигуре из 9 клеток - если потребуем, чтобы на этой фигуре можно было бы разместить и V-пентамино. Но этому условию отвечают всего две изображенные на рис. 28 конфигурации из 8 клеток, такие, что и V-пентамино размещается на рассматриваемой "доске". Однако легко видеть, что на обеих "досках" не умещается, например, U-пентамино; для того чтобы обеспечить размещение на "доске" также и U-пентамино, потребуется увеличить любую из изображенных на рис. 28 фигур еще минимум на одну клетку. Таким образом, площади в 8 клеток для решения задачи будет не хватать, в то время как 9-клеточные фигуры, удовлетворяющие условию задачи, как мы видели выше, существуют.
Несколько лет назад к решению разнообразных задач о полимино были привлечены современные электронные вычислительные машины. Так, в сообщении известного американского специалиста по математической логике Дана Стюарта Скотта, профессора Стэнфордского университета (см. библиографию в конце книги), говорилось о двух задачах, решенных с помощью ЭВМ Стэнфордского университета MANIAC. Первая из них, уже знакомая нам, состояла в складывании из 12 разных пентамино прямоугольника размером 3×20. Выяснилось, что два ее решения, указанные на стр. 24, являются единственно возможными. Вторая задача заключалась в перечислении всех возможных покрытий 12 различными пентамино шахматной доски размером 8×8, в центре которой вырезан квадрат размером 2×2 (квадратное тетрамино). Оказалось, что последняя задача имеет 65 разных (то есть не получающихся друг из друга поворотами и отражениями доски) решений.
При составлении программы Д. Скотт воспользовался очень простой и остроумной идеей, которая заключалась в следующем: Х-пентамино можно расположить на шахматной доске лишь тремя существенно различными способами, показанными на рис. 29; Электронная вычислительная машина MANIAC нашла 20 решений для первого расположения Х-пентамино, 19 - для второго и 26 - для третьего расположения. Три из наиболее интересных решений, входящих в число этих 65, приведены на рис. 30, а на рис. 31 показаны три невозможные ситуации - они невозможны просто потому, что их нет в списке Скотта.
Рис. 29. Три возможных положения Х-пентамино на шахматной доске 8×8 с удаленным центральным квадратом 2×2
Рис. 30. Три интересных решения задачи о покрытии доски 8×8 с удаленным центральным квадратом 2×2
Рис. 31. Невозможные покрытия полимино шахматной доски 8×8
Профессор Манчестерского университета С. Б. Хэзелгроув, английский астроном, известный также своими результатами по теории чисел, не так давно с помощью ЭВМ подсчитал число всевозможных способов сложения из всех 12 пентамино прямоугольника размером 6×10. Вот его результат: не считая поворотов и отражений шахматной доски, ЭВМ нашла 2339 принципиально разных решений! Вместе с тем Хэзелгроув проверил и подтвердил два названных выше результата Дана Скотта.
В заключение приведем еще три несомненно заслуживающие внимания задачи, относящиеся к составлению фигур из пентамино:
1. Покройте "64-клеточную пирамиду", изображенную на рис. 32, 12 разными пентамино и квадратным тетрамино (впрочем, последнее можно заменить любым другим тетрамино). Одно из решений приведено на рис. 32.
Рис. 32. "Треугольник" из 64 квадратов
2. Покройте 12 пентамино вытянутый крест, изображенный на рис. 33.
3. Профессору Р. М. Робинсону (который также впервые указал "зубчатый квадрат", приведенный в гл. VI) принадлежит очень простое доказательство того, что 60-клеточную фигуру, показанную на рис. 34, нельзя покрыть 12 разными пентамино. В самом деле, с краев эта фигура ограничена 22 клетками (считая и четыре угловые), а если сосчитать, сколько квадратов каждого из 12 пентамино может находиться на краю нашей фигуры, то в сумме мы получим всего лишь 21 клетку - на единицу меньше, чем требуется:
Т-пентамино - 1; W-пентамино - 3; Z-пентамино - 1; L-пентамино - 1; U-пентамино - 1; Х-пентамино - 3; F-пентамино - 3; Р-пентамино - 2; V-пентамино - 1; Y-пентамино - 2; 1-пентамино - 1; N-пентамино - 2 Итого: 21 клетка.
Рассуждения такого рода, где отдельно рассматриваются внутренние и "граничные" клетки доски, весьма полезны при складывании "зигзагообразных" фигур.
Другие любопытные головоломки с пентамино будут рассматриваться в гл. VI.