Giuccube

Più che succube.

Papino, ma tu sai contare in Russese?

Russo, Russese, in fondo basta capirsi, e si sa che mia figlia è un po’ creativa. In ogni caso la frase è stata pronunciata dopo che ci siamo messi a contare da 1 a 10 in Toscano, Milanese, Lituano, Inglese ed Estone.

Carissimo…

Non reggo più quelli che ti conoscono appena e quando ti incontrano (o quando ci si sente al telefono) fanno partire quell’insopportabile “carissimo…”, quasi sempre pronunciato in modo radioso. Matematico che stanno per rifilarti una fregatura. Recentemente a chi si rivolge a me in quel modo ho preso l’abitudine di replicare con un ben più ironico “santità, dimmi pure”.

Strette di mano incrociate e non incrociate

Questo post nasce dopo la cena di ieri sera. Gli amici Angelika e Vadim, una simpatica coppia moldava, sono stati da noi per una pizza. Una volta varcato l’ingresso è stato il turno dei saluti e – come spesso accade in questi casi – si è creata una situazione di incrocio. In passato mi sarà capitato altre mille volte (e lo stesso sarà accaduto a chi legge), tuttavia questa volta ho sentito il bisogno di metterci dentro un po’ di matematica.

Ho intitolato il post in questo modo anche se i saluti non necessariamente si svolgono sotto forma di strette di mano. È uso scambiarsi una stretta di mano tra uomini (sia tra conoscenti che tra sconosciuti); tra donne prevale la stretta di mano quando non ci si conosce e il bacio in caso di amicizia; idem tra uomo e donna. Questa almeno è la convezione diffusa qui in Padania. Scendendo nella vicina Italia (in particolare nell’Italia meridionale), e ancor più passando dall’Italia alla Sicilia, il bacio tende a diffondersi anche tra gli uomini, specie se conoscenti.
In ogni caso in termini matematici il problema è equivalente allo scambio di strette di mano simultanee tra un numero pari* di soggetti disposti simmetricamente** attorno a un tavolo rotondo.

Mi sono domandato: quanto è probabile incorrere in una situazione di saluti incrociati?

Per fare ciò prima di tutto è necessario calcolare le configurazioni di coppie di possibili strette di mano. Partiamo da un caso semplice***: quattro persone intorno a un tavolo che occupano le posizioni est (E), nord (N), ovest (O) e sud (S). Le configurazioni simultanee sono tre:

O-N, S-E
N-E, O-S
S-N, O-E

Le prime due non danno luogo a incroci, la terza sì.

Si tratta ora di capire cosa succede quando le coppie salgono di numero, cioè quando intorno a un tavolo ci sono 6, 8, 10, …, 2n persone.
Si può dimostrare abbastanza agevolmente che le configurazioni possibili (S) sono:

S(2n) = (2n – 1)(2n – 3)*…*5*3*1 = (2n – 1)!!

Il doppio punto esclamativo indica il semifattoriale, talvolta chiamato fattoriale doppio, con una delle espressioni più ambigue e infelici di tutta la matematica. Quando il semifattoriale è applicato a un numero dispari si può passare al fattoriale mediante la formula seguente:

(2n – 1)!! = (2n)!/(n!2n)

Da cui deduciamo che con sei persone attorno al tavolo le possibili configurazioni di strette di mano simultanee sono 15. Queste diventano 105 con otto persone, 905 con dieci persone, 10.395 con dodici persone, ecc.

A questo punto dobbiamo determinare il numero di configurazioni di strette di mano che non si incrociano (s). Di fatto ciò equivale a calcolare il numero di corde non intersecantisi che connettono 2n punti disposti su una circonferenza. Si tratta di uno dei numerosi risultati matematici che chiamano in causa i numeri di Catalan.

s(2n) = (2n)!/(n!(n + 1)!)

I valori sono s(2) = 1, s(4) = 2, s(6) = 5, s(8) = 14, s(10) = 42, s(12) = 132, …

La probabilità di incorrere in un saluto incrociato, ciò che mi ero proposto di calcolare, è dunque data dal complemento a 1 del rapporto s/S:

P(2n) = 1 – s(2n)/S(2n) = 1 – 2n/(n + 1)!

P(2) = 0%
P(4) = 33,33%
P(6) = 67,67%
P(8) = 86,67%
P(10) = 95,56%
P(12) = 98,73%

