Zadanie
Nutno uznať, že po prvom kole bol Matúš očarený Kubkovým šarmom a genialitou jeho kúzelníckych trikov. Ostávalo naozaj už len trošku, aby si Matúš uvedomil svoj veľký omyl a stiahol sa i so svojou armádou preč z Uhorska. Kubko vedel, čo bolo v stávke, no i tak sa rozhodol staviť všetko na jednu kartu - svoj ultimátny trik s kartami, ktorý ak vyjde, tak roztopí srdiečko každému, aj tomu najstrašnejšiemu kazisvetovi na svete.
Definícia. Keď máme v rade usporiadané karty \(1,\, 2,\, \dots,\, n\), tak dvojicu kariet \((a, b)\) voláme inverzia, pokiaľ \(a > b\) a karta s číslom \(a\) sa nachádza v rade skôr ako karta s číslom \(b\). Napríklad, v rade kariet \(3,1,4,2\) máme \(3\) inverzie: \((3,1)\), \((3,2)\), a \((4,2)\).
Kubko má \(n\) kariet očíslovaných číslami \(1,\,2,\,\dots,\, n\), ktoré má v nejakom poradí usporiadané v rade. Postupne pre \(i = 1, 2, \dots, n\) urobí Kubko nasledovnú operáciu: Zoberie kartu s číslom \(i\) a keď naľavo od nej je \(k\) kariet, tak ju presunie v rade tak, aby napravo od nej bolo \(k\) kariet. Dokážte, že bez ohľadu na to, s akým poradím kariet Kubko začínal, bude mať jeho výsledné poradie kariet rovnaký počet inverzií ako počiatočné poradie kariet.
Príklad. Pokiaľ Kubko začína s poradím \(3,1,4,2\), tak preusporiadavanie bude vyzerať nasledovne: \[3,1,4,2\to 3,4,1,2\to 2,3,4,1\to 2,4,3,1\to 2,3,4,1.\]
Po vyskúšaní si pár príkladov zistíme, že množstvo inverzií sa v každom kroku veľmi mení, nie je v ňom žiadny poriadok a na konci iba akoby zázrakom skočí vždy na správny počet inverzii. Môže nás to viesť k myšlienke, že na to bude treba ísť inak a bude treba vymyslieť nejaký trik.
Hlavná myšlienka je, že zadanú operáciu môžeme pozmeniť podľa našej ľubovôle, ak na konci dostaneme správne poradie kariet. Navyše, je celkom logické hľadať takú operáciu, ktorá v jednom kroku nemení počet inverzii. Keď už máme tento cieľ, po chvíli skúšania (hoci práve tento krok bol na úlohe to najťažšie), vyjde vhodná operácia nasledovná.
Definícia. Definujme si novú operáciu, ktorá zároveň s tým, že vymení poradie karty na opačnú pozíciu, navyše zväčší toto číslo o \(n\). Názornejšie to bude na príklade:
\[3,1,4,2\to 3,4,5,2\to 6,3,4,5\to 6,4,7,5\to 6,7,8,5\to 2,3,4,1.\]
Všimnime si dve veci. Prvá je, že po poslednom kroku sú karty usporiadané rovnako ako po pôvodných operáciach, ibaže sú všetky o \(n\) väčšie (keďže každú sme posunuli práve raz, teda raz sme pridali \(n\)). A teda finálne poradie bude mať presne rovnako veľa inverzií ako po pôvodných operáciach. Druhá je, nasledovná.
Lema. Po každom kroku novej operácie je počet inverzii rovnaký.
Dôvod je takýto: Zjavne krok môže ovplyvniť iba tie inverzie, ktoré obsahujú kartu, ktorú akurát presúvame.
V každom kroku presúvame kartu s najmenším číslom, a teda počet inverzií ktoré obsahujú túto kartu je práve počet kariet naľavo od nej. Po presune sa z nej stane najväčšia karta, a teda počet inverzií ktoré obsahujú túto kartu je práve počet kariet napravo od nej. Ale tieto dva počty sú rovnaké práve vďaka spôsobu akým ju presúvame.
Najnázornejšie je to znova na príklade. Vezmime si prvý krok \(3,1,4,2\to 3,4,5,2\). Inverzie obsahujúce \(1\) sú práve tie karty ktoré ležia naľavo od jednotky. Na druhej strane, inverzie obsahujúce \(5\) sú práve tie ktoré ležia napravo od \(5\)-ky. Tých je ale rovnako veľa, a teda počet inverzii sa nezmenil.
Vytvorili sme operácie ktoré majú rovnaký výstup a pri žiadnom kroku nezmenia počet inverzii. Takže finálne usporiadanie má rovnaký počet inverzii ako pôvodné.
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ť.