Si traiem totes les peces del diablotín i les tornem a col·locar a l'atzar, ¿és sempre possible reordenar-lo correctament? Podem preveure que no, ja que només és permès fer lliscar les peces i, per tant, es redueix el nombre de moviments que es poden fer. Aleshores ens podem plantejar trobar en quins casos és possible resoldre el diablotín i en quins no.

Quan hem estudiat el cas del diablotín format per 3 peces de mida 2x2, hem trobat que hi ha només 3 casos possibles, però el nombre total de permutacions de 3 elements és 6. Així tenim les següents permutacions:

Observem doncs que en els casos possibles el nombre d'intercanvis de peces és parell i en els impossibles és senar.

A més, el 14-15 puzzle proposat per en Sam Loyd conté un únic intercanvi de peces i sabem que no es pot resoldre. Per tant, podem intentar generalitzar aquest fet.

Considerem f una permutació qualsevol de les peces. Per exemple, agafem:

Aleshores sabem que f s'expressa com a producte de funcions generadores, que són permutacions d’ordre 3. Per tant, f ens queda expressada com: f = (9,13,10) (5,9,6) (1,5,2).

Ara bé, sabem que qualsevol permutació d'ordre k és producte de k-1 transposicions (permutacions de dos elements). Aleshores cada permutació d'ordre 3 és producte de 2 transposicions i, per tant, la permutació f serà producte d'un nombre parell de transposicions. En el nostre cas, f és: (9,10) (9,13) (5,6) (5,9) (1,2) (1,5) , sis transposicions, un nombre parell.

Així obtenim que qualsevol permutació de les peces és formada per un nombre parell d'intercanvis. Però, ¿pot passar que el producte d'un nombre parell de transposicions es pugui escriure com a producte d'un nombre senar? És a dir, podem expressar el moviment que representen les nostres sis transposicions amb cinc, o tres, o set, etc.? No és possible, ja que aleshores tindríem la identitat expressada per un nombre parell de transposicions, però això no pot ser perquè sabem que la identitat només es pot escriure com un nombre parell de transposicions. Així arribem a la següent conclusió:

Donada una certa reordenació de les peces, només és possible arribar a la solució correcta si el nombre d'intercanvis de peces és parell.

Aquest resultat és independent de les mides del diablotín, la qual cosa explica la qüestió pendent en el cas 3x2.

[Home][Història][Estudi][Links]

[ Aquest treball m'agrada ]