LV.AMO.2005.9.5 lv
Doti \(3\) stienīši. Uz viena no tiem sākotnēji uzmaukti \(n\) dažādu izmēru diski ar caurumiem vidū tā, ka to rādiusi samazinās no lejas uz augšu; abi pārējie stienīši sākotnēji ir tukši (skat. 1.zīm., kur \(n=6\)).
Ar vienu gājienu var pārlikt augšējo disku no jebkura stienīša uz jebkuru citu, ja tikai pārliekamais disks \(D\) nav lielāks par to disku, kas atrodas pašā apakšā uz stienīša, uz kuru pārliek \(D\).
Ar kādu mazāko gājienu skaitu var panākt, lai visi diski atrastos uz stienīša \(C\) tādā pašā kārtībā, kādā tie sākotnēji atradās uz stienīša \(A\)?
Atrisinājums
Apzīmēsim meklējamo skaitu ar \(x_{n}\) (skaidrs, \(x_{1}=1\)). Ar \(y_{n}\) apzīmēsim minimālo gājienu skaitu līdzīgā uzdevumā, kura vienīgā atšķirība - uz \(C\) diskiem nav jābūt tādā pašā secībā kā sākotnēji uz \(A\) (tātad lielākajam diskam tomēr ir jābūt apakšā). Skaidrs, ka \(y_{1}=1\).
Lai atrisinātu izmainīto uzdevumu, vajag pārcelt \(n-1\) diskus uz \(B\), tad apakšējo disku uz \(C\), tad \(n-1\) gājienos atlikušos diskus uz \(C\). Tas prasa \(y_{n-1}+1+(n-1)\) gājienus. Tātad \(y_{n}=y_{n-1}+n\). Tāpēc \(y_{n}=1+2+\ldots+n=\frac{1}{2} n(n+1)\).
"Īstajā" uzdevumā vajag vispirms pārcelt \(n-1\) diskus uz \(B\), tad apakšējo disku uz \(C\) un tad \(n-1\) atlikušos diskus uz \(C\), atcerieties, ka uz \(C\) vajag sākotnējo secību. Ar kursīvu izceltās daļas operācijas izpildot apgrieztā secībā, iegūstam izmainītā uzdevuma risinājumu \(n-1\) diskiem. Tāpēc \(x_{n}=y_{n-1}+1+y_{n-1}=2y_{n-1}+1=2 \cdot \frac{1}{2}(n-1)n+1=n^{2}-n+1\).