11: Circuit de diferents distàncies

Problema 11 

Sobre una quadrícula, en el nostre cas de rajoles, hem col·locat vint-i-vuit monedes.

Suposem que la quadrícula és exacta, amb una distància unitat entre dos encreuaments contigus i que les monedes estan exactament ben posades a les interseccions.

28 monedes sobre la quadrícula

Les distàncies en línia  recta entre dues monedes varien entre 1 i aproximadament 18,6 que és la distància entre les monedes extremes de la figura. Algunes monedes estan separades d’altres, distàncies que són exactament números enters.

Es tracta de trobar dotze monedes que formin un circuit tancat, de manera que les seves distàncies —en qualsevol ordre— siguin tots els valors enters compresos entre l’1 i el 12. Circuit tancat vol dir que de la dotzena moneda passem a la primera.

El circuit pot passar per damunt de l’emplaçament d’una moneda que no hi formi part.

La condició suplementària és que aquest circuit no tingui cap creuament, dit d’una altra manera, que no tingui una forma equiparable a un 8.

Solució 11

Aquest problema necessita per a la seva solució constatar el fet que les distàncies que són “exactament números enters” no vol dir que sigui entre dos punts situats a la mateixa vertical o horitzontal de la quadrícula.

Punts no ortogonals separats exactament 5 i 10 unitats

Hi ha dos casos amb números de l’1 al 12 en que això pot passar, són les solucions enteres del teorema de Pitàgores que ens proporcionen triangles rectangles de costats 3, 4 i 5 o 6, 8 i 10, essent els números vermells les hipotenuses esbiaixades respecte la quadrícula.
Vist això i trobats quins són els punts del problema allunyats 5 i 10 unitats sense seguir la quadrícula, podem trobar la solució:

Circuit amb 12 segments diferents

La manera més ràpida pot ser examinant totes les monedes que estiguin separades 10, 11 i 12 unitats, i aleshores provar totes les combinacions que no siguin impossibles —per exemple que no es creuïn—, i a partir d’aquest punt anar completant amb els segments menors.

8: Un núvol de punts

Problema 8

Marquem tres punts —X, Y i Z— que formin els vèrtexs d’un triangle equilàter.

Escollim ara un punt al atzar de l’interior d’aquest triangle, per exemple el que marquem amb el número 1 a la figura.

Els primers dotze punts de la figura

Aleshores escollim al atzar un dels tres punts inicials. En el nostre exemple Y. Marquem ara amb el número 2 el punt mig entre 1 i Y.

Continuem escollint al atzar qualsevol dels tres punts X, Y o Z, i anem marcant cada vegada el punt situat a mig camí entre el darrer punt i el vèrtex escollit.

En l’exemple de la figura la seqüència de vèrtexs és Y, Y X, Y, Z, Z, X, X, Y, Z, X… hi podem veure numerats els dotze primers punts. Insisteixo, és només un cas particular, la seqüència pot ser qualsevol al atzar i els punts aleshores serien uns altres.

Imaginem que continuem el procés fins col·locar uns quants milers de punts a la figura.

Nou possibles respostes al problema

A quina de les nou imatges s’assemblarà més el núvol de punts resultant d’aquest procés?

 Solució 8

La resposta és la figura D.

Si repetidament partim d’un punt a l’atzar dins del triangle, la seva distribució seria la de la figura A del diagrama que segueix:

Els 9 primers passos de la construcció del triangle de Sierpiński

Si apliquem la transformació —el punt a mig camí d’un dels tres vèrtexs escollit a l’atzar— passem a la distribució de la figura B: un punt que partís de la posició del triangle clar central aniria a parar necessàriament a un dels tres triangles foscos que toquen cadascun dels vèrtexs; un punt ja dins d’un d’aquests triangles aniria a parar al mateix triangle o a qualsevol dels altres dos foscos depenent de a quin vèrtex s’apropés.

En la segona iteració la figura B es transforma en C, cal veure com les zones blanques resten fora de l’abast dels punts.

