Foto: Magnific

Když obraz zavěsíte provázkem na dva hřebíky běžným způsobem a jeden vytáhnete, nic dramatického se většinou nestane. Obraz zůstane viset na druhém. Matematik A. Spivak ale už v roce 1997 položil mnohem zákeřnější otázku: lze provázek vést tak, aby po odstranění kteréhokoli z obou hřebíků obraz okamžitě spadl?

Odpověď zní ano. Zdánlivě jednoduchá hádanka se navíc postupně změnila v celou skupinu matematických problémů, u kterých už nestačí vzít do ruky kladivo a několik metrů provázku.

Ze dvou hřebíků se staly čtyři

Jednou z variant je takzvaný problém k-out-of-n. Máme určitý počet hřebíků a chceme obraz zavěsit tak, aby zůstal na stěně při odstranění menšího počtu z nich, ale spadl po vytažení libovolné stanovené kombinace.

Matematici už v roce 2012 ukázali, že taková řešení lze sestrojit obecně. Háček je v tom, že výsledné vedení provázku může být mimořádně komplikované.

Právě tím se zabýval počítačový vědec Tom Verhoeff. Při práci s variantou 2 ze 4, kdy obraz visí na čtyřech hřebících a musí spadnout po odstranění libovolných dvou, se podařilo původní známé řešení o délce 80 zkrátit nejprve na 58 a později na pouhých 18.

Verhoeff následně spolupracoval s tehdejším doktorandem Jensem Heuseveldtem. Pomocí počítačového programu prověřili kratší možnosti a dostali se na hodnotu 16. Nejde přitom pouze o další nalezené řešení. Vyčerpávající počítačové hledání ukázalo, že kratší varianta neexistuje.

Za provázkem se skrývá překvapivě vážná matematika

Celá úloha zní jako matematický vtip, její principy ale zasahují do teorie grup, teorie uzlů i teorie grafů. Jednotlivá vedení provázku lze převést do matematického zápisu a zkoumat bez skutečných hřebíků nebo obrazu.

Picture-hanging problémy mají také spojení s monotónními booleovskými funkcemi. Ty se objevují mimo jiné v kryptografii nebo teorii hlasovacích systémů. Neznamená to, že nový způsob věšení obrazů změní zabezpečení počítačů. Ukazuje však, jak se z jednoduché hry může stát problém propojující několik různých oblastí matematiky.

Verhoeff proto odmítá pohled, že podobné úlohy musejí mít okamžité praktické využití. Hraní si s problémem je podle něj samo o sobě jedním ze způsobů, jak se učíme. V tomto případě k tomu stačily čtyři hřebíky, provázek a otázka, jak obraz pověsit co možná nejhůř.

Zdroj: ScientificAmerican.com