Содержание
Пасьянс
Сойдется или не сойдется пасьянс
Этот нехитрый старинный пасьянс вошел в качестве примера в первую из серии новейших книг «Искусство программирования для электронных вычислительных машин».
Пасьянс
Колоду карт из 52 листов раскладывают на 13 групп, по четыре в каждой, картинкой вниз (см. рис. 1).
Рис. 1
Двенадцать групп соответствуют цифрам на циферблате часов: 1 час — туз (А), 2 часа — двойка, 3 часа — тройка и т. д. до 11 часов — валет, 12 часов — дама. Тринадцатую группу — группу короля помещают в центр.
Начинают с центра. Открыв верхнюю карту, кладут ее картинкой вверх под низ соответствующей группы. Например, если открылась семерка, то ее подсовывают под группу карт, соответствующую семи часам, если дама, то 12 часам и т. д.
Теперь открывается верхняя карта группы, под которую вы только что положили карту из центра, и кладется под соответствующую ей группу. То же самое проделывается с новой картой. И так далее.
Если вы перевернете карту, соответствующую группе, в которой она находится, положите ее картинкой вверх под эту группу, переверните следующую верхнюю карту этой же группы.
Если вы положите какую-то карту под группу и на ней не будет игровой карты, то есть карты, обращенной картинкой вниз (группа из четырех карт одного и того же достоинства, обращенных картинкой вверх), то возьмитесь за следующую группу на циферблате по часовой стрелке.
Пасьянс сошелся, если все 52 карты лягут картинкой вверх. 52-й, последней картой будет король. Если же вы перевернете четвертого короля до того, как это случится, дальнейшая перекладка прекращается и пасьянс считается невышедшим.
Раскладка пасьянса «часы» — процесс чисто механический, не требующий какого-либо умения, а только внимания, Вероятность того, что пасьянс сойдется, равна точно 1/13, и в конце концов среднее число карт, повернутых картинкой вверх в ходе игры, составляет 42,4.
Это не так трудно подсчитать, но вот другое этом пасьянсе более удивительно и не замечалось много десятков лет.
Сойдется или не сойдется пасьянс
Дональд Кнат, математик из Калифорнийского университета, автор книги «фундаментальные алгоритмы» из упомянутой выше серии, обратил внимание на то, что в этом пасьянсе очень просто узнать заранее, сойдется он или не сойдется.
Это, оказывается, зависит лишь от раскладки нижних двенадцати карт циферблата и совершенно не зависит от раскладки остальных сорока карт (включая группу короля)!
Давайте проверим это утверждение. Выложите карты на циферблат согласно рис. 2.
Рис. 2
Теперь переверните их картинкой вниз и добавьте в любом порядке к каждой из карт циферблата по три карты, а в центр положите четыре карты. Пасьянс должен обязательно сойтись.
Д. Кнат утверждает, что проверку сходимости пасьянса можно проводить построением диаграммы типа «дерево» — той самой диаграммы, которую математики охотно применяют в таких различных областях, как строение вещества, электрические сети, теория вероятностей, биологическая эволюция, исследование операций и все виды проблем комбинаторики.
В самом деле. Обратимся к рисунку 2 и укажем стрелками распределение имеющихся там карт по своим местам. Так, от пятерки с места Демы (12 часов) надо протянуть стрелку к цифре 5 циферблата, от цифры 5 (там лежит восьмерка) к цифре 8 и т. д. Получится картина, показанная на рис. 2 и рис. З.
Рис. З
Рисунок 3 «развернем» в виде дерева (рис. 4), в котором выявлены все связи, все перемещения нижних карт циферблата.
Рис. 4
В том случае, если все 13 групп войдут в одно дерево, пасьянс сойдется. Если же дерево распадется на отдельные веточки, пасьянс не выйдет.
Вы имеете возможность убедиться этом, составив дерево для трех предлагаемых раскладок нижних карт пасьянса и проверив затем свои предположения решением пасьянса задач — 1, 2 и З.
Задача 1.
Задача 2.
Задача 3.
Загадка о часах — три и семь ударов
Видео: Загадка инцидент на железнодорожных путях
Часы Масляный насос Jacob & Co.