Trencaclosques del 15 i paritat
Cada moviment és un intercanvi amb el buit, i cada intercanvi canvia la paritat de la permutació. Juga-hi i mira com el comptador d'inversions mai s'equivoca, moviment rere moviment.
Qualsevol disposició de les 15 fitxes en una graella 4×4 és, matemàticament, una permutació: una manera concreta d'ordenar-les. Per llegir-la, recorre la graella com un text (fila per fila, d'esquerra a dreta) i escriu els 15 números, ignorant el buit.
Una inversió és un parell de fitxes que apareix en l'ordre equivocat en aquesta lectura — per exemple, si el 5 surt abans que el 3, encara que sigui perquè hi ha altres fitxes pel mig. Comptar-les totes et diu si la permutació és parella (nombre d'inversions parell) o senar.
Cada moviment legal és un intercanvi entre el buit i una fitxa veïna — horitzontal o vertical. Un moviment horitzontal no canvia ni les inversions ni la fila del buit; un moviment vertical canvia totes dues alhora. Per això la combinació «inversions + fila del buit» es manté sempre amb la mateixa paritat, moviment rere moviment: és la clau de tot el que ve després.
Per què, exactament? Un moviment horitzontal només mou el buit dins la mateixa fila: com que la seqüència de lectura sempre l'ignora, la resta de fitxes es llegeixen exactament en el mateix ordre relatiu d'abans —el nombre d'inversions no canvia ni una unitat, no només de paritat. Un moviment vertical és diferent: la fitxa que es mou salta per damunt d'exactament 3 altres fitxes en la seqüència de lectura (les que li quedaven per llegir a la fila antiga, més les que ja s'hi havien llegit a la fila nova — entre totes dues sempre en sumen 3, perquè una fila té 4 columnes). Saltar per damunt de 3 fitxes equival a 3 bescanvis consecutius entre veïns de seqüència, i cada bescanvi d'aquests capgira la paritat de les inversions — tres capgiraments seguits tornen a capgirar-la en total. Com que la fila del buit també canvia de paritat a cada moviment vertical (i mai als horitzontals), els dos capgiraments van sempre junts: per això la seva suma no en fa mai cap, de sol.
El 1880, Sam Loyd va oferir 1000$ (una fortuna en aquella època) a qui resolgués el trencaclosques amb el 14 i el 15 intercanviats. Ningú els va cobrar mai: aquesta configuració concreta no té solució, i el 1879 Johnson i Story ja ho havien demostrat combinant la paritat de les inversions amb la fila del buit.
Més enllà de l'anècdota, aquest és un dels exemples més accessibles d'una demostració per invariant: en lloc de provar totes les seqüències de moviments possibles (impossible, n'hi ha bilions), es troba una propietat que mai canvia i que distingeix les configuracions possibles de les impossibles d'un sol cop d'ull. És exactament el mateix tipus de raonament que apareix a la teoria de grups amb el grup altern Aₙ (el subgrup de permutacions parelles).
Aquesta invariant no és una coincidència del trencaclosques: és una manifestació concreta del signe d'una permutació, la funció que assigna +1 a les permutacions parelles i −1 a les senars. El signe és un homomorfisme de grups de Sₙ cap a {+1,−1} —cada transposició (bescanvi de dos elements) el capgira sempre, sense excepció—, i cada moviment del trencaclosques és, en efecte, una transposició entre el buit i una fitxa. Per això el signe hi canvia a cada pas, mai per accident: és estructura de grup pura, la mateixa que hi ha darrere de qualsevol taula de Cayley.
- Joc lliure: mou fitxes adjacents al buit i observa com el comptador d'inversions, la fila del buit i la invariant final canvien (o no) a cada moviment.
- Compta les inversions: practica el mètode a mà sobre una graella estàtica, sense jugar-hi — escriu quantes inversions hi compta i comprova-ho.
Aquesta càpsula amaga una de les idees més potents de tota la matemàtica sota l'aparença d'un joguet de fira: com demostrar que una cosa és impossible. No difícil, no que ningú l'hagi aconseguida encara — impossible, per sempre, i sabent-ho amb certesa absoluta sense haver de provar-ho tot. Anem a veure com es fa, per què funciona, i per què el mateix argument reapareix des del cub de Rubik fins a la física de partícules.
1. Els 1000 dòlars que ningú va cobrar
Cap al 1880 el trencaclosques de les 15 peces va provocar una febre mundial comparable a la del cub de Rubik un segle després. Enmig d'aquella onada, el creador de trencaclosques nord-americà Sam Loyd va oferir 1.000 dòlars —una fortuna considerable— a qui aconseguís resoldre'l partint de la posició ordenada però amb el 14 i el 15 intercanviats.
Milers de persones ho van intentar. Ningú va cobrar mai. I no perquè fos molt difícil: és impossible, i ja s'havia demostrat el 1879 —un any abans de l'oferta— en un article de William Johnson i William Story. Loyd sabia perfectament que oferia diners sense cap risc.
2. Del tauler a una llista de números
El primer pas per poder demostrar res és deixar de veure un tauler i començar a veure un objecte matemàtic. Fem-ho: llegeix la graella com si fos un text, fila per fila i d'esquerra a dreta, i apunta els 15 números que trobis, ignorant el buit. Obtens una llista com 5, 2, 4, 15, 13, 7, …
Aquesta llista és una permutació dels números de l'1 al 15: una manera concreta d'ordenar-los. La posició ordenada correspon a la llista 1, 2, 3, …, 15. Qualsevol altra disposició és una barreja d'aquesta.
El pas conceptual important és aquest: el trencaclosques ja no és un tauler amb fitxes, és un punt dins del conjunt de totes les permutacions possibles. I d'aquest conjunt en sabem coses.
3. Inversions: mesurar el desordre
Necessitem una manera de quantificar «com de barrejada» està una llista. La més útil és comptar-ne les inversions: parelles de números que apareixen en l'ordre equivocat.
Concretament, per cada parella de fitxes, mira quina surt abans a la lectura i quina té el número més petit. Si la més gran surt abans que la més petita, aquella parella compta com una inversió. No cal que siguin veïnes: només compta l'ordre relatiu.
El que interessa no és tant el nombre exacte com la seva paritat: si és parell o senar. Aquesta és l'activitat «Compta les inversions» de la càpsula, i val la pena fer-ne unes quantes a mà abans de continuar, perquè tot el que ve depèn d'entendre bé aquest recompte.
4. Què li fa un moviment a la paritat
Aquí és on hi ha la part que gairebé cap explicació breu desenvolupa, i que és el cor de tot. Un moviment legal consisteix a lliscar una fitxa veïna cap al buit. N'hi ha de dos tipus, i es comporten de maneres oposades.
Moviment horitzontal
La fitxa i el buit intercanvien posicions dins de la mateixa fila. Com que la lectura ignora el buit, la seqüència de números que llegim no canvia gens: les mateixes fitxes, en el mateix ordre. Per tant el nombre d'inversions no canvia ni en una unitat. I la fila del buit tampoc no canvia.
Moviment vertical
Aquí la fitxa salta a la fila de sobre o de sota. En la seqüència de lectura, aquesta fitxa se salta exactament tres fitxes. Per què tres? Perquè entre la posició antiga i la nova hi ha una fila sencera de 4 caselles, una de les quals l'ocupa el buit (que no es llegeix): queden 3 fitxes pel mig.
I saltar per damunt de 3 fitxes equival a fer 3 bescanvis consecutius amb el veí immediat. Cada bescanvi de veïns canvia la paritat de les inversions (afegeix o treu exactament una inversió: la de la parella que s'ha bescanviat). Tres canvis de paritat seguits deixen la paritat capgirada.
(nombre d'inversions) + (fila del buit) té sempre la mateixa paritat, passi el que passi. És un invariant.
5. De l'invariant a la impossibilitat
Ara l'argument es tanca sol, i val la pena veure com de poc esforç costa un cop tens l'invariant.
A la posició resolta hi ha 0 inversions i el buit és a la fila 4. La suma és 0 + 4 = 4, parella. (Amb la convenció de files 0-indexada que fa servir la càpsula, la suma és senar; el que importa no és el valor absolut sinó que la paritat mai canviï.)
Ara mira la posició de Loyd: exactament la mateixa, però amb el 14 i el 15 intercanviats. El buit segueix a la mateixa fila, però bescanviar dues fitxes veïnes afegeix exactament una inversió. La suma ha canviat de paritat.
I com que cap moviment legal no pot canviar aquesta paritat, no existeix cap seqüència de moviments —ni de deu, ni d'un milió— que porti d'una posició a l'altra. No és que sigui difícil: és que les dues posicions viuen en compartiments estancs de l'univers del trencaclosques.
6. Què fem a l'element interactiu
La càpsula té dues activitats complementàries.
Joc lliure. Mous fitxes i, a sota, tres números s'actualitzen a cada moviment: el nombre d'inversions, la fila del buit, i el veredicte de l'invariant. El propòsit no és resoldre el trencaclosques —això ja ho saps fer— sinó vigilar els números mentre jugues. Fes moviments horitzontals: veuràs les inversions quietes. Fes-ne un de vertical: veuràs el nombre saltar. I, mentrestant, el veredicte final no es mou mai. Estàs comprovant un teorema amb el dit.
Compta les inversions. Et dona una graella estàtica i et demana el número. És la part avorrida però imprescindible: si no has comptat inversions a mà unes quantes vegades, l'invariant continua sent una afirmació abstracta.
7. La idea de fons: demostracions per invariant
El que has fet aquí no és un truc del trencaclosques del 15. És una estratègia general de demostració que apareix a tot arreu, i val la pena enunciar-la en abstracte:
Per demostrar que no es pot arribar de A a B mitjançant unes certes operacions, busca una quantitat que cap operació no canviï, i comprova que val coses diferents a A i a B.
La força d'aquest mètode és que substitueix una cerca infinita per un càlcul finit. La pregunta original —«hi ha alguna seqüència de moviments, de qualsevol longitud, que ho aconsegueixi?»— és impossible d'atacar per força bruta: hi ha infinites seqüències. La pregunta reformulada —«coincideixen les paritats?»— es respon en deu segons amb un llapis.
És la mateixa lògica que la conservació de l'energia en física: no cal seguir un sistema instant per instant per saber que certs estats finals són inabastables.
8. El signe d'una permutació
Anem un pas més enllà, perquè l'invariant no és un accident del tauler 4×4: és una manifestació d'una estructura algebraica.
A tota permutació se li pot assignar un signe: +1 si té un nombre parell d'inversions, −1 si en té un nombre senar. Aquesta assignació té una propietat notable: el signe d'una composició és el producte dels signes. En el llenguatge de la càpsula de Taules de Cayley, el signe és un homomorfisme del grup simètric Sₙ cap al grup {+1, −1}.
La conseqüència: cada transposició (bescanviar dos elements) té signe −1, sense excepció. I cada moviment del trencaclosques és exactament una transposició —entre el buit i una fitxa. Per això el signe canvia a cada moviment: no per una casualitat combinatòria, sinó perquè així és com funciona l'estructura.
Les permutacions de signe +1 formen un subgrup, el grup altern Aₙ, que conté exactament la meitat dels elements. Les posicions accessibles del trencaclosques (amb el buit tornat al seu racó) són precisament les que corresponen a A₁₅, i n'hi ha 15!/2 = 653.837.184.000. Les «dues classes» del teorema de Johnson–Story són, en realitat, el grup altern i el seu complement.
9. Aparicions fora de les matemàtiques
El cub de Rubik. Té tres invariants d'aquesta família alhora: la paritat de la permutació de les peces, l'orientació total dels vèrtexs (mòdul 3) i la de les arestes (mòdul 2). Per això no pots girar una sola aresta i deixar la resta igual, ni intercanviar només dues peces. Si desmuntes el cub i el tornes a muntar a l'atzar, tens una probabilitat d'1 entre 12 que sigui resoluble.
Física de partícules. Les partícules es divideixen en fermions i bosons segons com es comporta la seva funció d'ona quan s'intercanvien dues partícules idèntiques: canvia de signe o no. És, literalment, el signe d'una permutació. El principi d'exclusió de Pauli —i, per tant, tota l'estructura de la taula periòdica— surt d'aquí.
Determinants. La fórmula del determinant d'una matriu és una suma sobre totes les permutacions, cada terme multiplicat pel signe de la permutació. Que un determinant canviï de signe en intercanviar dues files és exactament el mateix fet que fa impossible el trencaclosques de Loyd.
Verificació de programes i criptografia. La tècnica d'invariants s'usa contínuament en informàtica: un invariant de bucle és una propietat que es manté a cada iteració i que permet demostrar que un programa és correcte sense executar-lo per a totes les entrades possibles.
10. Curiositats
El número de Déu del trencaclosques és 80. Es va demostrar que qualsevol posició resoluble es pot resoldre en un màxim de 80 moviments de fitxa, i que n'hi ha que en necessiten exactament 80. Va caldre potència de càlcul considerable per confirmar-ho. Per comparació, el cub de Rubik en necessita 20.
Però el cas general és intractable. Trobar la solució més curta del trencaclosques n×n generalitzat és NP-difícil (Ratner i Warmuth, 1990). És a dir: saber si una posició és resoluble es fa en un instant amb l'invariant, però saber quin és el camí òptim és un dels problemes durs de la informàtica teòrica. La distància entre «sé que existeix» i «sé quin és» pot ser abismal.
Loyd va provocar pèrdues econòmiques reals. Cròniques de l'època parlen de botiguers que tancaven per jugar-hi, funcionaris que hi perdien la jornada i patrons que van prohibir el trencaclosques a l'oficina. A França se'l va arribar a descriure com una plaga pitjor que l'alcohol o el tabac.
La mateixa paritat, un tauler diferent. Si el tauler fos de 3×3 (el trencaclosques del 8), l'argument funcionaria igual però amb un detall: en un tauler d'amplada senar, els moviments verticals salten per damunt d'un nombre parell de fitxes, i llavors n'hi ha prou amb la paritat de les inversions, sense haver de mirar la fila del buit. La regla depèn de l'amplada del tauler, i aquest és un bon exercici per comprovar que has entès el mecanisme i no memoritzat la fórmula.
La solució de Loyd, si s'hi val a fer trampa. Si gires el tauler sencer 90°, la lectura canvia i la paritat també. Alguns contemporanis ho van proposar com a «solució». Loyd, previsor, havia especificat que les fitxes havien d'acabar en l'orientació correcta.
11. Connexió amb altres àrees
Aquesta càpsula és, essencialment, una il·lustració física del grup altern, que és un dels objectes centrals de la càpsula de Taules de Cayley: allà construeixes taules de grups petits i en busques subgrups; aquí n'estàs manipulant un de 15! elements amb els dits.
La connexió amb la Teoria de Galois és encara més directa i històricament decisiva. El fet que Aₙ sigui «simple» (no es pot desmuntar) per a n ≥ 5 és exactament la raó per la qual les equacions de grau 5 no es poden resoldre per radicals. El mateix grup que fa impossible el trencaclosques de Loyd fa impossible la fórmula de la quíntica.
I amb Nusos i tricolorabilitat comparteix el mètode sencer: trobar una propietat que les transformacions permeses no poden alterar, i utilitzar-la per separar el possible de l'impossible. Canvien els objectes; l'estratègia és idèntica.
Cada moviment és un intercanvi amb el buit: sempre canvia la paritat de la permutació. La invariant real combina la paritat de les inversions amb la posició (fila) del buit.