Come si nota, la probabilità di incorrere in una stretta di mano incrociata aumenta molto rapidamente. I casi più frequenti sono i saluti tra 4 e 6 soggetti; nel primo caso la probabilità di un saluto incrociato è una su tre, nel secondo raddoppia a due su tre. La matematica, dunque, dimostra che l’elevata frequenza con cui si verificano situazioni di questo tipo è del tutto normale.

_____
* se i soggetti fossero dispari verrebbe meno la condizione di simultaneità

** una disposizione simmetrica non è un vincolo necessario, tuttavia è utile per visualizzare meglio le diverse configurazioni

*** se le persone sono due (caso banale) c’è una sola configurazione possibile: una stretta di mano non incrociata

Quanto è lunga la password?

La password di accesso al mio conto bancario online è formata da n lettere tutte diverse tra loro. Un ladro che volesse impossessarsene dovrebbe provare, nella peggiore delle ipotesi, un certo numero di sequenze. Tuttavia se la password fosse più corta di due lettere i tentativi del ladro si ridurrebbero a un quarantaduesimo di quelli iniziali. Quanto è lunga la password?

L’equazione da impostare è la seguente:

(n – 2)! = n!/42

da cui:

(n – 2)! = n(n – 1)(n – 2)!/42
n(n – 1) = 42
n2n – 42 = 0

Le due soluzioni sono n = -6 (non accettabile) e n = 7. Dunque la mia password è lunga sette caratteri.

I divisori di 60.000

Quanti divisori ha il numero 60.000? In apparenza sembrerebbe un problema molto difficile, in realtà non è così. 60.000 può essere fattorizzato come (25)(31)(54), dunque ogni suo divisore ha la forma 2a3b5c. Dato che a può assumere uno qualunque dei sei valori compresi tra 0 e 5, b può assumere i valori 0 e 1, e c può assumere uno qualunque dei cinque valori compresi tra 0 e 4 la soluzione è data da 6*2*5 = 60.

Il trucco dei delimitatori nel calcolo combinatorio

Immaginiamo la seguente situazione. Quattro persone si recano al voto; entrano in cabina, compilano la scheda elettorale e poi la depositano all’interno di una delle quattro urne disponibili. Le urne sono identiche e indistinguibili; ciascun elettore entra a turno, quindi non vedo ciò che ha fatto chi lo ha preceduto. Al termine delle votazioni qual è la distribuzione delle schede nelle urne? Può capitare che finisca una scheda in ciascuna urna, che tutte le schede finiscano nella stessa urna e tutte le configurazioni intermedie tra queste due. Quante sono le configurazioni possibili?

Tutti i problemi di questo tipo possono essere risolti applicando un piccolo trucco, detto dei delimitatori. La situazione in cui troviamo una scheda in ciascuna urna può essere rappresentata come segue (gli asterischi schematizzano le schede, le barre verticali sono i delimitatori tra le urne):

* | * | * | *

La situazione in cui, ad esempio, ci sono tre schede nella seconda urna e una nella quarta è invece rappresentabile come indicato sotto:

| *** || *

Enumerare tutte le possibili configurazioni significa determinare tutti i modi in cui possiamo disporre i tre delimitatori tra i sette oggetti costituiti da asterischi e barre verticali o – equivalentemente – determinare tutti i modi in cui possiamo disporre quattro asterischi tra i sette oggetti costituiti da asterischi e barre verticali.

In termini matematici possiamo scrivere:

C(7,3) = C(7,4) = 7!/(3!4!) = 7!/(4!3!) = 35

dove C(n,k) indica le combinazioni di n oggetti presi a gruppi di k.

Passiamo ora al caso generale. Date n urne avremo d = n – 1 delimitatori. Quindi le configurazioni possibili sono:

C(n+d,d) = C(2n-1,n-1) = (2n – 1)!/((n – 1)!n!)

Nel caso sopra siamo partiti da una situazione di quattro schede con quattro urne e abbiamo derivato una formula generale nel caso di n schede e n urne; il metodo permette tuttavia un’ulteriore generalizzazione: quella di n schede e m urne. In tal caso la formula da applicare è la seguente:

C(n+m-1,m-1) = (n + m – 1)!/((m – 1)!n!)

Voci precedenti più vecchie