Математические игры и головоломки
Введение
Одним из главных качеств, способствующих процессу решения задач как у обычного человека так и у программиста, является его логика и способность к нестандартному мышлению. Как представитель специальности, где логика играет не последнюю роль, мною была выбрана тема «Математические игры и головоломки». Возможно именно потому, что с детства люблю разгадывать всевозможные загадки и решать головоломки, выбор специальности и пал на ИУС.
В процессе поиска материалов по теме индивидуального задания, был найден реферат [1], который способствовал принятию решения о выборе темы. После длительного мониторинга портала магистров, небыло найдено ни одного индивидуального раздела, относящегося к выбранной мною теме. Однако, недолгие поиски по всемирной паутине привели к некоторым результатам. Таким, например, как интерес к данной теме в основном проявляется у старшеклассников. Именно они составляют рефераты и сообщения на аналогичные темы.
Математика (от греч. mathematike, от mathema – наука) – наука, в которой изучаются пространственные формы и количественные отношения [2].
До начала 17 в. математика – преимущественно наука о числах и сравнительно простых геометрических фигурах. Изучаемые ею величины (длины, площади, объемы и пр.) рассматриваются как постоянные. К этому же периоду относится возникновение арифметики, геометрии, позднее – алгебры и тригонометрии. Областью применения математики являлись: счет, торговля, землемерные работы, астрономия, отчасти архитектура [2].
Как было точно отмечено, что «Математика, также, являлась и является любимым развлечением многих эрудированных людей. Математические развлечения – это и решение занимательных задач, и геометрические построения, и разгадывание числовых и механических головоломок, и математические игры и фокусы. Они развивают математические способности, сообразительность, логическое мышление, укрепляют память. Математические развлечения объединяют учение и игру, труд и отдых, но для занятий ими нужны и воля, и упорство, и настойчивость в достижение цели. Математические задачи делают ум гибким, развивают мышление, подобно тому, как физические упражнения делают гибким тело.»[3].
История возникновения задач-головоломок
Из истории, размещенной на [1] «Задачи – головоломки известны с давних времён, они встречаются уже в Египетских папирусах. Например, с 1 в. н. э. известна задача, получившая название задачи Иосифа Флавия, римского историка. Легенда рассказывает, что однажды отряд воинов, среди которых находились Флавий и его друг, был окружен. Из всех уставших, и выбившихся из сил воинов, отчаявшихся спастись, нужно было выбрать двоих, которые предприняли бы попытку найти выход из окружения. Флавий предложил выбрать этих двоих путём пересчёта так, чтобы каждый третий выбывал из построенных в круг воинов. Счёт продолжался до тех пор, пока не осталось только два человека. Это был мудрый Флавий и его друг. На какие места в округе он встали, если в отряде был 41 воин? Древняя рукопись сообщает: на 16-е и 31-е».
Головоломки очень похожи на математические игры, а некоторые из головоломок произошли именно от существующих игр. Игры, основу которых взяли головоломки придумали древнегреческие математики.
Головоломки и математические игры в современном мире помогают находить верные стратегии и алгоритмы для устранения проблем в программировании.
Математические игры
Для нахождения идеальной стратегии зачастую используют математические игры и задачи. Некоторые задачи простые и решаются известными методами, такими как инвариант и раскраска, но есть и такие, что но до сих пор не решены.
Например, игра крестики-нолики на бесконечном поле (рэндзю). В нее, при верной стратегии обоих игроков, можно играть бесконечно, но выигрышную стратегию при этом никто не знает. За время ее существования придумано много алгоритмов этой игры, основанных, прежде всего, на переборе различных вариантов и анализе игры на следующие несколько ходов, которые очень близки к выигрышной стратегии, но лишь при их реализации на компьютере – человек же им следовать практически не может. Также существуют простые стратегии этой игры, которыми пользуются игроки, но решающей чаще всего бывает внимательность.
Игра крестики и нолики, или тик – так-тоу
Английское название игры в крестики и нолики – тик-так-тоу – пишется и произносится по-разному. В соответствии с «Оксфордским словарём стихов Матушки – гусыни» название тик-так-тоу происходит от старинной английской детской считалочки [4]:
Tit, tat, toe,
My first go,
Three jolly butcher boys all in a row.
Stick one up, stick one down,
Stick one in the old man’s crown.
Об этом древнем состязании на сообразительность писал ещё Уордсворт:
На глади грифельной доски,
Расчерченной в квадраты,
Ведём сраженье я и ты,
Бывалые солдаты.
Кресты с нулями испестрят
Все поле битвы густо,
Но строй их – не могильный ряд
И не наводит грусти.
Не нужно нам владеть клинком,
Не ищем славы громкой.
Тот побеждает кто знаком
С искусством мыслить тонко.
Не можем мы лишь одного:
Назвать то состязанье,
Хоть просты правила его,
Длинно его названье.
Рисунок 1 – Крестики и нолики
Первый игрок (ему принадлежат крестики) может сделать любой из трёх ходов (рис. 1). Во избежание проигрыша второй игрок (ему принадлежат нолики) должен в каждом случае занять одну из указанных клеток.
Игра Ним
Ним одна из самых старых и занимательных математических игр. Играют в неё вдвоём. Дети используют для игры камешки или клочки бумаги, взрослые предпочитают раскладывать монетки на стойке бара. В наиболее известном варианте нима 12 монет раскладывают в три ряда так, как показано на рисунке 2.
Рисунок 2 – Ним
Монеты, разложенные для игры по схеме « 3, 4, 5 ».
Пусть имеется одна или несколько групп предметов. Играющие по очереди берут предметы из групп по правилам, которые заранее устанавливают: какое количество предметов разрешается брать за один раз и из скольких групп. Существует множество вариантов игры, и для большинства известна наилучшая стратегия, ведущая к выигрышу. Наличие самих предметов не обязательно, можно играть и с числами.
Двое называют по очереди любое число от 1 до 10 и складывают названные числа. Выигрывает тот, кто первым доведёт до 100 сумму чисел, названных обоими игроками. Оптимальная стратегия в этой игре состоит в том, чтобы после хода противника называть числа дающие в сумме с предыдущими, члены следующего ряда: 12, 23, 34, 45, 56, 67, 78, 89, 100.
Звёздный ним
Она довольно проста, но стратегия в ней видна не сразу. Играют в эту игру на звездообразной фигуре, изображённой на рис. 3, слева. Поставьте по одной фишке на каждую из девяти вершин звезды. Игроки A и B делают ходы по очереди, снимая при каждом ходе либо одну, либо две фишки, соединённые отрезком прямой. Тот, кто снимает последнюю фишку, выигрывает.
Рисунок 3 – Звёздный ним (слева) и выигрышная стратегия для него (справа)
У игрока B при игре в звёздный ним есть выигрышная стратегия, использующая симметрию игровой доски (вообще, выигрышные стратегии многих математических игр строятся на этом). Представим, что отрезки прямых, соединяющие вершины звезды, – это нити. Тогда всю конфигурацию можно развернуть в окружность, топологически эквивалентную нитяной звезде. Если A снимает с окружности одну фишку, то B снимает две фишки с противоположного участка окружности. Если A берёт две фишки, то B снимает с противоположного участка окружности одну фишку. В обоих случаях на окружности остаются две группы из трёх фишек. Какую бы фишку (или какие бы фишки) ни взял A из одной группы, B берёт соответствующую фишку (или фишки) из другой группы. Ясно, что последняя фишка достанется игроку B [5].
Задачи
С древности до наших дней очень популярны головоломки – шутки, они учат внимательно прислушиваться к каждому слову условия задачи.
Вот одна из них: в кармане лежат две монеты на общую сумму 15 копеек. Одна из них не пятак. Что это за монеты?
Задача основана на психологической особенности человеческого восприятия – запоминать главные факты из условия задачи. В данном случае – то, что монета в кармане не пятак. И начинаются безуспешные попытки решения. А правильный ответ: 10 коп. и 5 коп, так как в условии сказано, что только одна монета не пятак.
В старинной задаче «Волк, козёл и капуста» крестьянину нужно перевести через реку волка, козу и капусту. Лодка так мала, что в ней кроме крестьянина может поместиться или только волк, или только козел, или только капуста. Но если оставить волка с козлом, то волк его съест, а если оставить козла с капустой, то будет съедена капуста. Как быть крестьянину?
В этом случае крестьянину переправу нужно начать с перевозки козла. Затем крестьянин возвращается и берёт волка, которого перевозит на другой берег и там оставляет, но везёт на первый берег козла. Здесь он оставляет его и к волку капусту. А затем, возвращаясь, перевозит козла [6].
Или такая задача1:
У трех маляров был брат Иван, а у Ивана братьев не было. Как это могло случиться?
Ответ очень прост: маляры были сестрами.
А есть такие:
Задача 2 [7]:
Директор обнаружил, что его ограбили, рано утром, когда пришёл на работу. Он тут же вызвал детектива.
– Похоже, кто-то брал ключ от моего маленького сейфа в стене, – пожаловался пострадавший детективу.
– Но не могу понять, как они его могли взять. Этот ключ всегда у меня в связке.
– Вы когда-нибудь кому-нибудь давали эти ключи? – спросил детектив.
– Да. Двое моих работников, Джон и Тед, привозили на моем грузовике товар. Ключ от грузовика в этой связке, но потом они всегда возвращают её мне. Кроме того, я всегда запираю свой кабинет, они здесь даже никогда не были. Я всегда сам выхожу в торговый зал, – пояснил пострадавший.
Когда Джон и Тед появились на работе, детектив побеседовал отдельно с каждым из них, сказав одно и тоже:
– Вчера был взломан сейф в кабинете директора. Вы что – нибудь об этом знаете?
Тед сказал:
– Он запирает свой кабинет. Иногда он даёт мне связку ключей, но я не взламывал сейф!
Джон сказал:
– О чем вы? Вы считаете, что это я сделал копии с его ключей и залез в кабинет вчера вечером? Посмотрите на эту связку! Я даже не знаю, с какого ключа надо снять копию, чтобы открыть сейф! Детектив был доволен: – Теперь у нас есть подозреваемый!
Какой нелепый ответ выдал преступника?
Можно рассуждать так: Тед сказал, что не взламывал сейф, а Джон, похоже, знал, что сейф открывали ключом. Он сказал «Я не знаю, с какого ключа нужно было сделать копию, чтобы открыть этот сейф!» Если бы он не побывал в офисе, то не знал бы, что сейф открывается ключом, а не комбинацией цифр. Джон явно хитрит!
Или русская народная потешка, а в ней интересная загадка (Задача 3):
Прилетели галки,
Сели на палки.
Если на каждой палке
Сядет по одной галке,
То для одной галки
Не хватит палки.
Если же на каждой палке
Сядет по две галки,
То одна из палок
Будет без галок.
Сколько было галок?
Сколько было палок?
Ответ: Четыре галки, три палки.
Головоломки
Задачи не требующие математического решения, называются головоломками. Только логика и сообразительность помогут найти правильное решение.
К комбинаторным головоломкам относится знаменитый венгерский кубик Рубика, полимино, и игры типа «игра 15», а также задачи «на маневрирование», головоломки с перестановкой шашек «Ханойская башня» и др.
О Ханойской башне существует легенда, согласно которой где-то в глубине джунглей в буддийском храме находится пирамида, состоящая из 64 золотых дисков. День и ночь жрецы храма заняты разбором этой пирамиды. Они переносят золотые диски на новое место, строго соблюдая следующие правила: за один раз разрешается переносить только один диск (рис. 4). Предание гласит, что, как только жрецы закончат работу, грянет гром, храм рассыплется в пыль и наступит конец света [8].
Рисунок 4 – Ханойская башня
На всю работу им понадобится около 580 млрд. лет. За это время храм, действительно, может рассыпаться в пыль.
Древнейшие геометрические головоломки – это такие головоломки на складывание отдельных кусочков или геометрических фигур. Уже сами названия этих головоломок: «Пифагор», «Колумбово яйцо», «Архимедова игра» – говорит об их древности. С помощью картона можно сделать игру самому.
Топологические головоломки тоже одни из самых древних. К ним относятся всем известные лабиринты, проволочные, шнурковые и объемные сборно-разборные головоломки.
Способность человека отгадывать задуманное другим число является чудом для незнающего, но знающий сможете не только их показать, но и придумывать сам. Например, можно попросить друга задумать любое число, затем отнять от него 1, результат умножить на 2, из произведения вычесть задуманное число и сообщить вам результат. Прибавив к нему число 2, вы отгадаете задуманное. Секрет фокуса становится понятен, если записать предложенные действия в виде алгебраического выражения (х – 1) 2 – х, где х – задуманное число. Раскрыв скобки, и выполнив действия, мы получим, что это выражение равно х – 2.
Кроме этого, угадать результат арифметических действий над неизвестным числом тоже можно, например, так. Один человек задумал число. Вы просите умножить его на 2, затем прибавить к произведению 12, сумму разделить пополам и вычесть из неё задуманное число. Какое бы число ни было задумано, результат всегда будет равен 6, так как (2х + 12) / 2 - х = 6 при любом х.
Логические задачи – головоломки
В наше время огромную популярность получил именно такой вид логических задач – головоломки. Пример решения такой задачи приведен ниже.
Задача 1
Три мальчика, устав от игр, прилегли отдохнуть под деревом и уснули. Пока они спали, их товарищи испачкали им сажей лбы. Проснувшись, и взглянув друг на друга, мальчики стали смеяться. Внезапно один из них замолчал, так как понял, что его лоб тоже испачкан. Он подумал: «Мы смеёмся, потому что каждый из нас считает, что его лицо чистое. Но если моё лицо чистое, то Коле должен быть непонятен смех Андрея. Раз Андрей смеётся, а моё лицо чистое, то он смеётся над Колей. Коля должен это понять и перестать смеяться. А раз он не перестаёт, значит, мой лоб тоже в саже».
Или так
Посмотрим ниже:
1 = 1,
1 + 3 = 4 = 2,
1 + 3 + 5 = 9 = 3,
1 + 3 + 5 + 7 = 16 = 4
Может быть, эта закономерность (сумма подряд стоящих нечетных чисел начиная с единицы равна квадрату их числа) сохраняется и дальше? Как это проверить?
Нам нужно найти сумму всех нечетных чисел от 1 до 2n – и убедится, что она равна n. Это можно сделать различными способами. Мы предпочли геометрический. Возьмем квадрат из n клеток и закрасим клетки так, как это сделано на рис. 5 для n = 6. Квадрат при этом распадается на чередующиеся по цвету участки. Сосчитаем количество клеток в них, начиная с левого верхнего угла. Первый участок состоит из одной клетки, второй из трех клеток, третий из пяти и т. д., последний n – й участок состоит из 2n – 1 клеток. Следовательно, число клеток в квадрате равно 1 + 3 + 5 + 7 + … + 2n – 1.
Рисунок 5 – Квадрат
Это убеждает нас, что нужное равенство выполнено всегда. С помощью геометрических представлений можно вычислять и другие суммы.
Задача 2
В одной компании в начале карточной игры возникла удивительная ситуация. Когда всем игрокам раздали по 1 карте, оказалось, что значения карт идут по порядку от 1 до 10, ни одно значение карты не повторяется, а сумма карт у любого из двух соседних игроков равна сумме карт двух игроков, сидящих друг напротив друга (рис. 6). Вы можете определить относительное расположение 10 карт?
Рисунок 6 – Схема игры
Например:
1 + 10 = 11 и 5 + 6 = 11 (рис. 7).
Рисунок 7 – Схема игры (пример)
Игры с дыркой
До изобретения кубика Рубика для многих людей знакомство с головоломками начиналось с «пятнашек» – так часто называют известную игру «15».
С пятнашек начинается история игр с дыркой – головоломок, в которых фишки перемещаются по игровому полю за счёт того, что одно из мест на поле свободно. У «пятнашек» есть множество родственников, которые как раз и образовывают целый раздел этих головоломок.
Американский изобретатель головоломок Сэмюель Лойд игру «15» придумал в 70-х годах XIX-го века. Между созданием его игрушки и изобретением кубика Рубика лежит целый век. Интересен следующий факт: возраст обоих изобретателей, когда они придумали свои знаменитые головоломки, был одинаков (около тридцати лет). До «пятнашек» никакая другая головоломка таким успехом не пользовалась.
Великий Марк Твен, будучи современником Лойда и свидетелем всеобщего ажиотажа вокруг игры «15», включил в свою сатирическую повесть «Американский претендент» изложение сообщения, якобы переданного агентством «Ассошиэйтед пресс», в котором говорилось, что «за последние несколько недель вошла в моду новая игрушка-головоломка… и что от Атлантического океана до Тихого все население Соединенных Штатов прекратило работу и занимается только этой игрушкой; что в связи с этим вся деловая жизнь в стране замерла, ибо судьи, адвокаты, взломщики, священники, воры, торговцы, рабочие, убийцы, женщины, дети, грудные младенцы, – словом, все с утра до ночи заняты одним-единственным высокоинтеллектуальным и сложным делом… что веселье и радость покинули народ, – на смену им пришли озабоченность, задумчивость, тревога, лица у всех вытянулись, на них появились отчаяние и морщины – следы прожитых лет и пережитых трудностей, а вместе с ними и более печальные признаки, указывающие на умственную неполноценность и начинающееся помешательство; что в восьми городах день и ночь работают фабрики, и все же до сих пор не удалось удовлетворить спрос на головоломку» [9].
После своего появления на свет игру 15 перивезли и в европу, где она быстро распространилась во всех странах материка и поучила новое имя «такен». Изобретатель нашел такую меру сложности, что головоломка решалась без труда почти всеми и в то же время требовала определённой сообразительности, благодаря чему каждый мог получить удовольствие от сознания своего высокого интеллектуального уровня.
Успешной головоломка стала благодаря напечатанному в газетах объявление о призе в $1000 за решение следующей задачи: в исходной позиции фишки располагаются по порядку номеров, за исключением двух последних, которые переставлены местами друг с другом (рис. 8); передвигая по одной фишке, но, не вынимая фишки из коробочки, нужно поменять местами номера 15 и 14 так, чтобы все фишки стояли по порядку номеров, а правый нижний угол был свободен.
Рисунок 8 – Ловушка Ллойда
Когда Лойд размещал это объявление, он знал что ничем не рискует, так как думал, что предлагает неразрешимую задачу. Когда он пытался запатентовать свою игру, ему сказали, что нельзя запатентовать игру, не имеющую решения.
Секрет игры «15» [10]
Зачастую, головоломку нельзя перевести из одного состояния в другое, – запрещены такие переходы, при которых нарушаются те или другие законы сохранения. Существует особый закон и в игре «15». Чтобы объяснить его, мысленно заполним пустое место фишкой с номером 16. Тогда каждый ход – сдвиг фишки – будет состоять в том, что эта фишка меняется местами с фишкой 16. Операцию, при которой какие-то две фишки (не обязательно соседние!) меняются местами, так и назовем – обменом; математический термин для таких операций – транспозиция. Очевидно, что из любой расстановки 16 фишек можно не более чем за 15 обменов получить правильную позицию – обозначим ее S0 – и вообще любую другую расстановку. При этих обменах не запрещается вынимать фишки из коробки. Например, можно сначала поставить на свое место фишку 1, обменяв ее с той фишкой, которая это место занимает, затем точно так же поставить на место фишку 2 и т. д. Последними мы обменяем фишки 15 и 16 – при этом сразу обе встанут правильно. Конечно, не исключено, что по ходу дела какие-то фишки автоматически попадут на свои места, и их трогать не придется, при этом число обменов окажется меньше 15. Можно расставлять фишки по этой же системе, но в другом порядке, скажем 16, 15, 14, … или совсем иначе, и тогда число обменов может оказаться другим. Однако, каким бы способом ни выбрать последовательность обменов, превращающую одну заданную расстановку фишек в другую, четность числа обменов в этой последовательности всегда будет одной и той же.
Это очень важное и неочевидное докажем ниже. Оно позволяет дать следующее определение: расстановка называется четной, если ее можно превратить в правильную позицию с помощью четного числа обменов, и нечетной в противном случае. В математике обычно говорят не «расстановка», а «перестановка»; к этому мы еще вернемся. Сама правильная расстановка S0 всегда четная, а ловушка Лойда L нечетная. Но почему они не переводятся друг в друга?
Как выше уже сказано, каждый ход в игре «15» можно рассматривать как обмен фишки с одной из соседних. Следовательно, при каждом ходе четность расстановки 16 фишек меняется: если до хода расстановку можно было упорядочить за N обменов, то после него – за N+1 обменов (взяв этот ход назад), а числа N и N+1 – разной четности. В обеих расстановках классической задачи Лойда дырка (или фишка 16) расположена одинаково. Если бы мы сумели одну расстановку перевести в другую, то фишка 16 должна была совершить столько же ходов вверх, сколько вниз, и столько же ходов вправо, сколько влево, иначе она не вернулась бы назад. Поэтому мы сделали бы четное число ходов, а так как при каждом ходе четность расстановки меняется, в начале и в конце она была бы одинаковой. Но позиции S0 и L, как мы видели, имеют разную четность.
Заключение
В данной статье была рассмотрена малая часть логических головоломок, придуманных математиками различных времен, но если когда-нибудь еще и придумают головоломку более популярную, чем игра «15», то известней знаменитого кубика Рубика наверняка нет!
В любом возрасте человек стремиться познать что-то новое и разгадать неразгаданное. Большенство игр на отгадывание во многом похожи друг на друга – один игрок загадывает что-то, а другой, задает определенные вопросы и получает необходимые ответы на них находит ответ.
Наша детская страсть к играм и головоломкам иногда вызывает у человека желание посвятить свою жизнь математике, физике, биологии, или другим наукам, чтобы «отгадывать» более серьезные загадки.
Создатели математических теорий, лучшие криптографы скорее всего с самого детства любили загадки и всегда верно их разгадывали. Кроме развития логики, математические и логические игры развивают творческие способности человека, приучают ставить самые важные вопросы и находить на них ответы.
Разгадывание математических головоломок – это не просто интересное времяпровождение, а очень полезное для ума занятие.
Список литературы
- Т. Крапивко, «Математические игры и головоломки», п. Большой Исток, 2008 г.
- Мультимедийная энциклопедия Кирилла и Мефодия.
- Юнциклопедия [электронный ресурс]. – Режим доступа: Математические развлечения.
- О. Писклена, газета «Математические игры».
- А.А. Петров, «Математические игры и головоломки», г. Кемерово, 1999 г.
- Е.Я. Гик, «Занимательные математические игры».
- И. Ганчев, К. Чимев, Й. Стоянов, «Математический фольклор».
- Издательство «Росмен», «Энциклопедия математика».
- Щ. Еленьский, «По следам Пифагора».
- Место игр [электронный ресурс]. – Режим доступа: playland.ru.