Zadanie
Keď Sgt. Peppera nebavilo riešiť problémy iných, tak si vyrazil do lokálneho kasína ošklbať niekoho o peniaze. Toho dňa, kedy našiel stratený dobytok statkára Ritza, bola v ponuke takáto hra:
Na stole máme karty s hodnotami od \(1\) po \(13\) v nejakom poradí. Postupne ťaháme karty z balíčka a ukladáme na kôpky. Kôpky musia byť rastúce (novú kartu môžeme položiť len na kartu s menším číslom) a kartu ukladáme vždy na kôpku s najvyšším možným číslom, lícom nahor. Ak taká kôpka neexistuje, vytvoríme novú. Keď vyložíme všetky karty, dáme kôpky na seba (postupne od najnovšej na spodku po najstaršiu na vrchu), otočíme (čím získame opäť balíček kariet, ktoré sú lícom nadol) a hráme znovu.
Kasíno vehementne hlásilo, že dá 100$ tomu, komu sa podarí nájsť také poradie kariet, ktoré sa týmto spôsobom usporiadať nedajú. Dokážte, že také poradie neexistuje a karty sa po niekoľkých opakovaniach vždy usporiadajú.
Proces ťahania a ukladania kariet a zbierania nazveme kolom. Nech v balíčku je \(n\) kariet, úlohu dokážeme pre ľubovoľné \(n\).
Možno si všimnúť nasledovný invariant1 vzhľadom na počet kôl: Predpokladajme, že máme na stole v nejakom momente počas ťahania a ukladania kariet aspoň \(2\) kôpky \(P, Q\), nech čísla na vrchu týchto kôpok sú \(p, q\). Nech platí, že kôpka \(P\) sa objavila na stole skôr ako \(Q\). Potom platí \(p > q\). Toto teraz dokážeme.
Najprv potrebujeme dokázať, že to platí v momente, keď sa na stole prvýkrát spolu objavia dané \(2\) kôpky \(P, Q\). Majme teda kôpku \(P\) s číslom \(p\) navrchu a práve nám vznikla kôpka \(Q\) s číslom \(q\). Z balíčka sme vytiahli kartu s číslom \(q\). Zrejme nemôže platiť \(p = q\). Keby platilo \(p < q\), kartu s číslom \(q\) by sme uložili na vrch kopy \(P\). Preto musí platiť \(p > q\).
Teraz dokážeme, že ak v istom momente invariant platí pre všetky dvojice kôpok, bude platiť aj keď vytiahneme kartu z balíčka a uložíme ju na príslušnú kôpku. Vezmime si opäť konkrétnu dvojicu kôpok \(P, Q\) s číslami \(p, q\) navrchu, pričom \(P\) sa objavila na stole skôr. Nech z balíčka vytiahneme kartu s číslom \(r\). Ak túto kartu neuložíme ani na jednu z \(P, Q\), invariant bude ďalej platiť. Ak kartu uložíme na kôpku \(Q\), zrejme musí platiť \(r < p\), ináč by sme porušili pravidlá zadania. Teda v tomto prípade invariant platí. Ak kartu uložíme na kôpku \(P\), musí platiť \(r > p\), a teda keďže platí \(p > q\), vieme, že platí aj \(r > q\).
Teda invariant platí vždy.
Indukciou vzhľadom na \(k\) dokážeme, že po \(k\) kolách sa budú nachádzať na \(k\) posledných miestach v balíčku karty s číslami \[n, n - 1, \dots , n - k + 1.\]
Nech \(k = 0\), vtedy tvrdenie nehovorí nič, a teda je pravdivé.
Nech tvrdenie platí pre nejaké \(k\).
Z indukčného predpokladu, na začiatku \(k+1\)-ého kola sa na posledných \(k\) miestach v balíčku nachádzajú karty s číslami \(n, n - 1,\dots, n - k + 1\). Po ťahaní \(n - k\) kariet z balíčka budú na stole karty \(1, \dots, n - k\). Karta s číslom \(n - k\) musí byť podľa invariantu na najstaršej kôpke. Podľa pravidiel zo zadania ostatné karty z balíčka s číslami \(n, \dots, n - k + 1\) uložíme práve na túto kôpku. Po zozbieraní všetkých kôpok sa tak karta s číslom \(n - k\) dostane pred kartu s číslom \(n - k + 1\). Tvrdenie teda platí aj pre \(k + 1\).
Po opakovaní \(n\) kôl sa v balíčku budú nachádzať vzostupne usporiadané karty.
Vlastnosť ktorá sa nemení, zostáva rovnaká.↩︎
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.