Chi ha ucciso il Duca di Densmore?

Nelle scuole e università francofone, e nei blog che si occupano di matematica nella stessa area, circola da tempo questo problema, ispirato dal racconto poliziesco Qui a tué le Duc de Densmore? (1994) del matematico Claude Berge, fondatore e uno dei membri più autorevoli del gruppo dell'OuLiPo,  teorico della teoria dei grafi. Nell’opera originale, il detective Ralston di Scotland Yard indaga sulla morte, scoperta con un anno di ritardo, del duca di Densmore e del suo maggiordomo, avvenuta sull'isola di Wight a causa di un'esplosione. Raccolte le testimonianze delle otto persone che per ultime hanno visto in vita il duca, Ralston risolve il caso grazie all'aiuto di un suo vecchio amico, Cedric Turner-Smith, professore di Matematica al Merton College di Oxford. Il caso viene risolto grazie alla conoscenza degli studi effettuati dal matematico ungherese György Hajòs (1912-1972) nel campo della teoria grafi. In questo adattamento, del tutto privo di valore letterario, il protagonista è Sherlock Holmes e, per individuare il colpevole, è necessario l’utilizzo di un grafo degli intervalli.

Nella teoria dei grafi, un grafo degli intervalli è un grafo non orientato che rappresenta le intersezioni di un insieme di intervalli sulla retta dei numeri reali (più o meno come quando si rappresenta la soluzione di un sistema di disequazioni o si costruisce un diagramma di Gannt). Esso possiede un vertice per ogni intervallo dell’insieme e un arco tra ogni coppia di vertici che corrispondono a intervalli che si intersecano. Ad esempio, all’insieme di intervalli [1 ; 4], [3 ; 7], [3 ; 5], [6 ; 9] si può associare il grafo più sotto:

Dove i vertici A e D (e C e D) non sono collegati perché gli intervalli corrispondenti non si intersecano. È evidente che tale grafo esiste se, e solo se, esiste almeno un’intersezione.

Una proprietà di questi grafi degli intervalli è che è impossibile un grafo che presenti un ciclo senza diagonale come quello qui rappresentato:

Dove A non può essere collegato a D senza esserlo a C (chi non ci crede provi a disegnare gli intervalli corrispondenti, con estremi a piacere). Esiste infatti un teorema (di Gilmore e Hoffman) che afferma che un grafo è un grafo degli intervalli se, e solo se, è “triangolato”, vale a dire che ogni ciclo di lunghezza maggiore di 3 deve possedere una diagonale.

---

Un giorno, Sherlock Holmes ricevette la visita dell’amico Watson, che era stato incaricato di condurre un’indagine su un misterioso assassinio avvenuto tre anni prima, quando il vecchio Duca di Densmore era morto a causa dell’esplosione di una bomba che aveva completamente distrutto il castello in cui si era ritirato.

I giornali del tempo avevano riferito che il testamento, distrutto anch’esso nell’esplosione, aveva tutti gli elementi per dispiacere a una delle sue sette ex-mogli. Ora, prima di morire, il Duca le aveva invitate tutte a trascorrere qualche giorno nella sua tenuta scozzese.

Holmes: Mi ricordo di questa vicenda. Ciò che mi sembra strano è che la bomba era stata costruita appositamente per essere nascosta nella struttura della camera da letto, il che implica che l’assassino ha necessariamente effettuato diverse visite al castello!

Watson: Di sicuro, e per questo motivo ho interrogato ciascuna delle donne: Ann, Betty, Charlotte, Edith, Felicia, Georgia e Helen. Tutte hanno giurato di essere state una sola volta nella loro vita al castello di Densmore.

Holmes: Uhm… Avete chiesto loro in quale periodo vi hanno soggiornato?

Watson: Ahimè! Nessuna ricordava la data esatta, dopo più di tre anni! Tuttavia ho chiesto loro chi avessero incontrato. Ecco, ho fatto questo elenco:

Ann ha incontrato Betty, Charlotte, Felicia e Georgia.

Betty ha incontrato Ann, Charlotte, Edith, Felicia e Helen.

Charlotte ha incontrato Ann, Betty e Edith.

Edith ha incontrato Betty, Charlotte e Felicia.

Felicia ha incontrato Ann, Betty, Edith e Helen.

Georgia ha incontrato Ann e Helen.

Helen ha incontrato Betty, Felicia e Georgia.

Come vedete, caro Holmes, le risposte sono concordanti!

Holmes, senza dir parola, prese una matita e tracciò uno strano schema, con dei punti indicati con A, B, C, E, F, G, H e delle linee che univano alcuni di questi punti. Lo guardò attentamente per un paio di minuti, poi disse:

Holmes: Bene, bene. Ciò che mi avete appena detto individua la colpevole in modo univoco!

Chi è l’assassina?

---

Come Holmes, disegniamo un grafo degli intervalli con i vertici A, B, C, E, F, G e H. In questo caso gli intervalli considerati sono intervalli di tempo. Nel grafo colleghiamo i vertici corrispondenti all’iniziale del nome se le sospettate si sono incontrate al castello per un certo intervallo di tempo.

Per scoprire quale delle sette donne è stata più di una volta al castello, bisogna cercare nel grafo dei cammini chiusi che collegano quattro vertici, senza diagonale. Ora, A è vertice di tre cicli senza diagonale (AFHG, ABHG e ACEF). Non ci sono l’arco AH e l’FG per il ciclo AFHG, così come non ci sono AH e BG in ABHG e non ci sono AE e FC in ACEF. Il grafo degli intervalli è perciò difettoso.

Il problema dice che c’è solo un’assassina. Cerchiamo allora di scartare solo un vertice, in modo che il grafo restante diventi triangolato. Tale vertice è all’intersezione di tutti i cicli con lunghezza maggiore di 3 senza corda, AFHG, ABHG e ACEF, cioè A, mentre quando vengono cancellati gli altri tre vertici di ogni ciclo, il grafico rimane difettoso. Così facendo, il subgrafo rimanente è infatti un grafo degli intervalli “triangolato”, cioè regolare.

Si dovrebbero aggiungere almeno tre copie di A per eliminare i tre cicli di lunghezza 4 e ottenere un grafo degli intervalli corretto. Ciò significa che Ann è stata al castello almeno tre volte!

Per essere sicuri, costruiamo lo schema degli intervalli temporali, che corrisponde alle dichiarazioni delle donne. L’unica maniera che rispetti le intersezioni tra gli intervalli è illustrata qui sotto:

Si può perciò concludere che è Ann l’assassina.