Dos solitaris

Bon dia!

Avui presentarem dos solitàris ben coneguts.

Les torres de Hanoi

Les torres de Hanoi és un solitari ideat per Edouard Lucas el 1883. El joc consisteix a passar totes les peces del pal de l'esquerra al de la dreta, seguint les regles següents: cada cop només es pot moure una peça i al moure una peça sempre s'ha de dipositar o bé en un pal buit, o bé sobre una peça més gran. Quin és el nombre mínim de moviments?

Granotes i gripaus

Aquest és un altre solitari clàssic en el qual s'han d'intercanviar les posicions de les peces blanques i negres seguint les regles següents: les blanques només poden avançar cap a la dreta i les negres cap a l'esquerra, un moviment consisteix o bé en avançar a un forat buit contingu o bé saltar una peça contrària que té un forat buit darrera. Quin és el mínim nombre de moviments?

Solucions als dos solitaris

Bon dia!

Sembla que això dels solitaris no ha engrescat a ningú, no he rebut cap solució ni ningú ha fet cap comentari. Què hi farem!

Torres de Hanoi

Una bona manera de començar consisteix en simplificar i veure què passa si tot just tenim una peça. És evident que en aquest cas amb un únic moviment en tenim prou. Què passa si tenim dues peces? Traiem la petita, la posem al pal central, la gran al seu lloc, i la petita a sobre, tres moviments. Bé. Què passa amb tres peces? Podeu mirar de fer-ho anant provant i hauríeu de veure que 7 és el mínim nombre de moviments. Però si pensem un xic podem veure que per poder treure la peça gran, abans hem hagut de treure les dues peces de sobre, però això ja sabem que són tres moviments, ara traiem la de sota, un altre moviment, i per acabar les dues peces a sobre, tres moviments  més, és a dir, 7 moviments. Caram! Podem utilitzat aquesta estratègia per quan tinguem més peces. Si tenim n peces, per treure la de sota, primer hem de treure les n-1 de sobre, treure la de sota, i tornar a posar les n-1 a sobre. És a dir, si anomenem T(n) al nombre de moviments mínim per treure n peces, tenim que per trobar el nombre de moviments mínim de n+1 peces serà:

T(n+1)=T(n)+1+T(n)=2T(n)+1

Ah! Amb això podem calcular tots els moviments que desitgem, no? Per què per qualsevol n, si hem calculat els anteriors som capaços de trobar el valor de T(n). Fem-ho:

T(1)=1, T(2)=3, T(3)=7, T(4)=2x7+1=15, T(5)=2x15+1=31, T(6)=2x31+1=63,....

Bé, això està molt bé, és el que se'n diu una fórmula recurrent, si coneixem els primers valors podem saber els següents. Clar, però.... sempre he d'haver calculat tots els anteriors i això a mesura que anem tenint nombres més grans pot ser un rotllo. No seria possible trobar una fórmula tancada, és a dir, que només depengués de n.

Per fer això ens hem de fixar en els nombres que hem obtingut:

1, 3, 7, 15, 31, 63, ...

No ens diuen res? Si no ens diuen res haurem de continuar, però si tenim un xic de coneixement de nombres, podem veure que tots són un menys que les potències de 2, és a dir, 2, 4, 8, 16, 32, 64, ...

Ah! si fos així tindríem una fórmula tancada T(n)=2ⁿ-1.

Com ho podríem justificar? Si per n=1 tenim T(1)=1 aleshores

T(2)= 2x1-1=3=2²-1 i, en general, T(n)=2xT(n-1)+1=2x(2^(n-1)-1)+1=2ⁿ-2+1=2ⁿ-1. Aquí estem utilitzant inducció, però ara no vull entrar en el tema per no fer-me pesat. Suposo que tanmateix es veu que la fórmula tancada és certa.

Granotes i gripaus

Un altre cop hem de simplificar. Si només tenim una granota i un gripau és fàcil veure que amb tres moviments ja hem acabat. Compte que en aquest joc com que no es pot anar enrere, si es fa això és evident que farem més moviments. Per tant, sempre s'ha d'anar avançant en el sentit adequat, sinó el joc queda bloquejat. Anem per feina, si tenim n granotes i n gripaus i han de d'intercanviar les posicions cada un d'ells ha d'avançar n+1 forats. Per tant, el total de moviments, si no hi hagués salts seria 2nx(n+1). Però resulta que hi ha salts. Podem considerar que les granotes salten sobre els gripaus (no és exactament cert, però en definitiva el resultat és aquest), és a dir, el nombre de salts és nxn. Els salts els hem de restar al nombre total d'avançaments per tant tenim que el nombre mínim de moviments és:

2nx(n+2)-nxn=2n²+2n-n²=n²+2n=(n+1)²-1.

Soc conscient que ho he fet un xic ràpid però....