martedì 23 agosto 2016

Una proposta di ordinamento olimpico di Simon Tatham

Scrivo ancora qualcosa sulla classifica olimpica definitiva. Nel post precedente non c'era nessun tentativo di confronto fra i tipi di medaglie: uno stato che aveva ottenuto una sola medaglia d'oro non era confrontabile con un altro stato che aveva ottenuto un solo argento.

La proposta di Tatham, fatta otto anni fa, si basa invece sulle regole seguenti, che sono decisamente condivisibili:


  • Il numero di medaglie guadagnate conta, a parità di altri fattori: se uno stato X ha ottenuto almeno tanti ori, almeno tanti argenti e almeno tanti bronzi di quanti ne abbia ottenuto uno stato Y, allora i due stati sono almeno pari in classifica.
  • Oro è meglio di argento, argento è meglio di bronzo: se lo stato X ha ottenuto, ad esempio, un argento in più e un bronzo in meno rispetto allo stato Y, allora deve essere più in alto in classifica. Infatti Y, per ottenere lo stesso risultato di X, dovrebbe fare meglio in una specialità in cui ha vinto il bronzo e riuscire a ottenere l'argento.


Diciamo allora che uno stato X è stato migliore di un altro stato Y se il medagliere di Y può essere trasformato nel medagliere di X mediante una sequenza di aggiunte di medaglie oppure di sostituzione di medaglie basse con medaglie alte.

Il che si traduce nel seguente insieme di regole: se indichiamo con (O, A, B) il numero di ori, argenti e bronzi ottenuti da X, e con (o, a, b) il numero di ori, argenti e bronzi ottenuti da Y, allora X precede Y se e solo se


  • Oo,
  • O + Ao + a,
  • O + A + Bo + a + b.

Ed ecco il risultato:


Come di consueto, classifiche olimpiche

Anche quest'anno, così come avevo fatto in occasione delle olimpiadi di Londra, ho fatto un'immagine con la madre di tutte le classifiche olimpiche:


Le spiegazioni sono nel post di quattro anni fa.




Qui sotto, invece, la sequenza delle operazioni che ho eseguito per arrivare al grafico finale, in modo da non diventare matto di nuovo tra quattro anni.


  • Programmino python che legge il file in cui ho inserito il medagliere, copiato da wikipedia, e che produce un file scritto in linguaggio dot, digeribile dalla suite graphviz.
  • Uso del preprocessore tred per la riduzione transitiva (insomma, per togliere frecce inutili ottenibili mediante la proprietà transitiva).
  • Modifica manuale delle label troppo lunghe per farle andare a capo in maniera graficamente soddisfacente.
  • Uso del programma dot per produrre un file png.


giovedì 4 agosto 2016

I numeri di Catalan — 2. Percorsi particolari possono portare a ponderate persuasioni

Abbiamo visto come fare per calcolare quanti percorsi di minima lunghezza si possono fare su una griglia n × n, se si vuole andare da un vertice al vertice opposto”.

“Sì, è come calcolare gli anagrammi di una parola composta da tante lettere quante sono i passi che servono per fare il percorso, distinguendo tra passi verso destra e passi verso l'alto”.

“Bene, ora aggiungiamo una complicazione: partiamo dall'angolo in basso a sinistra, arriviamo all'angolo in alto a destra, e dobbiamo sempre stare al di sotto della diagonale del quadrato”.

“Uhm, fammi capire bene”.

“Ecco, per esempio questo è un percorso che non va bene:”.



“Ah, capisco, il terzo passo ci fa passare dall'altra parte della diagonale. Il secondo però arriva sulla diagonale, va bene lo stesso?”.

“Sì, l'importante è non andare al di là: possiamo stare sotto o, al massimo, toccare la diagonale”.

“Ok, quindi col giochino degli anagrammi si tratta di, uhm, considerare solo parole nelle quali le D non possono essere seguite da troppe A. Ehm, mi rendo conto di non averlo detto in maniera proprio precisa”.

