Atrisinājums

Apzīmēsim papagaiļus ar numuriem no \(1\) līdz \(38\) un krātiņus ar numuriem no \(1\) līdz \(39\) tā, ka sākotnēji papagaiļa numurs sakrīt ar krātiņa numuru. Vienkāršības dēļ tukšajā vietā sākumā ieliksim iedomātu papagaili ar numuru \(39\). N̦emsim patvaļīgu papagaili \(a_{1}\), kas neatrodas savā krātiņā, pieņemsim, ka tas atrodas krātiņā \(a_{2}\). Tad \(a_{2}\) arī neatrodas savā vietā un atrodas kādā vietā \(a_{3}\), utt, līdz papagailis \(a_{n}\) atrodas vietā \(a_{1}(2 \leq n \leq 39)\). Tādā veidā visi papagaiļi sadalās ciklos. Ja ciklā ir \(n\) papagaiļi, tad šī cikla sakārtošanai nepieciešams tieši

(A) \(n-1\) gājiens, ja tajā ietilpst tukšais krātiņš. Tad tur ir \(n-1\) papagailis un ar katru gājienu ne vairāk kā vienu var ielikt savā krātiņā, tātad mazāk gājienu nevar būt. Ar \(n-1\) gājienu pietiek, jo vienmēr būs kāds papagailis, kuru ielikt savā vietā;
(B) \(n+1\) gājiens, ja tajā neietilpst tukšais krātiņš. Ar pirmo gājienu nevienu papagaili nevar ielikt savā vietā un ar katru nākamo gājienu ne vairāk kā vienu papagaili var ielikt savā vietā, tāpēc mazāk būt nevar. Pirmajā gājienā jebkuru papagaili pārceļ uz tukšo krātiņu, atlikušos \(n-1\) sakārto kā (A) gadījumā ar \(n-1\) gājienu un pēdējā gājienā ieceļ savā vietā to, kuru pārcēla pirmo.

Tātad kopējais nepieciešamais gājienu skaits ir

• papagaiļu skaits + ciklu skaits, ja nevienā ciklā neietilpst tukšais krātiņš
• papagaiļu skaits + ciklu skaits - \(1\), ja kādā ciklā ietilpst tukšais krātiņš.

Redzams, ka maksimālais gājienu skaits būs nepieciešams tad, kad ciklu skaits ir maksimālais un nevienā ciklā neietilpst tukšais krātiņš. Minimālais papagaiļu skaits ciklā ir \(2\), tāpēc maksimālais ciklu skaits ir \(38:2=19\), tātad maksimālais gājienu skaits, kāds var būt nepieciešams, ir \(38+19=57\) gājieni. Redzam: ja papagaiļus samaina vietām pa pāriem, tad tieši tik daudz gājieni arī ir vajadzīgi.