Sākums

LV.SOL.2014.12.5   lv

Rindā ir \(12\) krēsli; uz katra no tiem sēž pa skolēnam. Skolēniem vienu reizi atļauts piecelties un apsēsties citā secībā, pie tam katrs drīkst apsēsties vai nu iepriekšējā vietā, vai tieši blakus iepriekšējai vietai.
Cik dažādi skolēnu izvietojumi iespējami pēc pārkārtošanās?

Hide solution

Atrisinājums

Apzīmēsim atbilstošu pārkārtojumu skaitu \(n\) skolēnu gadījumā ar \(a_n\). Acīmredzami, \(a_1=1\) un \(a_2=2\).

Apskatīsim \(n+2\) skolēnus un meklēsim formulu, kas izsaka \(a_{n+2}\) ar \(a_n\) un \(a_{n+1}\). Visi pārvietojumi iedalās divās daļās:

a) pirmais skolēns paliek uz vietas. Tad pārkārtojas tikai atlikušie \(n+1\) skolēni. Šādu pārkārtojumu pēc definīcijas ir \(a_{n+1}\).

b) pirmais skolēns pāriet uz otro krēslu. Tad uz pirmo krēslu pāriet skolēns no otrā krēsla. Pārējie \(n\) skolēni pārkārtojas "savā starpā". Tādu pārkārtojumu pēc definīcijas ir \(a_n\).

Tātad \(a_{n+2}=a_{n+1}+a_n\). Iegūstam \(a_3=1+2=3\), \(a_4=5\), \(a_5=8\), \(a_6=13\), \(a_7=21\), \(a_8=34\), \(a_9=55\), \(a_{10}=89\), \(a_{11}=144\), \(a_{12}=233\).