“Infatti non è facile. Puoi dire che, presa una parola, ogni segmento iniziale non contiene più A che D, lasciando al lettore il compito di definire il concetto di segmento iniziale, anche se è abbastanza intuitivo”.

“Vabbé, mi pare abbastanza chiaro. Quello che non è chiaro è come fare il calcolo, ci sono troppe possibilità per analizzarle tutte”.

“Effettivamente è complicato. Ma, come ti dicevo, ho capito una dimostrazione che mi permette di ricordare una delle tante formule per il calcolo di questi possibili percorsi obbligati”.

“Interessante”.

“Provo a spiegarti, procedendo pian piano. Prima di tutto, dato un certo percorso P, come quello in figura, tanto per fissare le idee, chiamiamo elevazione di P il numero e(P) uguale al numero di tratti verticali che si trovano al di sopra della diagonale. I tratti possono anche partire dalla diagonale stessa”.

“Vediamo, fammi contare: nella figura che hai disegnato ci sono due tratti verticali, giusto?”.

“Giusto. In questo percorso, e(P) = 2”.

“Fin qua ci sono”.

“Ora definiamo una trasformazione che, dato un certo percorso, ne produce uno nuovo. Questa è un po' difficile da spiegare, quindi vado per passi. Ci sei?”.

“Vai”.

“Allora, per prima cosa seguiamo il percorso, partendo dal punto iniziale, fino a che non oltrepassa la diagonale”.

“Nel nostro esempio lo fa al terzo passo”.

“Esatto. Da questo momento andiamo avanti fino a identificare l'ultimo tratto, che sarà necessariamente orizzontale, che sta nella zona proibita. L'ultimo passo prima del primo rientro, insomma”.

“Perché è necessariamente orizzontale?”.

“Beh, perché un passo verticale si allontana dalla diagonale, non si può mai avvicinare”.

“Ah, ho capito, ok”.

“Bene, hai capito quindi qual è il passo che ci interessa, nel nostro esempio?”.

“Mi pare di sì, lo coloro di rosso:”.



“Ok. Ora spezziamo in tre parti il nostro percorso. La parte successiva alla freccia rossa viene spostata e messa all'inizio”.

“La devo proprio staccare?”.

“Sì, stiamo costruendo una nuova figura. La parte dopo la freccia rossa diventa la prima. Disegnata quella, si mette la freccia rossa, e successivamente tutta la parte precedente la freccia rossa. In sostanza, la parte in alto a destra va in basso a sinistra, quella in basso a sinistra va in alto a destra, e la freccia rossa le congiunge”.

“Provo, viene una cosa del genere?”.



“Esatto!”.

“La freccia rossa però non è rimasta ferma”.

“No, no, non doveva. La freccia rossa continua a separare i due pezzi, però si sposta. Ma prova a calcolare l'elevazione di questa nuova figura”.

“C'è una sola freccia verticale al di sopra della diagonale, ora l'elevazione è uguale a 1, quindi è diminuita”.

“Perfetto”.

“Succede sempre così?”.

“Prova a pensarci. La trasformazione che abbiamo definito spezza la figura in due parti. Sulla parte superiore non sappiamo niente, se non che essa parte dalla diagonale e che la sua ultima freccia termina anch'essa sulla diagonale, perché l'arrivo è fisso: è sempre il punto in alto a destra”.

“Giusto”.

“Quindi, facendo lo scambio dei due pezzi di percorso, siamo sicuri del fatto che il pezzo in alto a destra, che ora è finito in basso a sinistra, parte da un punto della diagonale e finisce in un punto della diagonale”.

“Vero”.

“Poi attacchiamo la freccia rossa, che ci fa fare uno spostamento verso destra”.

“Vero anche questo. Poi attacchiamo la prima parte, che è quella che avevamo analizzato in precedenza, e che sicuramente usciva dalla diagonale”.

“Esatto. E, spostandola di un passo verso destra, otteniamo come risultato il fatto che la prima freccia che usciva dalla diagonale ora sta sotto”.

“Ah! Ecco perché l'elevazione diminuisce sempre di uno! Perché in pratica riusciamo a fare rientrare una freccia. E una soltanto, perché il passo a destra è di un solo segmentino”.

