7: Un text xifrat

Problema 7 

La criptografia és la tècnica —o art— de transformar un missatge en un seguit de signes que si són interceptats sigui difícil, o fins i tot impossible, esbrinar el missatge original.

Durant molts segles es van emprar mètodes que amb les tècniques modernes serien molt fàcils de desxifrar. Fins i tot durant la II Guerra Mundial, el mètode de xifratge del Reich alemany que emprava unes màquines anomenades “Enigma” i que només va ser trencat emprant una gran quantitat de mitjans humans i tècnics, seria molt fàcil de trencar amb els ordinadors actuals.

El mètode més antic que es coneix rep el nom de Juli Cèsar, que segurament el va emprar. Consisteix en substituir cada lletra del alfabet  per la lletra que hi ha n posicions més endavant, continuant comptant a partir de la A, si arribem al final del alfabet. Per exemple, si fem servir n = 4, la A es convertirà en E, i la X en B. És un mètode molt fàcil de desxifrar, i si Juli Cèsar el va emprar amb èxit, segurament va ser perquè el seus enemics gairebé no sabien llegir.

Un mètode quasi tan elemental com aquest, és el de substituir cada lletra per un dibuixet diferent. Aquí cal esbrinar a quina lletra correspon cada signe. Recordo haver vist fer servir aquest sistema entre els nois de l’escola…

Si, a més es mantenen els espais entre les paraules o els signes de puntuació, encara és més fàcil ja que paraules d’una o dues lletres n’hi ha poques.

Però aquí, per complicar-ho una mica, farem com Juli Cèsar, que com tots els romans escrivia sense espais; en el text els he suprimit, com també accents i altres signes de puntuació. Els signes estan disposats en grups de cinc, senzillament per llegibilitat.

Text xifrat, sense espais però en grups de 5 caràcters per facilitar la lectura

Podeu desxifrar aquest text? I encara que no tingui res a veure amb la criptografia, esbrinar —és fàcil— qui és el seu autor?

Pistes

En primer lloc, per desxifrar un text d'aquestes característiques, cal fer un estudi estadístic de les freqüències de les lletres.

En català, les 10 lletres més freqüents en un text són per ordre: E, A, S, L, I, R, T, N, O, U. Podem suposar que en el text que volem esbrinar les freqüències seran similars.

En segon lloc les repeticions de lletres. Com que hem suprimit els espais entre paraules, si trobem el mateix símbol dues vegades seguides, pot ser una lletra que es repeteixi dins una paraula, o una que aparegui al final d'un mot i al principi del següent. Si un símbol sure més de dues vegades seguides, és el cas de: ❯❯❯❯, segur que és dos cops al final d'una paraula i una al començament de la següent. En català, això, pràcticament, només li pot passar a una lletra.

Ocurrències dels símbols i de les seves repeticions

 Substituint les símbols més fàcils de conjecturar per la seva lletra, podem començar a esbrinar paraules, que ens donen el valor dels símbols menys freqüents, i amb facilitat ens permetran desxifrar tot el text.

Solució

… properament …

6: El mapa dels quatre colors al cel

Problema 6

A mitjans del segle XIX un jove universitari britànic es va entretenir un dia acolorint el mapa dels comtats anglesos, de manera que dos que compartissin frontera mai no fossin del mateix color. Va aconseguir amb certa facilitat fer-ho amb només quatre colors, i també va veure que amb tres era impossible.

Aleshores es va preguntar si qualsevol mapa es podria acolorir d’aquesta manera amb només quatre colors. En tots els mapes que ho va provar, ho va aconseguir, però no va trobar cap sistema per demostrar-ho.

Un mapa acolorit amb quatre colors.

El problema va arribar a les orelles dels matemàtics professionals —el primer que se’n va ocupar va ser Augustus de Morgan— que tampoc no van aconseguir la demostració.

Alguns avenços sí que es van fer: es va demostrar que no era possible que cinc regions compartissin frontera cadascuna amb les altres quatre, que amb cinc colors sempre era possible acolorir qualsevol mapa, que un mapa sobre una esfera era equivalent en aquest aspecte a qualsevol mapa pla, i fins i tot, que sobre d’altres superfícies el nombre de colors necessaris podia ser superior. Per exemple, sobre un tor —la figura en forma de pneumàtic— son possibles set regions que dos a dos comparteixin frontera i va ser possible demostrar que amb 7 colors és sempre possible acolorir qualsevol mapa pintat sobre aquesta superfície. Però l’esfera i el pla es resistien.

