Sei persone si incontrano a una festa. Alcune si conoscono già, altre si presentano per la prima volta. Senza sapere nulla delle loro storie, possiamo essere certi che fra loro esista una piccola regolarità?
Il gioco chiede di trovare tre persone che si conoscano tutte fra loro, oppure tre persone nessuna delle quali conosca le altre due. Le relazioni possono essere distribuite in qualunque modo: non scegliamo noi chi arriva alla festa.
Servono soltanto sei punti, due colori e un ragionamento breve. La sorpresa è che la conclusione non dipende dalla fortuna né dalla probabilità di incontrare un vecchio amico.
PROBLEMA 1729 #046
Tempo: 10–15 minuti
Difficoltà: Medio
Categoria: Grafi e teoria di Ramsey
Il problema
A una festa ci sono sei persone. Per ogni coppia di persone distinte vale esattamente una delle due possibilità: si conoscono oppure non si conoscono. La conoscenza è reciproca: se Anna conosce Bruno, anche Bruno conosce Anna.
Dimostra che esistono sempre tre persone che si conoscono a due a due, oppure tre persone che non si conoscono a due a due. Possono esistere entrambe le situazioni.
Non supponiamo che la conoscenza sia transitiva: conoscere una persona che conosce Carlo non significa conoscere Carlo. Come seconda sfida, mostra perché cinque persone non bastano a garantire la stessa conclusione.
Prima di proseguire, fermati: disegna sei punti, unisci ogni coppia e usa il blu per chi si conosce e l’oro per chi non si conosce. Cerca un triangolo con tutti e tre i lati dello stesso colore.
💡 Mostra un indizio
Scegli una sola persona e osserva i suoi cinque rapporti con le altre. Puoi dividerli in due gruppi senza che almeno uno contenga tre rapporti?
Se entrambi i gruppi ne contenessero al massimo due, arriveresti soltanto a quattro. È il principio dei cassetti applicato a cinque relazioni e due possibilità.
💡 Mostra un indizio
Supponi che Anna conosca Bruno, Carla e Diego. Se due di questi tre si conoscono, hai già trovato una terna con Anna. Che cosa succede se nessuna coppia fra loro si conosce?
Per il caso in cui Anna non conosca tre invitati, scambia semplicemente i ruoli dei due colori.
✅ Mostra la soluzione
Indichiamo una persona con A. Fra le altre cinque ce ne sono almeno tre che A conosce, oppure almeno tre che A non conosce. Chiamiamole B, C e D.
Caso 1: A conosce B, C e D
Se almeno una coppia fra B, C e D si conosce, quella coppia insieme ad A forma tre persone che si conoscono tutte fra loro. Se invece nessuna coppia si conosce, B, C e D sono già tre persone reciprocamente sconosciute.
Caso 2: A non conosce B, C e D
Se almeno una coppia fra B, C e D non si conosce, quella coppia insieme ad A forma tre persone reciprocamente sconosciute. Se invece tutte le coppie si conoscono, B, C e D formano una terna di conoscenti.
I due casi esauriscono le possibilità. Dunque con sei persone la terna richiesta esiste sempre.
Perché cinque non bastano
Disponi A, B, C, D, E sui vertici di un pentagono. Supponi che ciascuno conosca soltanto i suoi due vicini lungo il bordo: le conoscenze sono AB, BC, CD, DE, EA. Le altre cinque coppie non si conoscono.
Le linee blu formano un ciclo di cinque lati, privo di triangoli. Anche quelle oro formano un ciclo di cinque lati, percorso nell’ordine A, C, E, B, D, A. Non c’è quindi alcuna terna tutta blu né tutta oro. Un triangolo del problema deve avere come vertici tre persone: gli incroci delle diagonali non aggiungono invitati.
Sei persone bastano sempre; cinque possono non bastare.
La matematica dentro al gioco
Abbiamo colorato gli spigoli del grafo completo K₆: sei vertici e un collegamento per ogni coppia, per un totale di 6 × 5 / 2 = 15 spigoli. Cerchiamo un triangolo monocromatico, cioè una terna i cui tre collegamenti abbiano lo stesso colore.
La scrittura R(3,3) = 6 indica il minimo numero di vertici che garantisce un triangolo blu oppure un triangolo oro in ogni colorazione a due colori. La prova ha due parti indispensabili: mostrare che sei bastano e costruire un esempio in cui cinque falliscono.
Qui non stiamo assumendo che ciascun colore abbia probabilità 1/2: la conclusione vale per ogni configurazione. Il principio dei cassetti trova tre relazioni dello stesso tipo; il controllo delle relazioni fra quei tre invitati completa il ragionamento.
Per una trattazione classica si può consultare l’apertura di Ramsey Theory, di Ronald L. Graham, Bruce L. Rothschild e Joel H. Spencer, che esplicita anche la simmetria della relazione di conoscenza.
Una variante per te
Puoi dimostrare che le terne omogenee sono sempre almeno due? Contiamo prima quelle miste, con due lati di un colore e il terzo dell’altro.
Da una persona partono cinque collegamenti. Se d sono blu, gli altri 5 − d sono oro. Le coppie di collegamenti di colori diversi che partono da quella persona sono d(5 − d), al massimo 6: basta controllare d = 0, 1, 2, 3, 4, 5.
Sommando su tutte le sei persone otteniamo al massimo 36 coppie. Ogni triangolo misto viene contato esattamente due volte, nei due vertici dove incontra lati di colori diversi. I triangoli misti sono quindi al massimo 18.
Le terne possibili sono 6 × 5 × 4 / 6 = 20. Ne restano almeno 20 − 18 = 2 omogenee. Il limite si raggiunge: dividi gli invitati in due gruppi di tre, tutti conoscenti all’interno del proprio gruppo e tutti sconosciuti fra gruppi diversi. Le uniche terne omogenee sono i due gruppi iniziali.
Lo sapevi?
Il nome della teoria ricorda Frank P. Ramsey. Il suo tema generale è capire quando una struttura sufficientemente grande deve contenere una configurazione ordinata, qualunque sia la distribuzione dei colori.
Erdős contribuì enormemente allo sviluppo di queste domande, soprattutto usando il caso per dimostrare l’esistenza di configurazioni che evitano grandi gruppi omogenei. Le note introduttive dell’Università di Washington sul metodo probabilistico partono proprio dal problema delle sei persone per arrivare ai numeri di Ramsey.
La festa è un modo concreto di entrare nel problema. Cambiando “si conoscono” in un’altra relazione simmetrica a due possibilità, la stessa dimostrazione continua a funzionare.
Problema 1729
#046 — Sei persone a una festa: amici o sconosciuti?
Giochi, enigmi e idee matematiche per menti curiose.
Lascia un commento