“Benissimo. Ecco quindi che la nostra trasformazione, ogni volta che viene applicata, fa diminuire l'elevazione di 1”.

“Ma quindi se la applico una seconda volta, dovrei ottenere un percorso di quelli cercati, cioè un percorso di quelli che stanno sempre sotto la diagonale”.

“Certo. Prova! Prima di tutto, identifica il punto in cui spezzare”.

“Vediamo, devo seguire il percorso fino a che non esco, e poi devo colorare di rosso l'ultimo segmento orizzontale prima del rientro sulla diagonale. Mi viene una cosa del genere però:”.



“Va benissimo”.

“Ma il segmento rosso è l'ultimo!”.

“Non importa, applica la regola, funziona anche in questo caso”.

“Boh, allora, dovrei prendere il pezzo di percorso che segue la freccia rossa, ma non c'è”.

“Bene, mettilo al primo posto”.

“Ma non c'è!”.

“Quindi non metti niente, rimani fermo nell'angolo in basso a sinistra”.

“Ok. Poi devo mettere la freccia rossa, e poi la parte precedente, cioè tutto”.

“Quasi tutto, no? La freccia rossa l'hai già messa”.

“Quasi tutto, sì. Ecco qua: funziona!”.



“Come vedi l'elevazione è diventata uguale a 0, e quindi hai ottenuto uno dei percorsi validi”.

“Ok, fin qua ci sono”.

“Ora andiamo all'indietro. Dato un percorso, questo può essere sempre pensato come ottenuto dalla trasformazione di un altro percorso avente elevazione aumentata di uno?”.

“Ah, non ne ho idea”.

“Pensa al procedimento fatto e prova a vedere se riesci a invertirlo”.

“Allora, fino ad adesso abbiamo cercato il primo segmento orizzontale che termina sulla diagonale”.

“Giustissimo”.

“Che poi, nella trasformazione, diventa l'ultimo segmento orizzontale che parte dalla diagonale”.

“Benissimo, hai capito come funziona”.

“Ah, quindi per invertire il processo devo prendere l'ultimo segmento orizzontale che parte dalla diagonale e fare il contrario di quello che facevo prima”.

“Che è poi la stessa cosa, cioè devi invertire la parte sopra con la parte sotto”.

“Vediamo se ho capito. Riprendo la prima figura, quella con elevazione 2, e identifico l'ultimo segmento orizzontale che parte dalla diagonale:”.



“Bene”.

“Adesso inverto la parte superiore con l'inferiore. Vediamo, ho solo una freccia in su, poi metto la freccia rossa, poi tutto il resto. Ecco qua:”.


“Benissimo. Ti convince il fatto che questo percorso, di elevazione 3, diventa quello da cui siamo partiti applicando la solita trasformazione?”.

“Sì, funziona. Spezzo in corrispondenza della freccia rossa, e torno indietro. Ok, ci sono”.

“Quindi, se continuiamo ad andare indietro, possiamo arrivare ad avere un percorso con elevazione 5, sei d'accordo?”.

“Sì”.

“E quindi, riassumendo, il numero di percorsi con elevazione 5 è uguale al numero di percorsi con elevazione 4, al numero di percorsi con elevazione 3, e così via fino all'elevazione 0”.

“Aspetta, aspetta, perché sono uguali?”.

“Perché a ogni percorso di elevazione 0 ne corrisponde uno e uno solo di elevazione 1, e a ogni percorso di elevazione 1 ne corrisponde uno e uno solo di elevazione 2, e così via. Abbiamo detto che la nostra trasformazione è invertibile, cioè si può andare avanti e indietro, aumentando o diminuendo l'elevazione, in un unico modo”.

“Ok, ho capito”.

“Quindi, come concludiamo?”.

“Eh, se il numero di percorsi aventi una certa elevazione è sempre lo stesso, e se conoscessi quante elevazioni posso avere…”.

“Ma lo sai!”.

“Uh?”.

“Eh, al massimo di quanti passi puoi salire?”.

