Max Home IndustryВот головоломка, которую просто просят превратить в популярную браузерную игру. Это следующий поворот в Cut the Rope?
Ученые-информатики, математики и программисты часто разделяют любовь к головоломкам и находят удовольствие придумывать новые. В недавней исследовательской работе группы известных людей, в том числе Эрика и Мартина Демейна и Рональда Ривеста, исследуется не очень известная головоломка с изображением висячих изображений и несколько ее вариантов. Учитывая нынешний интерес к таким играм, как Cut the Rope, это могло быть источником более чем одной новой компьютерной игры.
Базовую головоломку легко сформулировать — все, что вам нужно сделать, это повесить картину с помощью гвоздей и обернуть веревку вокруг гвоздей так, чтобы картинка упала, когда будут удалены все k гвоздей.
Первоначальная версия головоломки была создана в 1997 году А. Спиваком и состояла всего из двух гвоздей. Удалите любой гвоздь, и изображение упадет. Вы можете увидеть решение ниже, как показано в документе:
Идея очевидна — сделайте петли вокруг гвоздей так, чтобы при удалении одного из гвоздей веревка была распущена.
Самая общая версия головоломки спрашивает, что изображение падает, когда удаляются определенные подмножества гвоздей. Новое исследование показывает, что у этой обобщенной головоломки всегда есть решение. Единственная проблема заключается в том, что доказательство включает в себя экспоненциально увеличивающееся количество поворотов вокруг гвоздей. Однако, если мы ограничим наше внимание k из n версий головоломки, то повороты будут расти только с полиномиальной скоростью по мере увеличения количества гвоздей.
Теория связана с обобщениями хорошо известных колец Борромео, которые связаны вместе, но разваливаются при удалении одного кольца:
Расположение из трех колец выше обеспечивает решение проблемы с двумя гвоздями. Обобщения дают решения проблемы с k = 1 n гвоздями. Вы можете увидеть решение для трех ногтей ниже.
Исследование устанавливает связь между головоломкой с изображением висящего изображения и теорией групп и монотонными булевыми функциями — так что, вероятно, где-то есть серьезное приложение. И, как вы, наверное, догадались, здесь есть что-то о теории сложности. В частности, у нас есть результат:
Для данной картины, висящей на гвоздях, попытка решить, есть ли k гвоздей, удаление которых приводит к падению изображения, является NP-Complete.
Газету интересно читать, и вы можете попробовать решить десять головоломок с картинками. Есть также несколько открытых теоретических вопросов, если вы действительно хотите копнуть глубже.
Так можно ли превратить эту забавную математику в игровую игру?
Я уже слышу звук падающих картинок.