Blog d’en Cesc

El nombre de Déu és el nombre mínim de moviments necessaris per
resoldre qualsevol instància del cub de Rubik, és a dir, per passar de
qualsevol configuració desordenada del cub de Rubik a la configuració
diguem-ne bàsica, on totes les cares tenen un color (per moviment
entenem un quart de volta o mitja volta d’una cara del cub). Li diuen el
nombre de Déu, perquè se suposa que Déu empraria el menor nombre
possible de moviments per resoldre el cub de Rubik.

Es coneixen configuracions que necessiten 20 moviments per resoldre-les
(és a dir, que no hi ha manera de resoldre-les amb 19 o menys), i la
conjectura és que el nombre de Déu és ‘vint-i-un parell’.

Aquest estiu, Gene Cooperman i un estudiant de doctorat, Dan Kunkle, en un treball presentat a l’ISSAC’07, han baixat la fita superior per a aquest
nombre de Déu a 26. Podeu trobar l’article original a la pàgina web que en
Kunkle ha muntat sobre el tema, i on trobareu a més un recull d’enllaços a les notícies que s’han publicat sobre aquest treball.

La demostració ha consistit essencialment a comprovar que en el graf de amb nodes totes les possibles configuració (i n’hi ha més de ) i arestes representant els moviments que passen d’una configuració a l’altre, tot node pot connectar-se a la configuració bàsica per un camí de 26 o menys arestes. Sí, és una demostració ‘amb ordinador’, tipus la teorema dels quatre colors o de la conjectura de Kepler, però com en aquests casos, no consisteix en una cerca exhaustiva de tots els camins possibles, que seria impossible atesa la magnitud de la tragèdia, sinó que la dueixen mitjançant una sèrie d’astúcies molt interessants, i molt matemàtiques: els cal primer demostrar teoremes de teoria de grups, de teoria de grafs, d’algorítmica en paral·lel, i fins i tot sobre gestió eficient de memòria. Així i tot, ha costat més de 800 hores de CPU.

Va’t aquí un problema ben curiós: trobar el nombre de Déu. Si més no, té un nom ideal per demanar subvencions.
És un problema rellevant? No ho crec, o, dit d’una altra manera més política, tant com la conjectura de Kepler.
Ara, és important aquest treball concret? Crec que sí. És clar que davallar la
fita superior del nombre de Déu és anecdòtic fins i tot per als
aficionats al cub de Rubik (de fet, encara ningú no ha trobat cap
configuració que no es pugui resoldre amb 20 moviments, prou enfora de
26). Però la gestió de grafs grans amb milions o fins i tot bilions
de nodes és un problema cada dia més rellevant: per esmentar-ne un
exemple que m’és proper (i que és el que m’ha fet llegir aquest
article, a mem si podia aprofitar qualque idea), les xarxes de
reaccions i interaccions bioquímiques que es produeixen als éssers
vius. Moltes qüestions sobre aquests grafs s’han de resoldre amb una
combinació de teoremes matemàtics (que dirigeixen, fiten fan més
eficient, … l’anàlisi del graf) i de càlculs massius
amb ordinadors el més memoriuts i potents possible.

En tot cas, per als matemàtics més purs, sempre queda el problema
bàsic: podríem trobar el nombre de Déu amb una demostració que no
involucràs càlculs massius? Qui ho sap. Però per ventura, si us voleu fer famosos, primer us convindria provar amb una demostració ‘lliure d’ordinador’ del teorema dels quatre colors.

Em fa vergonya haver estat, tot animat, dels primers en demanar un bloc, i
encara no haver dit ni piu. La veritat és que entre feina, mudança i
altres problemes, aquests darrers mesos no he tingut gaire temps per res
més que anar trampejant les meves obligacions diverses. Però en fi, ara ja
estic una mica més lliure (no molt, que el començament de curs es presenta
ferest), i em puc dedicar una mica a les coses que no són obligatòries.

Volia dedicar aquest bloc principalment a explicar coses que anàs
llegint i trobàs que podien interessar als xeixeros (xeixers?
xeixencs? xeixistes? (ai, no!)). Precisament aquests dies he estat
mirant un article molt curiós den Mark Segal (director del Centre de
Bioinformàtica i Bioestadística Molecular de la Universitat de
Califòrnia a San Francisco) titulat “Chess, Chance and Conspiracy”,
aparegut fa poc a Statistical Science.

Resulta que alguns escaquistes de renom, com ara Fischer, Spassky o na
Zsófia Polgár, han denunciat diversos cops que el match entre Karpov i
Kasparov pel campionat del món d’escacs de 1985 estava amanyat. La
veritat és que no ho sabia, ja fa temps que no em dedico a
això dels escacs. Vistes les raons que diu Segal que
addueixen aquests grans escaquistes, fa efectivament una mica d’olor
de teoria de la conspiració. El que fa Segal és no aturar-se en
aquesta impressió, i fer una anàlisi estadística (de fet, diverses
anàlisis) de l’evidència més important que suporta aquesta acusació per mostrar
que no hi ha cap necessitat d’invocar una conspiració per explicar-la.

Mentre esperam que qualque matemàtic analitzi l’assassinat de Kennedy,
aquest treball un bon exemple, fins i tot senzillot, de com aplicar les
matemàtiques per mostrar que un fet (en aquest cas, una seqüència de
moviments) que alguns experts diuen que és increïble que succeeixi de
manera natural sense una conspiració, en realitat és creïble i fins i tot
més probable que altres coses que donam per perfectament assumibles.

Ah, podeu trobar l’article den Segal a l’ArXiv
aquí