Koniec kola: 25. november 2019 23:59
4 days
Počet bodov:
Popis:  10b

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.