Problem dwóch gwoździ, czyli matematycy odkrywają najgorsze sposoby wieszania obrazu
Informatyk Tom Verhoeff po raz pierwszy zajął się tymi zagadnieniami w ramach zajęć z uczniami szkół podstawowych na obozie matematycznym. Eksperymentowano z realnymi rekwizytami, ale też wprowadzano symbolikę.
W 2012 roku został opublkowany preprint dowodzący istnienia rozwiązań dla każdego problemu typu „k z n” (gdzie n to liczba gwoździ, a usunięcie przynajmniej k dowolnych spowoduje, że obraz spadnie). Znane rozwiązania mogą jednak wymagać skomplikowanych sposobów zapętlania sznurka. Uczestnicy warsztatów Verhoeffa zmierzyli się z problemem „2 z 4” (obraz spada po usunięciu dowolnych dwóch z czterech gwoździ) i zmniejszyli najkrótsze znane wówczas rozwiązanie z 80 do 58 owinięć sznurka wokół gwoździ.
Później Verhoeff zredukował tę liczbę do 18, a z pomocą doktoranta Jensa Heuseveldta oraz przy wykorzystaniu programu komputerowego, sprawdzającego wszystkie prostsze układy, osiągnął absolutne minimum – 16 owinięć. Początkowo Verhoeff pokazał Heuseveldtowi program rozwiązujący problem w blisko dwie godziny. „Powiedziałem mu wtedy, że mój program potrafi rozwiązać to zadanie w dwie sekundy” – wspomina Heuseveldt i dodaje: „a teraz jego program działa szybciej niż mój”. Verhoeff opublikował wyniki swoich badań i najkrótsze znane rozwiązania całej gamy tego typu problemów w serwisie preprintów arXiv.org.
Dlaczego matematycy interesują się takim zawiłym, dziwacznym wieszaniem obrazów? Choć samo sformułowanie problemu brzmi zabawnie, stanowi on zagadnienie ściśle związane z teorią grup, teorią węzłów, teorią grafów i innymi dziedzinami matematyki. Na przykład, rozwiązania wariantu „1 z n” można opisać jako pętle poprowadzone wzdłuż krawędzi n-wymiarowego sześcianu, przechodzące przez każdy jego wierzchołek. Co więcej, dla każdego „sensownego” zestawu reguł określających warunki upadku obrazu można znaleźć odpowiedni sposób jego zawieszenia; nie można na przykład wymagać, by usunięcie tylko gwoździa A powodowało upadek obrazu, podczas gdy usunięcie gwoździ A i B pozwalałoby mu nadal wisieć. Reguły te odpowiadają dokładnie monotonicznym funkcjom boolowskim – kluczowemu rodzajowi funkcji stosowanych w takich dziedzinach, jak kryptografia czy teoria głosowania.
Jednak zdaniem Verhoeffa pytanie o użyteczność tego problemu jest niewłaściwe, bowiem „jako ludzkość nie wiemy, dokąd zmierzamy ani co będzie nam potrzebne do przetrwania, a zabawa to jeden ze sposobów, w jaki się uczymy”.