A continuació la figura serà D, E, F, G, H, I… i a partir d’aquí ja no la podrem distingir a ull de l’anterior.

Dit d’una altra manera, a cada pas, la figura de la distribució dels punts es triplica, es disminueix a la meitat de la mida i es ressitua tocant a cadascun dels vèrtexs del triangle.

En el límit, aquesta figura és el que s’anomena triangle de Sierpiński, en honor al matemàtic polonès que el va descriure l’any 1915.

Si partim d’un únic punt a l’atzar, a cada iteració s’anirà aproximant als punts del triangle de Sierpiński, al cap de molt poques —posem-hi vuit— ja serà a menys d’un píxel en la resolució de la figura.

El fet que el salt del punt sigui cada vegada al atzar, provoca l’efecte que aquesta aproximació és a qualsevol punt del fractal amb la mateixa probabilitat.

O sigui que llevat de les primeres poques iteracions, a efectes visuals el nostre punt anirà recorrent el triangle de Sierpiński, encara que en realitat mai hi arriba, senzillament s’hi apropa en el límit.

La figura resultant serà l’aproximació visual al fractal, potser afegint-hi mitja dotzena de punts inicials que veurem aïllats en zona blanca. 

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.

4: Seixanta-quatre igual a seixanta-cinc?

Problema 4

Observen aquest quadrat format per quatre peces. La quadrícula ens permet veure que la seva àrea és 8 × 8 = 64 unitats quadrades.

Quatre peces formen un quadrat de 8 × 8

A continuació, reordenem les peces —les dues trapezoïdals les hem de girar 90º— per formar un rectangle. Si ara mesurem l'àrea podem veure que és de 5 × 13 = 65 unitats quadrades.

Les mateixes quatre peces formen un rectangle de 5 × 13

D'on ha sortit el quadrat suplementari?

Solució 4

Les quatre peces que formen el quadrat, tenen sumades, efectivament, una àrea de 64. Però no són exactament iguals a les quatre peces que formen la figura rectangular.

 Il·lustració acurada: les quatre peces del quadrat dins el rectangle

En un trencaclosques real, amb les peces fabricades amb una certa tolerància, vores una mica arrodonides i talls entre les peces de gruix no menyspreable, no es nota gaire. En un dibuix acurat és més fàcil d'apreciar.

Podem observar en particular que per fer veure que les peces ocupaven tot el rectangle de 5 × 13, les dues peces triangulars s'havien deformat per convertir-les en quadrilàters amb el quart vèrtex situat als punts blancs del centre del dibuix.

L'àrea de la zona blava, és exactament s'una unitat quadrada, precisament la que ens havia aparegut del no res.

Teorema de Pick

Per calcular aquesta àrea, podem fer ús d'un teorema publicat per primera vegada l'any 1899 pel matemàtic austríac Georg Alexander Pick que afirma:

L'àrea d'un polígon simple —sense forats ni costats que s'intersequin— que tingui tots els vèrtex en els punts d'una quadrícula regular, és igual a I + V/2 – 1, essent I el nombre de punts de la quadrícula interiors al polígon i V els que cauen en el seu perímetre, siguin els vèrtex o punts continguts en un dels costats.

En el cas del nostre problema, la figura blava és un polígon que té els quatre vèrtex a punts de la quadrícula —V = 4—, i cap punt a l'interior —I = 0—, o sigui que la seva superfície serà: 0 + 4/2 – 1 que val, precisament, 1.

Aplicant el mateix teorema podem veure que els triangles de la figura tenen una àrea de 12, i els trapezis de 15, o sigui un total de 12 + 12 + 15 + 15 = 64 unitats quadrades.

Els "triangles" tramposos de la figura rectangular, són de fet quadrilàters, amb 4 vèrtex a la quadrícula, 9 punts de la quadrícula als costats i 7 punts interiors; en conseqüència la seva superfície és de 12,5.