dissabte, 26 de març de 2011

24: Salts de cavall

Problema 24
El cavall d’escacs és una figura amb un moviment fascinant, diferent al de les altres. En lloc d’avançar segons una línia, salta caselles, i sovint per anar a parar a un lloc concret ha de fer curioses giragonses.
El primer que cal constatar del moviment del cavall és que a cada pas canvia el color de la casella. Una conseqüència d’això és que per anar a una casella del mateix color, sempre li cal un nombre parell de salts, i per canviar de color, senar.
És fàcil veure que per anar d’un angle del tauler d’escacs al oposat —que és del mateix color— calen sis jugades.

Sis salts de cavall de punta a punta
La pregunta és: per quants camins diferents ho pot fer? considerant dos camins diferents si tenen alguna casella diferent.
Un sistema de solucionar aquest problema seria dibuixar els diagrames de tots els recorreguts possibles i comptar-los, prenent cura de no descuidar-ne cap ni tampoc de repetir-los, però aquest mètode és molt feinós, cal buscar millors maneres de calcular.
Una petita pista: aquests recorreguts de punta a punta amb sis salts no passen per totes les caselles del tauler…

Tots els salts vàlids per obtenir una solució
A la figura els podem veure tots superposats. Per anar de punta a punta i passar per qualsevol de les caselles no marcades amb un punt, caldrien més de sis salts, o sigui que no cal comptar cap recorregut del cavall que passi per qualsevol d’elles.
Ara, imaginem que el tauler és infinit, que no hi ha la restricció de no poder saltar més enllà de la vora. Continuen calent els sis salts per arribar a la casella de destí, però ho podem fer per més camins. Quants en total?

★★★ COMENTARIS ★★★