Uvažujme následující graf G. Vrcholy grafu budou odpovídat jednotlivým dílům N-úhelníka, přičemž dva vrcholy budou spojeny hranou, pokud jim odpovídající díly mají společnou stranu. Graf G zřejmě bude souvislý a navíc nebude obsahovat žádný cyklus. Uvnitř cyklu by totiž ležela alespoň jedna stěna grafu G. Té musí odpovídat nějaký průsečík v nakresleném N-úhelníku. Tento průsečík však rozhodně nemůže ležet na okraji N-úhelníka, a máme tak spor s tím, že žádné dvě tětivy se neprotínají.
Souvislý graf bez cyklů je strom a naše úloha se tím zjednodušuje na nalezení maximální nezávislé množiny vrcholů (tj. takové množiny vrcholů, že žádné dva vrcholy z této množiny nejsou spojeny hranou) ve stromu. Maximální nezávislou množinu můžeme určit prohledáváním do hloubky. Na počátku si označíme všechny vrcholy jako přijatelné do nezávislé množiny. Začneme v libovolném vrcholu prohledávat strom. Když se vracíme z nějakého vrcholu, který je označen jako přijatelný, přidáme ho do nezávislé množiny a jeho otce odznačíme. Když takto projdeme celý graf, máme vybranou maximální nezávislou množinu. Nezávislost vybrané množiny je zřejmá. Proč ale bude vybraná množina maximální? Označme si vybranou nezávislou množinu A a dále si vezměme maximální nezávislou množinu B, která se od naší vybrané množiny liší v nejméně vrcholech. Nyní se podívejme na takový vrchol v, ve kterém se A a B liší a který je nejvzdálenější od vrcholu, ve kterém začalo prohledávání do hloubky. Případ, kdy v je v B a ne v A, nastat nemůže, protože když jsme nějaký vrchol v nevzali do A, tak pouze proto, že byl sousedem nějakého vrcholu u pod ním zařazeného do A. Protože v je nejvzdálenější vrchol, ve kterém se A a B liší, musí být u obsažen i v B, a tedy B také nemůže obsahovat v. Může tedy nastat pouze situace, že v je obsažen v A a není obsažen v B. Pokud ale v přidáme do B a z B vyřadíme otce v (pokud v ní byl), bude B stále maximální nezávislá množina a přitom se bude lišit v méně vrcholech, což je spor s výběrem B. Vybraná nezávislá množina A musí být proto skutečně maximální.
Zkonstruovat výše popsaný graf a na něm pak provést prohledání do hloubky je zbytečně pracné. My budeme graf prohledávat bez jeho explicitní konstrukce. Nejdříve si tětivy zorientujeme tak, aby každá tětiva začínala ve vrcholu s nižším číslem a přidáme pomocnou tětivu začínající v prvním a končící v posledním vrcholu. Tětivy si pomocí přihrádkového třídění setřídíme vzestupně podle jejich počátku, tětivy začínající ve stejném vrcholu pak sestupně podle jejich konce. Nyní postupně procházíme vrcholy N-úhelníku v pořadí od vrcholu s číslem jedna po vrchol s číslem N. Při procházení si udržujeme zásobník s tětivami, od nichž jsme viděli začátek, ale ne konec. U každé tětivy na zásobníku si navíc pamatujeme, zda je přijatelná. Vždy, když začneme zpracovávat nový vrchol, nejdříve ze zásobníku odebereme tětivy, které v tomto vrcholu končí. Pokud je odebíraná tětiva označena jako přijatelná, zvětšíme velikost nezávislé množiny a odznačíme tětivu pod ní v zásobníku. Po odebrání všech končících tětiv přidáme na zásobník všechny tětivy začínající v daném vrcholu a označíme je jako přijatelné. Pak pokračujeme do dalšího vrcholu N-úhelníku. Výpočet skončíme po projití všech vrcholů N-úhelníku.
Uvedený algoritmus přesně odpovídá dříve popsanému prohledávání do hloubky. Každá tětiva totiž jednoznačně koresponduje s hranou v grafu, která spojuje vrcholy odpovídající dílům odděleným tětivou. Uložení pomocné tětivy (1,N) na zásobník odpovídá vstupu do vrcholu, ze kterého začínáme prohledávání. Uložení další tětivy na zásobník odpovídá přejití po odpovídající hraně dolů (směrem od vrcholu, ve kterém začalo prohledávání), vybrání tětivy ze zásobníku pak návratu zpět po hraně. Při prohledávání do hloubky jsme si označovali vrcholy, které lze přidat do nezávislé množiny. V upraveném algoritmu místo vrcholu značíme tu hranu, po které jsme do vrcholu poprvé vstoupili. Algoritmus má časovou i paměťovou složitost O(N) (tětiv nikdy nemůže být více než N-3).
Základem programu bude rekurzivní procedura vytvor(prvni,posledni), která vytvoří jednosměrný spojový seznam popsaný v prvním odstavci. Tento seznam bude obsahovat všechny mince s čísly od prvni do posledni. Pokud jsou čísla prvni a posledni shodná, procedura vytvoří jednoprvkový seznam. Jeho jediný prvek bude ukazovat na strom tvořený jedním uzlem, který bude obsahovat číslo prvni=posledni. Pokud jsou čísla prvni a posledni různá, procedura nejdříve rozdělí interval tvořený čísly od prvni do posledni na dva intervaly polovičních délek a na každý z nich se rekurzivně zavolá. Takto získáme dva lineární spojové seznamy s vlastnostmi popsanými v prvním odstavci. Z nich naše procedura vytvoří jeden.
Výsledný seznam budeme vytvářet od začátku, a to následujícím způsobem: Na některou z mincí ve stromě hlavy (tj. prvního prvku) prvního ze seznamů a na některou z mincí ve stromě hlavy druhého seznamu zavoláme funkci |porovnej|. Pokud je mince hlavy prvního seznamu lehčí, odpojíme hlavu od prvního seznamu a připojíme ji na konec výsledného seznamu; poté pokračujeme porovnáním hlav nově vzniklé dvojice seznamů. Pokud je naopak mince hlavy druhého seznamu lehčí, připojíme na konec výsledného seznamu hlavu druhého seznamu a pokračujeme s druhým seznamem bez jeho původní hlavy. Zbývá případ, kdy mince obou hlav mají stejnou hmotnost. V tomto případě připojíme na konec výsledného seznamu prvek, který ukazuje na strom, jehož levý podstrom je strom hlavy prvního seznamu a pravý podstrom je strom hlavy druhého seznamu; od obou seznamů následně odpojíme jejich hlavy. Takto pokračujeme, dokud jeden nebo oba z našich dvou seznamů nejsou prázdné. Pokud je jeden z nich neprázdný, nezapomeneme ho připojit na konec výsledného seznamu.
Vytvořit celý program je nyní již snadné: Nejprve ze souboru vahy.in načteme počet mincí N. Poté zavoláme proceduru porovnej s parametry prvni=1 a posledni=N. Nakonec vypíšeme čísla v listech stromů (zleva doprava) ve výsledném seznamu; každý strom vypíšeme na samostatný řádek souboru vahy.out, a to v pořadí, v jakém stromy odpovídají prvkům seznamu. Čísla na každém řádku jsou setříděna (z konstrukce stromů patřícím prvkům seznamu) a hmotnosti mincí v pořadí dle řádků jsou rostoucí (dle vlastností vytvářeného seznamu). Zbývá si rozmyslet, že náš algoritmus neprovádí zbytečné volání funkce porovnej, a určit jeho časovou složitost.
Nejprve dokážeme indukcí dle délky intervalu určeného parametry při volání procedury vytvor, že náš program neprovádí zbytečné volání funkce porovnej. Procedura vytvor volá funkci porovnej pouze na dvojice prvků z intervalu specifikovaného parametry procedury vytvor. Pokud je tento interval jednoprvkový, dokazované tvrzení platí z triviálních důvodů. V opačném případě, se nejprve vytvoří dva seznamy rekurzivním voláním procedury vytvor a ty se následně sloučí. Při slučování dvou seznamů je funkce porovnej volána pouze na dvojice mincí z různých seznamů (tedy výsledek takového volání není určen výsledky volání funkce porovnej při rekurzi). Vzhledem k tomu, že porovnáváme z každého seznamu minci s nejmenší vahou (a mince s menšími vahami jsme zařadili již do výsledného seznamu), nemůže být vztah hmotností mincí z dotazované dvojice určen předchozími dotazy. Můžeme tedy uzavřít, že žádné volání funkce porovnej není zbytečné.
Hloubka rekurzivního volání procedury vytvor je O(log N) (N je počet mincí), neboť při každém volání se délka intervalu specifikovaného parametry funkce zmenší na polovinu. Na sloučení dvou seznamů je třeba čas úměrný délce výsledného seznamu. Protože na každé úrovni volání se libovolná mince vyskytuje právě v jednom seznamu, je čas strávený algoritmem během procedur vytvor na jedné úrovni rekurze lineární, tj. O(N). Celková časová složitost je tedy O(N log N). Libovolná mince se vyskytuje při běhu programu vždy právě v jednom seznamu, a tedy paměťová složitost programu je O(N).