Minacce aliene — Parte 1

Gli alieni invadono la Terra e minacciano di annientarla se entro un anno gli uomini non riusciranno a trovare il numero di Ramsey per cinque rosso e cinque blu. Potremmo far scendere in campo le menti migliori e i calcolatori più veloci del pianeta e probabilmente entro un anno riusciremmo a calcolare quel valore. Se tuttavia gli alieni volessero il numero di Ramsey per sei rosso e sei blu, non avremmo altra scelta se non un attacco preventivo.

“Com’è questa faccenda degli alieni?”.

“Te lo spiego con un gioco”.

“Oh, bene!”.

“Abbiamo questo schema. A turno dobbiamo colorare i segmenti che collegano i punti: io uso il rosso, tu usi il blu. Naturalmente se uno di noi ha colorato un segmento, l’altro non può colorarlo di nuovo”.



“Ok”.

“Perde il primo che forma un triangolo. Comincia tu ”.

“Uhm”.

“Cosa c’è?”.

“Di solito, quando un Vero Matematico propone un gioco, è sicuro di vincere”.

“Eh, c’è del vero in quello che dici”.

“E quindi, se le cose stanno così, io non ho nemmeno la speranza di riuscire a pareggiare. Figuriamoci se posso pensare di vincere”.

“In effetti in questo gioco non è possibile pareggiare, nemmeno giocando male”.

“Davvero? E come è possibile? Non dirmi che, anche colorando i lati a caso, si riesce sempre a creare un triangolo”.

“E invece è proprio così. In questo gioco è impossibile non avere un triangolo. Prova: colora a caso alternativamente di rosso e di blu i segmenti, e guarda come va a finire”.




“Uh, è vero. Però, se non sbaglio, un caso favorevole non dimostra un’affermazione, no?”.

“Molto bene, vedo che i miei sforzi hanno prodotto qualche risultato”.

“Eh, so che i Veri Matematici tengono molto alle loro dimostrazioni, e so che questa non lo è. E mi è venuta anche la curiosità di sapere come si possa affermare che è sempre possibile trovare un triangolo colorato”.

“Bene, bene. La dimostrazione non è difficile: il campo di gara di questo gioco...”.

“A proposito: ha un nome?”.

“Sì, si chiama Sim. Dicevo, il campo di gara è quello che i Veri Matematici chiamano grafo completo composto da 6 vertici”.

“Un esagono con tutte le sue diagonali”.

“Esatto. Qui trattiamo le diagonali vere e proprie e i lati dell’esagono allo stesso modo: li chiamiamo spigoli. Da ogni vertice escono naturalmente cinque spigoli”.

“Naturalmente”.

“Quindi almeno tre verranno colorati allo stesso modo”.

“Uhm, perché?”.

“Vuoi assegnare ogni diagonale a un colore: è come se tu dovessi distribuire cinque maglie in due cassetti, quello rosso e quello blu”.

“Cosa c’entrano le maglie?”.

“E’ un esempio: distribuisci cinque maglie in due cassetti. Quante maglie andranno in ogni cassetto?”.

“Boh, dipende”.

“Mettere una maglia in un cassetto corrisponde a colorare uno dei cinque spigoli. Riesci a fare in modo che nessuno dei due cassetti contenga tre maglie?”.

“Eh, no, è impossibile: posso mettere due maglie in ogni cassetto, per un totale di quattro maglie. Poi però mi rimane la quinta, e da qualche parte devo mettere pure quella”.

“Quindi uno dei due cassetti avrà almeno tre maglie”.

“Perché almeno?”.

“Perché potresti anche mettere tutte le maglie nello stesso cassetto. Qualunque cosa tu faccia, un cassetto conterrà certamente più di due maglie”.

“Va bene”.

“E quindi, comunque tu scelga una colorazione dei cinque spigoli che partono da un vertice dell’esagono, almeno tre di essi avranno lo stesso colore”.

“D’accordo”.

“Supponiamo che sia il blu”.

“Immagino che la dimostrazione con tre spigoli rossi sia simmetrica a questa”.

“Esattamente. I Veri Matematici usano così spesso queste simmetrie che hanno coniato un acronimo apposta: invece di scrivere che la scelta che hanno fatto non fa perdere di generalità al problema, scrivono wlog”.

“Una funzione? Una specie di logaritmo? Che roba è?”.

“Un acronimo: without loss of generality. Alcuni lo usano anche quando parlano”.

“Sono pazzi”.

“Eh, un po’. Ma andiamo avanti: chiamiamo V il vertice che abbiamo scelto. V è connesso con altri tre vertici, che possiamo chiamare R, S e T. Se uno qualsiasi degli spigoli RS, ST o RT è blu, allora abbiamo trovato un triangolo blu. Se nessuno dei tre invece è blu...”.

“...allora abbiamo un triangolo rosso!”.

“Quello di vertici R, S e T, esatto.”.

“E quindi è vero che in una qualsiasi colorazione degli spigoli di questo grafo troviamo sempre un triangolo con i lati dello stesso colore”.

“Una qualsiasi colorazione fatta con due soli colori, naturalmente”.

“Ah, sì, certo. Dunque, al gioco del Sim non si può pareggiare”.

“Proprio così. Ora, naturalmente ai matematici piace generalizzare”.

“Capirai”.

---

Questa è la prima parte di un articolo uscito sulla rivista Archimede, numero 4, del 2017.