“Ah, ma certo, se la scacchiera è 5 × 5 al massimo posso salire di 5 passi. In una scacchiera n × n l'elevazione massima è n”.

“E la minima?”.

“Zero”.

“E quindi quante elevazioni puoi avere?”.

“In tutto sono + 1”.

“Bene, hai n + 1 gruppi, contenenti lo stesso numero di elementi, aventi elevazioni diverse. A te interessano soltanto quei percorsi aventi elevazione 0, quindi come puoi calcolarli?”.

“Prendo tutti i possibili percorsi e li divido per n + 1, facile”.

“Ed ecco quindi la formula:”.



“Uhh, questi sono i numeri di Catalan?”.

“Esatto”.

“Quindi nel nostro caso il numero di percorsi che si possono ottenere su una griglia di lato 5, in modo tale da stare sempre sotto la diagonale, sono… fammi fare i calcoli… 42”.

“Che è sempre un bel numero”.

“…”.

“Sono un po' tanti per disegnarli tutti, però. Ti faccio invece vedere tutta la casistica per una griglia più semplice, la 3 × 3”.

“Ok. Aspetta che faccio i conti… dovrebbe risultare 5”.

“Giusto. Primo gruppo, da elevazione 3 a elevazione 0. Ogni percorso si ottiene da quello che gli sta sopra applicando la nostra trasformazione. Naturalmente l'unico elemento accettabile è quello più in basso, quello con elevazione zero”.



“Ok, ho capito”.

“Secondo gruppo:”.



“Ok, ho controllato, anche qua tutto bene”.

“Terzo gruppo:”.



“Bene”.

“Quarto gruppo:”.



“Giusto anche questo, vai con l'ultimo”.

“Quinto e ultimo gruppo:”.



“Ahh, molto bene, ho capito. Ogni percorso con elevazione 0 è legato a un particolare percorso con elevazione 1, uno con elevazione 2, e così via”.

“Esattamente. Con n = 3 ci sono 6! / (3! × 3!) possibili percorsi, cioè 20. Li abbiamo raggruppati in cinque gruppi da 4 elementi ciascuno, un elemento per ogni possibile valore dell'elevazione”.

“Benissimo”.

“Sarebbe bello un disegno unico con una griglia di percorsi”.

“Sarebbe bello, ma il margine di questa pagina è troppo stretto per contenerla”.

“…”.






Grazie a Paul Gaborit di stackexchange per il codice LaTeX usato per tutte le figure. Senza sarei diventato matto.

mercoledì 3 agosto 2016

I numeri di Catalan — 1. Permutazioni e anagrammi

“Ho scoperto un metodo per ricordarmi una delle tante formule per il calcolo dei numeri di Catalan”.

“Ah, tu pensa che io non so nemmeno cosa siano, questi numeri”.

“Eh, ci sono tanti modi per definirli, tutti equivalenti. Ma forse è meglio prima parlare di anagrammi”.

“Eh?”.

“Sì, mescolamenti di lettere, prendi una parola e riordini le lettere in modo da ottenerne un'altra”.

“E cosa c'entra la matematica?”.

“In matematica si contano i modi che si hanno per mescolare le lettere, in modo da ottenere nuove parole”.

“Ah, ma queste parole devono avere significato?”.

“No, vogliamo contare i modi di mescolare le lettere in una parola, senza tener conto del significato delle nuove parole ottenute. In termini matematici, si dice che stiamo contando le permutazioni di n oggetti”.

“E come si fa questo calcolo?”.

“Ti faccio un esempio, supponi che la parola sia UNO”.

“Ok”.

“Per creare tutte le nuove parole, immagina di avere tre caselle vuote da riempire”.

“Va bene”.

“In quanti modi puoi riempire la prima casella?”.

“Direi tre, no? Ci posso mettere la U, oppure la N, oppure ancora la O”.

“Esatto. Ora, in quanti modi puoi riempire la seconda casella?”.

“Ancora tre, come prima”.

“Eh, no”.

“Perché?”.

“Perché una lettera è già stata usata per la prima casella”.

