Visualizza il feed RSS

Titolo provvisorio...

Il valzer delle coppie...

Valutazione: 3 voti, con una media del 3.33.
di pubblicato il 30-10-2012 alle 17:56 (6327 Visite)
Sottotitolo: Donna Letizia risponde.

Il problema del quale trattiamo, noto in letteratura come problème des ménages, è uno dei più universalmente citati e discussi in combinatorica: tanto che si fa realmente fatica a trovare un testo specialistico nel quale non venga analizzato, o quantomeno menzionato - sovente più volte. Al tempo stesso è deliziosamente retrò per il modo così tipico in cui è stato formulato alla fine dell'Ottocento e per il suo stesso contenuto: si parla infatti di determinare il numero dei modi in cui n coppie - dove n è ovviamente un numero naturale maggiore di due - possono essere disposte a sedere attorno ad un tavolo circolare, alternando rigorosamente uomini e donne e facendo sì che nessun marito si trovi seduto accanto alla propria consorte. Qui la goliardia della scolaresca inizia inevitabilmente a scatenarsi...

La citazione della compianta Colette Rosselli, moglie del non meno compianto Indro Montanelli e soprattutto madre e madrina letteraria di quella Donna Letizia che dagli anni Cinquanta ha dispensato per almeno quattro decadi lezioni di galateo, signorilità e raffinato umorismo agli italiani, è pressoché obbligatoria: il bon ton dei ricevimenti conviviali, infatti, è considerato uno dei più fondamentali requisiti della buona società e fa appello ad un lunghissimo elenco di norme, sovente non scritte, quasi sempre del tutto arbitrarie.
A ciò si aggiunge il francesismo del nome, che si mantiene nella letteratura internazionale: piuttosto scontato in origine, se si considera che tale problema è stato formulato nel 1891 dal matematico francese Edouard Lucas nel suo "Théorie des nombres", eppur sufficiente ad ammantare la questione di un tocco esotico e impliciti richiami a raffinatezza ed eleganza. Da sempre, infatti, il francese è la "lingua ufficiale" nei ristoranti di alta cucina e soprattutto nell'alta moda, un mondo non a caso noto come haute couture e popolato dalle varie maisons.

Osserverei, en passant, che sebbene i consigli di Donna Letizia apparissero già obsoleti (o quantomeno frivoli, fuori posto, forse un tantino irrazionali) a noi adolescenti negli anni Settanta e Ottanta, nondimeno i principi di quella che possiamo a pieno titolo definire la formazione andragogica di tante coppie neo-benestanti degli anni del boom economico sono da salvare e conservare: specialmente in un momento di oclocrazia selvaggia, terrapiattismo, qualunquismo e volgarità gratuita come il presente.

A fortiori c'è dunque grande compiacimento nel presentare la versione più tradizionale di questo problema, immaginando anzi (come in una commedia di Feydeau) di accompagnare l'assegnazione dei posti con appropriate musiche d'epoca, inchini e riverenze un po' farseschi di ridanciane e ammiccanti dame piumate che muovendo con studiata nonchalance i ventagli scoprono spesso e volentieri i decolletées abbondantemente incipriati, mentre signori sempre un po' allampanati, con baffoni a manubrio e favoriti, fumano grossi sigari e si inteccheriscono come manici di scopa nel saluto militaresco sbattendo i tacchi e chinando il capo - inevitabile pensare anche a questa serie di divertenti e utili filmati preparati dagli amici dell'Università "La Sapienza" (per l'occasione, parliamo di quella situata in Romania, non in Roma ). Eppure... eppure non manca perfino chi osa asserire con livorosa albagia, scimmiottando alla lontana Benedetto Croce, che la scienza sarebbe noiosa, piatta, arida, illetterata e priva di creatività!

La storia del problema, di per sé, è interessante e ricca di connessioni inaspettate con altre branche matematiche, in particolare la teoria dei nodi. Lo spazio è però tiranno, e ci costringe ad accontentarci di una telegrafica cronistoria, limitata al secolo scorso. Eccone, in estrema sintesi, le tappe principali:

1934 - Jacques Touchard [1] pubblica una formula risolutiva in forma chiusa, senza però dimostrarla. Ecco tale formula:

Formula LaTeX: (1)\ \ \ 2\cdot n!\left[\sum_{k=0}^{n}(-1)^k\frac{2n}{2n-k}\binom{2n-k}{k}(n-k)!\right]

1943 - Irving Kaplanski [2] pubblica la prima dimostrazione della formula di Touchard.

1986 - Viene fornita da K. Bogart e P. Doyle [3] la prima dimostrazione elementare della (1), ripresa poi in numerosi testi.

2005 - Una giovane studentessa, Amanda Passmore [4], pubblica una rivisitazione della dimostrazione di Kaplanski, usandone i lemmi fondamentali ma impiegando unicamente concetti elementari di conteggio nella loro giustificazione.

La lezione fondamentale che dev'essere tratta dalla storia del teorema è che la dimostrazione di Bogart e Doyle ha richiesto un vero e proprio cambio di paradigma rispetto all'approccio cavalleresco (che nella tipica sfera di influenza del glass roof viene sbrigativamente tradotto con "sessista") di assegnare prima i posti alle signore, seguito fino ad allora. Dal punto di vista combinatorico tale approccio complica inutilmente il conteggio delle possibili permutazioni. Naturalmente Bogart e Doyle usano il riferimento al sessismo in modo volutamente leggero e ironico...

Ricordiamo brevissimamente, in termini assolutamente elementari, il concetto di permutazione semplice e permutazione vincolata (derangement o dismutazioni). Dato un insieme finito contenente n elementi distinti, si dicono permutazioni le presentazioni ordinate che si possono formare in modo da soddisfare contemporaneamente i seguenti criteri:
1) Ogni presentazione deve contenere tutti gli n elementi, ciascuno considerato una e una sola volta;
2) Ogni presentazione deve differire dalle altre solo e unicamente per l'ordine degli elementi.

