A quel punto lo accontentai e mi misi a studiare quello strano domino: recentemente, il domino incriminato mi è ritornato in mano e ho pensato di farvene partecipi.
A proposito, vi siete mai chiesti da dove venga il domino e che cosa siano quei numeri? Con beneficio di inventario, il domino è arrivato in Italia dalla Cina nel XII secolo: in un qualche momento imprecisato del millenio precedente, i cinesi avevano ricevuto i dadi dall'India e, per evitare la fatica di lanciarli (o il pericolo di dadi truccati), hanno pensato bene di spianarli. Infatti, il domino cinese (vedi figura qui sotto) rappresenta tutti i ventuno punteggi che si possono ottenere lanciando un paio di dadi (nei dadi cinesi, tradizionalmente, l'uno e il quattro sono dipinti di rosso)
Ma, come potete vedere dalla figura, il domino cinese non è affatto semplice come il nostro e non presenta i problemi che ho avuto io anche perché un certo numero di pezzi sono doppi (totale, 32 pezzi): il gioco consiste nel formare combinazioni di tre domini (e si è poi evoluto nel Mah-jong).
Visto che i veneziani non volevano saperne di imparare queste diavolerie cinesi hanno pensato bene di semplificare il tutto tenendo solo un esemplare per ogni tessera; di conseguenza, per poter giocare, sono stati costretti ad aggiungere la riga degli zeri ottenendo un set di ventotto pezzi che potevano essere disposti tutti in catena.
Tornando al nostro domino con sei simboli (in figura), prendiamo a prestito dalle carte da gioco il concetto di seme: un seme è il set dei pezzi che contengono un determinato simbolo.
Per esempio, la prima riga della figura precedente è il seme dello $0$, la sesta colonna è il seme del $5$.
Il gioco consiste nel formare una catena ponendo i domini uno accanto all'altro in modo che si tocchino le estremità contenenti numeri uguali: la figura successiva, nella prima riga, mostra gli unici tre modi in cui questo può essere fatto (non contando rotazioni e riflessioni)
La seconda riga contiene posizioni vietate: il quadrato vìola la regola che solo numeri uguali possano essere contigui (ogni domino è presente come esemplare singolo); il gruppo a destra vìola la regola che ogni pezzo può essere connesso solo ad altri due, altrimenti al posto di una catena avremmo una rete.
Il quadrato centrale vìola una regola non espressa che vieta di formare catene chiuse: se si forma una catena chiusa nessuno può vincere.
Prendiamo in considerazione un seme, per esempio, lo $0$
Il simbolo $0$ compare affiancato a tutti i simboli (compreso se stesso): se ora uniamo i pezzi tra loro osserviamo che, in qualunque modo facciamo, otteniamo sempre una catena che termina con $0$ perchè i sei pezzi contengono sette esemplari di $0$
Questo è vero per qualunque seme.
Per trovare la catena di lunghezza massima è sufficiente togliere tre domini che contengano tutti e sei i simboli, per esempio
ed ecco che, avendo ristabilito la parità negli esemplari di ciascun simbolo, diviene possibile formare una catena chiusa con i domini rimanenti. Per esempio
Qualunque sia il punto in cui decidiamo di aprire la catena otterremo sempre una catena con alle due estremità lo stesso simbolo: quindi, sarà impossibile attaccare più di uno dei tre domini che avevamo messo da parte, per esempio
In generale, per un domino con $n$ simboli ($n$ pari) avremo un numero minimo di domini avanzati pari a $n/2 \/ - \/ 1$.
Per stabilire quanto è lunga la catena minima consideriamo due semi, per esempio lo $0$ e l'$1$: uniti i domini a due a due
formiamo una catena "intraseminale"
Questa catena inizia con un seme e termina con l'altro avendo consumato tutti gli esemplari di ciasuno dei due; una catena più corta avrà necessariamente un'estremità con un seme diverso che consentirebbe di continuare ad attaccare. Qualcuno potrebbe pensare che i pezzi "doppi" possano essere lasciati fuori ma, dato che tolti loro, la catena finisce con $0$ ad un'estremità e $1$ all'altra, entrambi i domini esclusi possono essere riattaccati.
Poniamo ora attenzione al fatto che l'aggiunta di due nuovi simboli comporta l'aggiunta di due domini per ogni seme
risulta evidente che due semi formano una catena minima qualunque sia $n$ pari: cioè, in generale, la catena minima è lunga $2n \/ - \/ 1$.
Poiché il numero di domini dipende quadraticamente da $n$ e la catena minima solo linearmente, non ci vuole molto perché divenga molto difficile che qualche giocatore riesca a finire i suoi pezzi: per esempio, con $n \/ = \/ 20$ la catena minima è di $39$ domini su $210$ totali...
Venendo poi al suggerimento di Quelo, il set di domini a sei simboli è isomorfo a questo grafo
Possiamo rendercene conto osservando che i domini corrispondono agli archi che uniscono i sei nodi del grafo: per il seme dello $0$
Il grafo corrispondente ai semi dello $0$ e dell'$1$ rende subito evidente che l'aggiunta di due nuovi semi corrisponde all'aggiunta di un percorso chiuso che non altera il risultato che si ha fin dal set con due soli semi e cioè che la catena minima è formata con i domini di due semi.
Viceversa, il grafo isomorfo con la catena massima si ottiene ripetendo per sei volte consecutive la sequenza in rosso
col che si torna di nuovo in $0$ e si può completare la catena andando in $3$
Solo uno degli archi che uniscono nodi opposti può essere percorso.