“Ah! Certo! Mi rimangono due lettere, posso riempire la seconda casella solo in due modi”.

“Molto bene. Quindi finora quanti anagrammi parziali hai fatto?”.

“Uhm, per ogni scelta della prima casella ne ho due per la seconda, quindi tre per due? Sei modi?”.

“Certo, non è nemmeno difficile scriverli tutti:”.

UN_
UO_
NU_
NO_
OU_
ON_

“Ah, vero. E vedo che mi rimane una sola possibilità per la terza casella, la lettera che non ho ancora scelto”.

“Esattamente, ecco i sei anagrammi:”.

UNO
UON
NUO
NOU
OUN
ONU

“Bene, ho capito”.

“Sapresti rifare il calcolo con quattro lettere?”.

“Direi di sì: 4 modi per la prima casella, 3 per la seconda, 2 per la terza, e 1 per l'ultima. Totale: 24”.

“Mi interessa di più la formula del risultato”.

“Ah. Allora la formula è questa: 4×3×2×1”.

“Ottimo. Con n elementi come diventa?”.

“Diventa una schifezza del genere: × (− 1) × (− 2) × … × 2 × 1”.

“Dato che è una schifezza, come dici tu, i Veri Matematici hanno inventato un simbolo apposta per questo tipo di moltiplicazione: si chiama fattoriale e si indica con il punto esclamativo:”.

n! = × (− 1) × (− 2) × … × 2 × 1

“Mh, mi pare di ricordare qualcosa dai tempi della scuola”.

“Eh, già. Ora, quanti sono gli anagrammi della parola MAMMA?”.

“Sono cinque lettere, quindi cinque fattoriale, aspetta che faccio il calcolo”.

“No, non è il risultato corretto”.

“Eh? Perché”.

“Ti rispondo con una domanda: quanti sono gli anagrammi della parola MMM?”.

“Non sono sei?”.

“Prova a scriverli”.

“Uhm, eh, no, non sono sei, non si possono mescolare tre lettere uguali”.

“Quindi?”.

“Quindi c'è un solo anagramma. Però con la parola MAMMA non so mica come fare”.

“Immagina per un momento che le lettere siano tutte diverse”.

“Ma non lo sono, come faccio? Cambio parola?”.

“In un certo senso, sì, fai così: considera la parola M1A1M2M3A2”.

“Gulp”.

“Ho solo numerato le lettere in modo da renderle distinguibili una dall'altra. Se non ti piacciono gli indici, puoi immaginare che le lettere abbiano colori diversi”.

“Ah, no, va bene anche così”.

“Ora, quanti anagrammi puoi fare con questa nuova parola?”.

“Dato che le lettere sono tutte diverse, sono cinque fattoriale, no?”.

“Esatto, 5!, che fa 120”.

“Però ci sono parole che sono uguali, se cancelliamo gli indici”.

“Per esempio?”.

“Beh, per esempio M1A1M2M3A2 e M2A1M1M3A2”.

“Bene. Proviamo a fare un po' di calcoli: quante parole diventano uguali se cancelliamo solo gli indici delle lettere M?”.

“Ci sono 3 lettere M, e se cancello, uhm…  non so”.

“Ti giro la domanda: quante parole diverse puoi fare mescolando soltanto le lettere M?”.

“Ce ne sono tre, se mescolo solo loro… ah, certo, 3!, cioè 6, come abbiamo visto prima”.

“Perfetto. E quante, invece, se mescoli soltanto le due lettere A?”.

“Beh, 2!, cioè 2”.

“Giusto. Quindi, tra tutti i 120 possibili modi che hai di mescolare quelle lettere, otterrai gruppi di parole che diventano uguali quando cancelli gli indici. In particolare, quando cancelli gli indici della M, avrai dei gruppi formati da 6 parole che diventano tutte uguali. Quando cancelli gli indici della A, avrai dei gruppi da 2”.

“Sì, quindi? Devo contare i gruppi?”.

“Proprio così”.

“Ancora non so come fare”.

“Ragiona al contrario: una singola parola, come per esempio MAMMA, crea un gruppo formato da molte parole, quando aggiungi gli indici”.