124 anys després es va demostrar, però no va ser una demostració “normal”, amb llapis i paper, sinó que va precisar un ordinador que comprovés totes i cadascuna d’uns milers de configuracions de regions, anomenades irreductibles, en les quals es pot transformar mantenint el problema, qualsevol configuració.

No ho hem esmentat, però quan aquí parlem d’un mapa dividit amb regions, volem dir un mapa simple: on cada zona estigui envoltada per una línia fronterera simple, no s’hi valen els “països” dividits en dues o més zones. També cal la condició que si més de tres regions conflueixen al mateix punt, es consideri que les que només entren en contacte en aquest punt, no són veïnes, o sigui que el veïnatge necessita compartir una línia, no tan sols un punt.

Dos mapes que precisen 5 colors

Sense aquestes condicions, poden caldre més de quatre colors per pintar un mapa.

Per exemple, al mapa de la dreta, imaginem que les dues zones blaves marcades A, són el mateix país; B, C i D hauran de ser de colors diferents ja que toquen A i també entre elles; però aleshores, E necessita un cinquè color, ja que té frontera comú amb A, B, C i D que ja són de quatre colors diferents.

En el mapa de la dreta, si consideréssim veïnes W i Y, i també X i Z, ja ens caldrien quatre colors per a aquestes zones; aleshores V, que les toca a totes, precisaria un cinquè color.

Aquests aclariments són necessaris pel problema que plantegem.

Fins a principis del segle XX, les constel·lacions van ser conjunts d’estrelles que d’una manera més o menys vaga recordaven un objecte, personatge o sovint animal. La seva representació sovint incloïa superposat el dibuix corresponent, encara que més modernament es va substituir per unes poques línies representatives unint les estrelles més brillants.

Però a partir de 1930 es va anomenar constel·lació a una regió del cel, limitada per línies rectes que seguien els meridians i paral·les celestes i que incloïa l’antiga configuració d’estrelles.

Es van definir 88 constel·lacions que abasten tota la volta celeste. O sigui que qualsevol punt del cels està inclòs de manera unívoca en alguna de les 88 constel·lacions grans o petites i que es pot dibuixar un mapa del cel amb les fronteres de la mateixa manera que podem dibuixar un mapa del món amb els estats —prescindim ara dels mars—.

Les 88 constel·lacions del cel en projecció mercator (si surts per la dreta del mapa entres per l’esquerra)

Podem assegurar que aquest mapa es podrà acolorir amb quatre colors?

En principi no, perquè hi ha una anomalia, una de les constel·lacions —Serpens, marcada amb la vora groga— per motius històrics està dividida en dues zones. A més, posem la condició suplementària que als quatre punts —marcats en vermell— on conflueixen quatre constel·lacions, han de ser les quatre de colors diferents.

Podeu, amb aquestes condicions, acolorir el mapa del cel amb quatre colors?

Solució 6

És perfectament factible dibuixar el mapa tot i les condicions suplementàries.
He marcat amb × les constel·lacions  que estan envoltades per altres tres que es toquen mútuament i que en conseqüència han de ser de tres colors diferents; les marcades, senzillament, s’han de pintar del quart color i no afecten la resta del mapa.
Probalement el més fàcil és començar per Serpens —la que està pintada en groc i té dos regions— i a partir d’aquella zona anar-se expandint per tot el mapa.

Una de les moltes solucions al problema

En molts pocs casos ens trobem que hi ha una zona que no podem acolorir perquè fa frontera amb quatre que ja tenen els quatre colors, aleshores cal retrocedir en el procés fins trobar un punt on hem pres la decisió d’acolorir la constel·lació que ens causa el problema posterior i escollir per a ella un color diferent. És un mètode que es pot aplicar fàcilment a mà, només cal portar un registre de l’ordre en el que anem acolorint les zones per poder fer marxa enrere si és necessari.