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.\]
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.