In altri termini, una permutazione è una regola che ad ogni elemento dell’insieme dato associa un naturale (un ordinale finito, per l'esattezza) che ne descrive la posizione, in modo univoco - ovvero, in ultima analisi, essa costituisce un criterio di ordinamento. La formuletta che esprime il numero di permutazioni in funzione dell'intero non negativo n è arcinota e fa riferimento al fattoriale:

Formula LaTeX: (2)\ \ \ P(n) = n! = \begin{cases}1 & \text{ per } n \in \{0, 1\}\\ \prod_{i=1}^{n}i& \text{ per } n > 1 \end{cases}

Chiamiamo derangement una permutazione nella quale nessun elemento rimane al proprio posto di partenza, ovvero una permutazione priva di punti fissi.
Ad esempio, con esplicito riferimento alla permutazione base (permutazione identità) a0a1a2a3, si ha che a3a0a1a2 è un derangement, mentre a2a1a0a3 non lo è, perché almeno un elemento ai occupa la i-esima posizione (in questo banale esempio, i=3, evidenziato in rosso).

Il numero dei derangement si indica generalmente con D(n), ed esiste un apposito operatore "cofattoriale" per indicare tale quantità, definito come segue:

Formula LaTeX: \begin{align*}\\ (3)\ \ \ D(n) &= \ !n = n!\sum_{k=0}^{n}(-1)^k\cdot(k!)^{-1}\\ &= {\color{red}n!\cdot\left ( 1-\frac{1}{1!}+\frac{1}{2!}-\cdots +\frac{(-1)^n}{n!} \right )}\end{align*}

Formula LaTeX: (4)\ \ \ D(n) =\left \lfloor{\frac{n!}{e}+\frac{1}{2}} \right \rfloor \text{per n} \geqslant 1

Quante delle possibili permutazioni sono anche derangements? La risposta è piuttosto semplice.

Consideriamo l'espressione (3), nella forma espansa riportata ed evidenziata in rosso alla seconda linea: se dividiamo per n!, la rimanente serie tra parentesi non è altro che lo sviluppo di MacLaurin di e-1, e converge molto rapidamente a tale valore (il reciproco del numero di Nepero) al crescere di n.
D'altro canto, anche l'espressione (4) rende assai evidente che il rapporto tra !n e n! tende appunto al reciproco di e per n sufficientemente grande. Con buona approssimazione, una permutazione ogni tre è dunque un derangement ed è anzi facile incontrare in letteratura la (4) nella seguente forma:

Formula LaTeX: (5)\ \ \ D(n)\approx \frac{n!}{e}

Nessuno si stupisca nell'apprendere che la maggior parte dei generatori di derangement non sono altro che normalissimi generatori di permutazioni "con filtro", ovvero un meccanismo di riconoscimento e rifiuto delle permutazioni che non sono derangements, che non penalizza eccessivamente le prestazioni complessive.

Osserviamo un po' più da vicino il problema. Dopo aver assegnato un posto ad uno dei coniugi di una coppia, l'altro può sedersi in un qualsiasi posto libero, eccetto due di essi: quelli adiacenti al posto del proprio coniuge.
Questo vincolo è espresso efficacemente dalla seguente matrice binaria ciclica, esemplificata per n = 8, con la convenzione che ogni indice di riga identifica una coppia, le colonne individuano le sedie, e il valore nullo marca i posti "proibiti".

Formula LaTeX: \begin{bmatrix}0&1&1&1&1&1&1&0\\0&0&1&1&1&1&1&1\\1  &0&0&1&1&1&1&1\\1&1&0&0&1&1&1&1\\1&1&1&0&0&1&1&1\\  1&1&1&1&0&0&1&1\\1&1&1&1&1&0&0&1\\1&1&1&1&1&1&0&  0 \end{bmatrix}

Si noti che sovente in letteratura si usa anche la convenzione inversa, in modo che ciascuna riga contenga esattamente due valori pari a uno.

In ultima analisi, quindi, risolvere il problema significa trovare (per ogni singola permutazione delle signore o dei signori) tutti e soli quei derangements che rimangono tali anche dopo una rotazione a destra di una posizione. In altri termini, dato l'usuale insieme finito dei primi n naturali {0, 1, ..., n-1}, consideriamo tutte e sole le sue permutazioni nelle quali nessun elemento ai occupi la posizione i-1 (mod n) né la posizione i, per ogni i nel range [0, n-1]. La sommatoria nella formula (1) esprime appunto il numero di tali derangements condizionati.

Formula LaTeX: (6)\ \ \ Dc(n) = \sum_{k=0}^{n}(-1)^k\frac{2n}{2n-k}\binom{2n-k}{k}(n-k)!

I primi valori di tale sequenza (OEIS A000179), per n > 2, sono: 1, 2, 13, 80, 579, 4738, 43387...

Considerando ad esempio i nove possibili derangements per n = 4, soddisfano le condizioni poste solo i seguenti due:

Formula LaTeX: \begin{matrix}2&3&0&1& \mapsto&1&2&3&0\\3&0&1&2& \mapsto&2&3&0&1\end{matrix}

Il problema-giocattolo informatico che ci poniamo in questa sede, al solito scopo didascalico di stimolare riflessioni e approfondimenti, è quello di generare delle soluzioni valide al problema dei ménage. Come aperitivo (anzi, amuse-bouche ) vediamo come generare velocemente e facilmente una singola soluzione, in modo pseudocasuale.

Lasciati per alcune decine di minuti liberi di lavorare sugli input sopra forniti, di solito gli studenti si producono in una serie di inutili, arzigogolate, cervellotiche complicazioni sul tema, con sofisticati generatori PRNG, algoritmi a pettine, discese ricorsive e scorrimenti incrociati, dimenticando il principio KISS: Keep It Simple, Stupid.

Generare una singola soluzione valida è assolutamente banale: si parte da una qualsiasi delle configurazioni più sbagliate in assoluto, quelle cioè nelle quali ciascun marito siede accanto alla propria moglie (in un qualsiasi ordine delle coppie attorno al tavolo), e si applica quindi alle signore o ai signori una rotazione dei posti, senza variarne l'ordine relativo. In questo modo andiamo a generare sicuramente un derangement relativo all'ordine dei coniugi già seduti.
L'esempio delle permutazioni valide per n=4, nella sua basilare semplicità, è assolutamente illuminante da questo punto di vista: in tale caso, infatti, gli unici derangements ristretti validi sono rotazioni, a destra per fissare le idee, di una e due posizioni rispettivamente, a partire dalla sequenza "naturale" in ordine lessicografico ascendente. L'ampiezza di tale rotazione, più in generale, è banalmente compresa tra uno e n-2 posti, estremi inclusi: questo perché inizialmente gli insiemi di signore e signori coincidono (si può dire, con un certo grado di abuso lessicale, che le rispettive sedie sono sovrapposte), e solo in seguito gli array vengono sfalsati tra loro con l'aggiunta di un ulteriore offset implicito pari a +1 o -1, in modo da intercalare posti pari e dispari scegliendo arbitrariamente se partire da una signora o da un signore.
Al di là di questi banalissimi dettagli di bassa cucina, quel che interessa è che la rotazione può essere validamente resa pseudocasuale con un qualsiasi PRNG. As easy as 1-2-3.

Segue il main() del relativo programma in C: la quintessenza della banalità.
codice:
int main(void)
{
    uint i, offset;
    uint Chaises[MAX_COUPLES];

    /*
    ** Per rendere minimamente interessante l'output, si
    ** parte da una permutazione pseudocasuale dei
    ** cognomi, invece di limitarci al banale ordine 
    ** lessicografico.  
    */
    srand(NULL);
    shuffle(Chaises);

    /* 
    ** Si calcola l'offset, ossia il numero di sedie 
    ** da interporre come "distanza di sicurezza"
    ** tra mariti e mogli... :-) 
    */
    offset = 1 + (rand() % (MAX_COUPLES -2));

    /*
    ** G A M E   O V E R 
    */
    for (i = 0; i < MAX_COUPLES; ++i)
    {
        printf("%2d Madame %-10s %2d Monsieur %-10s\n",
               2*i+1, Surnomes[Chaises[i]],
               2*i+2, Surnomes[Chaises[(i + offset) % MAX_COUPLES]]);
    }

    return (0);
}
Per gli svogliati, ecco l'intero codice di esempio in un file di testo: menage_c.txt

Gli allegati del'intera serie di articoli sono stati riorganizzati ed espansi. Si veda questo post.

Naturalmente la generazione esaustiva delle soluzioni è un tantino più seria e impegnativa, ma non troppo... per intanto, la prossima volta che inviterete a cena qualche coppia di amici, saprete già come metterli a sedere.

[1] Touchard, J. "Sur un problème de permutations", C. R. Acad. Sciences Paris 198 (1934): 631–633.

[2] Kaplansky, Irvin. "Solution of the Problème des Ménages". Bulletin of the American Mathematical Society 49 (1943): 784-785.

[3] Bogart, Kenneth and Peter Doyle. "Non-sexist Solution of the Ménage Problem". Amer. Math. Monthly 93 (1986), no. 7, 514–519.

[4] Passmore, Amanda. "An elementary solution to the ménage problem".

Commenti