Sākums

LV.NOL.2021.12.5   lv

Taisnstūrveida rūtiņu tabulā ar \(n\) rindām un \(m\) kolonnām (\(n>1\), \(m>1\)) katrā rūtiņā ierakstīts atšķirīgs naturāls skaitlis. Sākumā rūtinās ierakstītie skaitļi pa rindām bija sakārtoti augošā secībā (katrā rindā visi skaitļi no katras rūtiņas pa labi ir lielāki, bet pa kreisi - mazāki nekā tajā esošais skaitlis). Pēc tam visas kolonnas sakārtoja augošā secībā (katrā kolonnā visi skaitli virs katras rūtinas ir mazāki, bet zem - lielāki nekā tajā esošais skaitlis). Pierādīt, ka pēc pārkārtošanas tabulā ierakstītie skaitlii pa rindām joprojām ir sakārtoti augošā secībā.

Hide solution

Atrisinājums-1

Pieņemsim pretējo, ka kāda rinda vairs nav sakārtota augošā secībā. Aplūkosim pirmo nesakārtoto rindu, tās kārtas numuru apzīmēsim ar \(i\). Tas nozīmē, ka visas rindas no pirmās līdz \((i-1)\)-ajai ir sakārtotas, bet \(i\)-ā rinda nav sakārtota.

Tātad šajā rindā ir divi tādi elementi \(x_{i}\) un \(y_{i}\), ka \(x_{i}\) atrodas pa kreisi no \(y_{i}\), bet \(x_{i}>y_{i}\). Aplūkosim kolonnas \(X\) un \(Y\), kurās atrodas attiecīgi \(x_{i}\) un \(y_{i}\), apzīmēsim to elementus attiecīgi ar \(x_{k}\) un \(y_{k}(1 \leq k \leq n)\).

Tā kā visas iepriekšējās rindas ir sakārtotas, tad \(x_{1}<y_{1}, x_{2}<y_{2}, \ldots, x_{i-1}<y_{i-1}\) (bet \(x_{i}>y_{i}\)). Tā kā kolonnas ir sakārtotas, tad tas nozīmē, ka kolonnā \(X\) ir tieši \((i-1)\) skaitlis \(\left(x_{1}, x_{2}, \ldots, x_{i-1}\right)\), kas ir mazāks nekā \(y_{i}\). Bet katrs no \(i\) skaitliem \(y_{1}, y_{2}, \ldots, y_{i}\) sākumā atradās vienā rindā ar kādu skaitli no kolonnas \(X\), kas par to ir mazāks, tātad tādiem skaitļiem jābūt vismaz skaitā \(i\) - pretruna.

Līdz ar to esam pierādījuši, ka arī pēc pārkārtošanas skaitļi pa rindām ir sakārtoti augošā secībā.

Atrisinājums-2

Aplūkosim, kā iespējams veikt prasīto skaitļu sakārtošanu pa kolonnām, kārtošanas procesā nepazaudējot sakārtojumu pa rindām. Skaidrs, ka pēc visu kolonnu sakārtošanas pirmajā rindā katrā kolonnā jābūt šīs kolonnas vismazākajam skaitlim.

Aplūkojam sākotnējās tabulas pirmo kolonnu un atrodam tajā vismazāko skaitli.

Pienemsim, ka mazākais skaitlis atrodas \(K\)-tajā rindā.

Samainīsim vietām pirmo un \(K\)-to rindu (skat. 9. att.). Ja kolonnas mazākais skaitlis jau bija pirmajā rindā, tad šis solis ir jāizlaiž. Esam ieguvuši, ka pirmajā kolonnā mazākais skaitlis atrodas pirmajā rindā un visas rindas joprojām ir sakārtotas augoši (jo katras rindas saturs ir iepriekšējais - mainīta ir tikai to secība).

Tagad aplūkojam otro kolonnu. Pieņemsim, ka mazākais skaitlis atrodas \(L\)-tajā rindā. Paņemsim 1. un \(L\)-tās rindas fragmentus no otrās kolonnas līdz beigām (\(M\)-tajai kolonnai) un samainīsim vietām (skat. 10. att.).

Pārliecināsimies, ka arī pēc šādas maiņas gan pirmā, gan \(L\)-tā rinda joprojām ir sakārtotas augoši.

Neatbilstība var rasties tikai starp rindas pirmo un otro skaitli - tālāk nekas netika mainīts. Pienemsim, ka pirms maiņas pirmās rindas pirmajā un otrajā kolonnā bija skaitļi \(p_{1}\) un \(p_{2}\), bet \(L\)-tajā - skaitļi \(l_{1}\) un \(l_{2}\). Šiem skaitļiem ir spēkā sakarības: \(p_{1}<p_{2}\) un \(l_{1}<l_{2}\) (sakārtojums pa rindām) un \(p_{1}<l_{1}\) un \(l_{2}<p_{2}\) (pirmo divu kolonnu mazākie skaitļi). Tātad ir spēkā arī \(p_{1}<l_{2}\) un \(l_{1}<p_{2}\), kas nozīmē, ka šo divu fragmentu samainīšana vietām saglabā sakārtojumu pa rindām.

Analoǵiski panākam, ka pirmās rindas trešais, ceturtais, ..., \(M\)-tais skaitlis ir mazākie savā kolonnā, katru reizi samainot vietām rindu fragmentus no vajadzīgās kolonnas līdz rindas beigām, bet skaitļus kolonnās pa kreisi neaiztiekot.

Kad šādi pirmajā rindā augošā secībā esam izvietojuši kolonnu mazākos skaitļus, varam par šo rindu aizmirst un atkārtot tādu pašu sakārtošanas procesu par vienu rindu mazākai tabulai - tai, ko iegūstam paņemot tabulas rindas no otrās līdz \(N\)-tajai.

Kad šādi būsim tikuši līdz beigām (pēdējā posmā sakārtojot divas rindas), gan kolonnas, gan rindas būs sakārtotas augošā secībā. Tas nozīmē, ka arī pēc kolonnu sakārtošanas skaitļi tabulas rindās ir sakārtoti.