Sākums

LV.SOL.1996.12.5   lv

Dotas \(2^n\) kartiņas, \(n\) – naturāls skaitlis. Tās sakārtotas kaudzītē. Ar vienu gājienu kaudzīti var pārdalīt patvaļīgā vietā un pēc tam abas iegūtās daļas "sajaukt" savā starpā tā, ka iepriekšējās "augšējās" daļas kartīšu savstarpējais novietojums paliek nemainīgs un iepriekšējās "apakšējās" daļas kartīšu savstarpējais novietojums – tāpat.
Pierādīt, ka ar \(n\) gājieniem pietiek, lai iegūtu jebkuru mums vēlamu kartīšu sakārtojumu.

Hide solution

Atrisinājums

Piešķirsim kartiņām numurus \(1;2;\ldots;2^n\) tādā kārtībā, kādā tām jāparādās beigās (no apakšas uz augšu). Apskatīsim sākotnējo sakārtojumu no apakšas uz augšu. Kartiņas numuri izvietojušies kaut kādā secībā. Sadalīsim tos monotoni augošos fragmentos; šādu fragmentu sākumā nav vairāk par \(2^n\). Pieņemsim, ka fragmentu skaits ir \(k\). Sadalīsim kaudzīti divās daļās tā, lai augšējā daļā būtu \(\left[\frac{k}{2}\right]\) monotoni fragmenti. Pēc tam daļas apvienojam tā, ka abu daļu apakšējie monotonie fragmenti tagad veido vienu monotonu fragmentu, nākošie abu daļu monotonie fragmenti arī veido vienu monotonu fragmentu nav vairāk par \(2^{n-1}\). Atkārtojot šādas operācijas, pēc \(n\) gājieniem būs \(1\) monotons fragments, t.i., kartiņas būs novietotas vajadzīgajā kārtībā.