“Eh, ma quante?”.

“Tieni fisse le lettere, muovi soltanto gli indici”.

“Ah, ho 6 modi per muovere gli indici della M e 2 per quelli della A. Ho capito! Ho 6×2 parole uguali nel gruppo”.

“Proprio così: per convincerti, te le scrivo tutte:”.

M1A1M2M3A2
M1A2M2M3A1
M1A1M3M2A2
M1A2M3M2A1
M2A1M1M3A2
M2A2M1M3A1
M2A1M3M1A2
M2A2M3M1A1
M3A1M1M2A2
M3A2M1M2A1
M3A1M2M1A2
M3A2M2M1A1

“Ok, devo raggruppare le 120 parole in gruppi da 12, quindi ottengo 120/12, cioè 10 anagrammi diversi”.

“Giusto, eccoli qua:”.

MMMAA
MMAMA
MMAAM
MAMMA
MAMAM
MAAMM
AMMMA
AMMAM
AMAMM
AAMMM

“Va bene, ho capito”.

“In generale, la formula è quindi questa: conti tutte le lettere e ne calcoli il fattoriale, poi conti la numerosità dei gruppi di lettere che si ripetono, e dividi il risultato che hai ottenuto prima per il fattoriale di ognuna di queste numerosità”.

“Mh, sì, credo di aver capito”.

“Niente di meglio che fare un esempio: quanti sono gli anagrammi della parola MATEMATICA?”.

“Allora, ci sono 10 lettere, quindi 10!, però ci sono 2 lettere M, quindi devo dividere per 2!, ci sono 3 lettere A, quindi devo dividere per 3!, poi ci sono anche 2 lettere T, quindi divido ancora per 2!. Il calcolo è quindi 10!/(2! × 3! × 2!)”.

“Che fa 151200. Bene, quindi hai capito la regola per gli anagrammi. Ora, un problema. Data una griglia 5 × 5, quanti sono i percorsi minimi che puoi fare partendo dall'angolo in basso a sinistra e arrivando all'angolo in alto a destra?”.

“Eeeh?”.

“Una cosa del genere:”.




“Boh? Non ne ho idea”.

“Hai capito cosa significa percorsi minimi?”.

“Veramente no”.

“Sono i percorsi più corti possibile”.

“Ah. Quindi non posso tornare indietro, posso solo andare a destra o in alto”.

“Molto bene! Quanti passi in alto?”.

“Ah, al massimo 5”.

“No, non al massimo”.

“Oh, certo, esattamente cinque, vero. Devo andare verso l'alto cinque volte se voglio arrivare nella riga più in alto. So anche cosa stai per chiedermi: quanti passi verso destra? Anche quelli sono esattamente 5”.

“Perfetto. Il percorso nella figura là in alto, quindi, può essere riassunto da dieci istruzioni: vai a destra, vai in alto, vai in alto, vai in alto, vai a destra, vai a destra, vai in alto, vai a destra, vai a destra, vai in alto”.

“Sì, molto noioso, ma è giusto.”.

“Ti abbrevio le istruzioni in questo modo: DAAADDADDA”.

“Ahh, ma quindi un percorso è una parola, e contare tutti i percorsi significa contare tutte le parole di quel tipo!”.

“Proprio così. Quindi quanti sono questi percorsi?”.

“Una parola da 10 lettere, con 5 A e 5 D, quindi 10! / (5! × 5!), fa 252”.

“Perfetto. Ultima domanda: com'è la formula per una scacchiera × n?”.

“Vediamo: ci sono 2n lettere, e due gruppi da n elementi ciascuno, quindi (2n)! / (n! × n!)”.

“Benissimo. Per motivi che ora non ti dirò, perché aprono un altro mondo, quel numero si indica anche in questo modo:”.




“Ah”.

“Per quanto riguarda i calcoli, basta usare il tastino nCr della calcolatrice”.

“Bene, buono a sapersi. Quindi questi sono i numeri di Catalan?”.

“No, ancora no, questo è un argomento propedeutico”.

“Gulp”.