Математики нашли самый худший способ вешать картину

Представьте себе картину с веревочкой на обратной стороне, которую вешают на два гвоздя. Если убрать один из них, она продолжит висеть, хотя уже и не так ровно. В 1997 году учитель математики Александр Спивак предложил задачу: можно ли повесить картину так, чтобы вытаскивание любого из гвоздей приводило к ее падению? С тех пор эта загадка разрослась в целое семейство увлекательных головоломок.

Математик и информатик Том Верхуфф впервые столкнулся с такими задачами на мастер-классе для школьников в летнем математическом лагере. Ребята экспериментировали с настоящими веревками и карабинами, а заодно перевели задачу на язык символов.

В 2012 году математики опубликовали препринт, в котором доказали, что решения существуют для любой задачи вида «k из n»: есть n гвоздей, и удаление любых k из них (но не меньше) заставит картину упасть. Однако известные решения часто требуют чрезвычайно замысловатых обертываний веревки. На том мастер-классе Верхуфф вместе с участниками взялись за задачу «2 из 4» — картину должны ронять любые два гвоздя из четырех. Им удалось сократить длину самого короткого из известных решений с 80 обертываний вокруг гвоздей до 58.

Позже Верхуфф довел эту длину до 18, а затем, при помощи тогда еще аспиранта Йенса Хёйсвелдта и компьютерной программы — до абсолютного минимума в 16 обертываний. Сначала Верхуфф показал Хёйсвелдту программу, которая решала задачу примерно за два часа.

«Я сказал ему, что моя справляется за две секунды. А теперь его программа работает еще быстрее, чем моя», — рассказал Хёйсвелдт.

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

Напрашивается резонный вопрос: зачем все это нужно? На самом деле, в основе задачи лежат глубокие связи с теорией групп, теорией узлов, теорией графов и другими разделами математики. Например, в случае «1 из n» решения можно описать как петли, проведенные по ребрам n-мерного куба так, что они проходят через каждую вершину. Кроме того, можно найти подвешивания для любого «разумного» набора правил падения картины — скажем, нельзя потребовать, чтобы картина падала при удалении только гвоздя A, но оставалась висеть при удалении A и B вместе. Эти правила в точности соответствуют монотонным булевым функциям — важнейшему классу функций в таких областях, как криптография и теория голосования.

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