1. Demostrar que en tota reunió de 6 persones sempre n’hi haurà 3 que es coneguin mútuament o siguin totalment desconegudes.
2. Provar que, si s’admet que cada persona té menys de 5 cabells per mm², a Catalunya hi almenys 2 persones amb el mateix nombre de cabells al cap.
Demostració:
1. Donada una persona qualsevol d’un conjunt de 6, anomenem-la Albert, pot conèixer o no cada persona del grup de 5 que queda. Clarament, almenys 3 d’aquestes persones tenen la mateixa relació amb Albert (de coneixença o desconeixença). Suposem que Beatriu, Claudia i David coneixen a Albert, i que es poden conèixer entre elles o no. Si no es coneixen en absolut, tenim un subconjunt de 3 persones d’un conjunt de 6 que es desconeixen totalment: Beatriu, Claudia i David. Si, per exemple, Beatriu i Claudia es coneixen, tenim un subconjunt de 3 persones d’un conjunt de 6 que es coneixen mútuament: Albert, Beatriu i Claudia.
2. En primer lloc se suposa que no es dóna una situació trivial: molta gent no té cap pel al cap. A aquestes persones se li pot assignar el nombre de cabells que tindria si no se’ls hagués tallat o caigut. Procedim per reducció a l’absurd, suposem que no hi ha 2 persones a Catalunya amb la mateixa quantitat de cabells al cap. Com que a Catalunya som més de 5 mil·lions de persones, n’hi ha haver alguna amb més de 5 mil·lions de pels al cap. Però com que no es poden tenir més de 5 pels per mm², la superfície del cap d’aquesta persona seria superior a un metre quadrat! No crec que hi hagi cap català amb un cap tan gran.
Aquest tipus de resultats són la versió humana de resultats matemàtics molt potents que pertànyen a la combinatòria, i especialment la teoria de Ramsey. La combinatòria, és una àrea de la matemàtica amb resultats molt generals i fàcils d’ennunciar, alguns de gran antiguitat, i molt sovint d’extrema dificultat. Una part de la combinatòria ha acompanyat raonaments matemàtics, sobretot aritmètics i probabilístics, des de temps immemorials i ha servit de base de moltes innovacions. Però la seva potència més extrema no s’ha començat a percebre fins mitjans del segle XX, a partir d’una sèrie de resultats molt significatius que han generat una allau de problemes que li asseguren un futur envejable. D’això us parlaré tot seguit.
Comencem pel Principi de Dirichlet (segle XIX) o principi de les caselles. La idea és que si s’han d’introduir 5 cartes en 4 bústies, necessàriament una bústia contindrà 2 o més cartes (o també, en qualsevol grup de 3 persones sempre n’hi haurà 2 del mateix sexe). Aquest principi, que he usat en la demostració dels 2 resultats anteriors, admet 2 formulacions: finita i infinita.
(i) Donats n i k enters positius qualsevol, si almenys kn+1 objectes es distribueixen entre n compartiments, aleshores almenys un d’ells contindrà k+1 o més ojectes.
(ii) Si s’han de distribuir infinits objectes en una quantitat finita de compartiments, aleshores almenys un d’ells en contindrà una quantitat infinita.
Pot semblar una trivialitat (i la seva demostració és un exercici elemental), però és una eina molt potent per demostrar relacions d’existència purament quantitatives.
Per entendre bé el cas finit és útil pensar en el pitjor dels casos possibles. Per exemple, en l’exemple (1) anterior suposem un grup de 5 persones (A,B,C,D,E) i la seva relació de coneixença com segueix A-B-C-D-E-A, on X-Y significa que X i Y és coneixen. És ben clar que no hi ha cap subconjunt de 3 persones enterament conegudes o desconegudes: aquest és el pitjor cas possible en aquesta situació. O, en la formulació (i) del principi de Dirichlet, en un conjunt de kn objectes es poden distribuir en n compartiments de forma que cada compartiment tingui k objectes. Aquest també és el pitjor cas possible, ja que afegint un únic objecte se satisfà el principi de forma ineludible.
El principi de Dirichlet és, de fet, el cas més senzill entre tots els resultats en teoria de Ramsey. La teoria de Ramsey va sorgir a partir d’uns teoremes que pretenien donar resposta a una sèrie de qüestions del tipus:
(a) Donats d, t enters positius, existeix W=W(d,t) enter positiu de forma que si s’assigna una t-coloració als W primers enters positius, existeix una progressió monocroma de d termes.
(b) Donats t enter positiu i A matriu mxn de coeficients enters, existeix S=S(A,t) de forma que si s’assigna una t-coloració finita als S primers nombres enters positius, aleshores existeix X vector de m valors enters entre 1,...,S del mateix color tals que AX=0.
(c) Per cada d, t enters positius existeix R=R(d,t) enter positiu tal que per tot graf complet amb R punts i qualsevol t-coloració d’aquest graf, existeix un subgraf complet de d punts monocromàtic.
Els resultats anteriors ens asseguren que aquests problemes i d’altres de similars admeten una solució finita, però determinar el valor exacte de W, S o R per cada d, t o A, trobar-ne cotes raonables o determinar-ne el creixement assimptòtic és extremadament difícil. Tota mena de problemes es deriven d’estudiar casos particulars, en principi més accessibles, i resoldre qüestions paral·leles a aquests problemes. Entre les eines més preuades per atacar aquests problemes es troba la teoria de grafs.
També entre aquests problemes té sentit preguntar-se sobre el pitjor dels casos possibles, ja que la singularitat del nombre R(d,t) es basa en que es poden trobar exemples de grafs complets de R(d,t)-1 punts de forma que per alguna t-coloració no existeixin subgrafs complets de d punts monocolors. Aquest és un altre problema difícil: trobar la t-coloració del graf corresponent que impedeix de trobar-ne un de monocolor de la forma desitjada.
Un últim comentari sobre la teoria de Ramsey euclidiana. Tracta de problemes sobre politops a l’espai euclidià n-dimensional. Hi ha la restricció de que els conjunts de punts a considerar presenten una estructura rígida (per exemple, els punts del cub unitat), no deformable però sí amb una certa simetria. Té l’avantatge que ens és més familiar, penseu en el famós passatemps del cub de colors de Rubik.
La teoria de Ramsey té aplicacions força curioses. Per exemple, el teorema de Bolzano-Weierstrass, que diu que tota subsecció acotada de nombres reals té una subsuccessió convergent, és pot interpretar com un corol·lari del teorema de Ramsey aplicat a un conjunt convenient d’elements. A més, genera una gran fascinació el fet que la teoria de Ramsey aporta resultats i relacions entre cardinals immensos, tant en el cas finit com en l’infinit (on entra en profunda relació amb la teoria de conjunts).
Per més informació, podeu consultar:
· Ramsey Theory – Graham, Rothschild, Spencer
