“Bene, dopo tutta questa introduzione possiamo finalmente parlare d'altro”.
“Ma come? Era un'introduzione?”.
“Sì, giusto per scaldarci un po'”.
“Ah. E di cosa parliamo?”.
“Di informazione”.
“Singolare?”.
“Sì, del concetto di informazione, di come si fa a misurarla”.
“Non sapevo che si misurasse. Ma cosa significa, poi, misurarla?”.
“L'idea è questa: abbiamo un dispositivo che immagazzina dati, oppure che può trasmetterli da una sorgente a una destinazione”.
“E fin qua è chiaro”.
“Chiamiamo messaggi i dati che vengono immagazzinati o trasmessi, così ci leghiamo al concetto di informazione. Che strada devo prendere al prossimo incrocio? Qual è il primo verso della Divina Commedia?”.
“Le risposte a queste domande sono i messaggi?”.
“Esatto. Mettiamoci poi nel caso in cui il numero di messaggi che un sistema può inviare (o conservare) sia un numero finito. La strada che devo prendere al prossimo incrocio è destra, sinistra, oppure dritto. Il primo verso della Divina Commedia è un messaggio composto da 35 lettere dell'alfabeto, che sono in numero finito, e così via”.
“Va bene”.
“Ora la domanda è: che numero possiamo prendere per misurare l'informazione prodotta quando viene scelto uno dei messaggi disponibili? Il messaggio vai diritto quanta informazione porta con sé? E il messaggio Nel mezzo del cammin di nostra vita?”.
“Non saprei proprio come risponderti”.
“Partiamo dal caso più semplice possibile: prendiamo come contenitore di messaggi, o come canale che trasmette i messaggi, una moneta”.
“Eh? Come una moneta?”.
“Una moneta parla: dice testa o croce. Permette di salvare, o trasmettere, due messaggi diversi. Come misuriamo la quantità di informazione che si produce quando selezioniamo testa o croce?”.
“Non so. Ancora non capisco di cosa stiamo parlando: come fa una moneta a essere il caso più semplice di tutti? Una moneta porta due messaggi: non si può pensare a un caso ancora più semplice in cui il messaggio è uno solo?”.
“Ma se il messaggio è uno solo, ti serve conoscerlo?”.
“Uh?”.
“L'idea che si vuole tradurre in linguaggio matematico è questa: tu non sai una cosa, poi ricevi un messaggio e la conosci. Quanto vale quel messaggio? Quanto pesa? Quanta informazione ti porta? Se sai già che il messaggio è uno solo…”.
“Non mi porta nessuna informazione! Perché io non conosca il messaggio, ce ne devono essere almeno due! Ecco perché la moneta è il caso più semplice”.
“Esatto. E nota che nel caso della moneta, la parola testa può anche essere abbreviata con una singola lettera, T, mentre se parli dei versi della Divina Commedia sapere che a un certo punto c'è una T invece di una C è una informazione più forte”.
“Vero: la parola Torre è diversa da Corre”.
“Non solo: in questo caso non hai solo due possibilità, cioè T o C, ma puoi anche avere altre lettere, e generare parole ancora diverse, come per esempio Porre. Inoltre, qui il messaggio T è diverso dal messaggio Testa, mentre nella moneta sono uguali”.
“Va bene, sto capendo qualcosa, ma ancora non saprei come misurare questa quantità di informazione, anche se ho capito che dipende dal contesto. Potremmo forse dire che la quantità di informazione dipende dai possibili messaggi?”.
“Sì, potremmo farlo. Potremmo dire che l'informazione T o C relativa al lancio della moneta vale 2, perché i casi sono solo due. Se invece stiamo parlando di lettere dell'alfabeto, la scelta di T o C vale di più”.
“Ci sono 26 possibilità, ammesso che Dante abbia usato anche le lettere straniere”.
“Nella Divina Commedia ci sono due J, un sacco di X che sono state usate per numerare i canti (ma non solo), e una Y. Non ho trovato delle W e delle K”.
“Quindi servono almeno 24 caratteri”.
“Senza contare tutti i segni di interpunzione e lo spazio, e senza fare differenza tra lettere maiuscole e lettere minuscole”.
“Oh già. Potremmo allora dire che l'informazione delle lettere dell'alfabeto usate per la Divina Commedia vale 24, senza contare tutto il resto?”.
“Potremmo, se la Divina Commedia fosse composta da un solo carattere”.
“Oh, già. Ma… allora l'informazione contenuta nella Divina Commedia è un numero enorme!”.
“Vorrei ben vedere, soprattutto se la paragoniamo al lancio di una moneta. Dante non sarebbe felice di sapere che ha prodotto poca informazione”.
“Sì, capisco, sarebbe un po' deludente”.
“Abbiamo detto, quindi, che per calcolare la quantità di informazione potremmo contare il numero di messaggi che un sistema può inviare. Ma non faremo così”.
“E perché?”.
“Perché useremmo una scala che non ci piace”.
“Mh. Come fa a non piacerci una cosa che definiamo noi?”.
“Te lo spiego con un esempio. Se una moneta produce informazione uguale a 2, secondo te quanta informazione produce una coppia di monete?”.
“Il doppio, no?”.
“Eh, il doppio, cioè 4”.
“Certo. Cosa c'è che non va?”.
“Come lo hai calcolato 4? Facendo 2+2 oppure 2×2?”.
“Cosa cambia? Fa comunque 4”.
“Il risultato non cambia, ma l'idea sì. Quanta informazione producono 3 monete?”.
“Sarà il triplo, no?”.
“Il triplo di 2 è 6”.
“Certo”.
“E allora qualcosa non torna: il numero di messaggi che si possono trasmettere con 3 monete non è 6”.
“Oh. È vero! Con 3 monete posso trasmettere 8 messaggi: TTT, TTC, TCT, TCC, CTT, CTC, CCT, CCC”.
“E quindi 4 era uguale a 2+2 oppure a 2×2?”.
“Era uguale a 2×2. Con 3 monete devo calcolare 23, con 4 invece 24, eccetera”.
“Quindi l'informazione prodotta da 3 monete non è il triplo dell'informazione prodotta da una moneta”.
“Eh, no. Purtroppo no. Capisco perché dici che non ci piace: io vorrei un modo di misurare questa informazione che mi permetta invece di dire che l'informazione prodotta dalla somma di tot monete è tot volte l'informazione prodotta da una moneta. Ma come si fa?”.
“Si fa, si fa. Ci sono i logaritmi apposta”.
“Ah! Se uso la base 2, con la moneta è facilissimo: una moneta ha informazione 1, due monete hanno informazione 2, eccetera”.
“Sì, è la scelta più naturale”.
“E possiamo dare un nome all'unità di misura? Una moneta ha informazione 1 cosa?”.
“Io direi che, per un po', potremmo continuare a chiamare questa unità di misura moneta. Anche se tutto il mondo la chiama bit”.
Visualizzazione post con etichetta combinatoria. Mostra tutti i post
Visualizzazione post con etichetta combinatoria. Mostra tutti i post
sabato 2 maggio 2020
lunedì 28 gennaio 2019
Il piccolo Fermat e i braccialetti
“Braccialetti?”.
“Braccialetti”.
“Cosa c'entrano i braccialetti con la matematica?”.
“I nostri braccialetti sono formati da perline colorate”.
“Ah, va bene. Quindi?”.
“Più precisamente: da un numero primo di perline colorate”.
“Uhm”.
“Chiamiamolo p, e per fare un esempio supponiamo che p sia uguale a 3”.
“Braccialetti con tre perline: una miseria”.
“Lo so, ma vorrei fare qualche disegnino, se aumentiamo il numero non finiamo più”.
“Ok, allora facciamo questi braccialetti con tre perline colorate. Ah, come le coloriamo?”.
“Con un certo numero di colori diversi, diciamo n colori diversi”.
“E anche in questo caso fissiamo un n di esempio?”.
“Sì, facciamo tre colori”.
“Uhm, non è che ci confondiamo tra n e p?”.
“Direi di no, perché faremo qualche schema: se indichiamo i colori con i numeri 1, 2 e 3, ci basta scrivere tre numeri per avere un braccialetto. Si dovrebbe distinguere bene tra il numero di cifre scritte e il fatto che le cifre vanno da 1 a 3”.
“Vediamo”.
“Allora, prima di rappresentare i braccialetti, risolviamo un problema più semplice: calcoliamo il numero di stringhe che si possono creare con tre perline colorate. Insomma, rispetto ai braccialetti qui abbiamo delle posizioni predefinite: una perlina può essere messa al primo posto, al secondo o al terzo. Nel caso dei braccialetti, invece, non esistono un primo, un secondo e un terzo posto, perché ogni posizione in cui compare la perlina è indistinguibile dalle altre”.
“A meno che non indichiamo anche dove si mette la fibbia di chiusura”.
“Esatto. Quella la nascondiamo, fabbrichiamo un braccialetto senza fibbia. Prima, però, le stringhe”.
“Forse riesco a calcolare le possibilità: ci sono tre posizioni, e in ogni posizione posso mettere uno dei tre colori. Quindi dovrei avere 3 possibilità per la prima posizione, 3 per la seconda e 3 anche per la terza. Totale: 27”.
“O, meglio, 33”.
“Va bene”.
“Eccole qua:”.
123
312
231
132
213
321
133
313
331
122
212
221
112
211
121
223
322
232
113
311
131
332
233
323
111
222
333
“Vedo”.
“Ora, le tre stringhe monocolori le mettiamo da parte”.
“Sono le ultime tre: perché le mettiamo da parte?”.
“Perché per loro servono conteggi diversi: dopo le recuperiamo. Per ora ragioniamo sulle prime 24”.
“Ok”.
“Trasformiamo ogni stringa in un braccialetto: ogni stringa può essere ruotata in tutti i modi possibili, e quindi ogni braccialetto può essere generato da più stringhe diverse”.
“Fammi capire meglio”.
“Le tre stringhe 123, 312 e 231 generano lo stesso braccialetto, perché non importa quale sia il punto di partenza”.
“Ah, hai ragione, l'importante è che 1 sia seguito da 2, 2 da 3 e 3 di nuovo da 1”.
“Esatto. Ora si tratta di contare i braccialetti”.
“Beh, è facile, li hai già raggruppati quando li hai elencati”.
“Sì, in questo esempio. Vorrei trovare una formula generale”.
“Ah”.
“Allora: noi possiamo prendere l'ultima perlina di una stringa, sfilarla dalla sua posizione e reinserirla all'inizio. Così facendo otteniamo una stringa diversa ma lo stesso braccialetto, giusto?”.
“Giusto”.
“Quante di queste alterazioni si possono fare prima che la stringa torni a essere uguale a com'era all'inizio?”.
“Direi 3, no? A parte le stringhe monocolore”.
“Non fissare le idee su questo esempio, che è solo un esempio. Come funziona in generale? Il numero di alterazioni possibili sarà sempre uguale al numero di palline?”.
“Pensavo di sì, dici di no?”.
“Guarda questo braccialetto composto da 6 perline:”.
121212
“Ah. Dopo il primo movimento diventa 212121 e dopo il secondo torna come prima”.
“Esattamente”.
“E allora come facciamo a calcolare questo numero di spostamenti?”.
“Bisogna pensare a qualche formuletta”.
“Era quello che temevo”.
“Non sarà difficile. Chiamiamo k il minimo numero di spostamenti di perline da fare perché il braccialetto torni uguale a com'era all'inizio”.
“Va bene. Ah, è per questo che hai messo da parte le stringhe monocromatiche?”.
“Molto bene! Per quelle k vale 1, naturalmente, perché sono sempre uguali a sé stesse.”.
“Ho capito, anche se avrei detto che per esse k dovrebbe essere 0 ”.
“Beh, 0 allora va bene per tutte, no? Tutte quante con 0 mosse diventano uguali a sé stesse”.
“Già, hai ragione. Quindi k deve essere positivo”.
“Bene. E, escludendo le stringhe monocromatiche, k deve essere maggiore di 1”.
“Giusto”.
“Ora, supponi di aver trovato un valore di k che funziona per una certa stringa: se essa diventa uguale a sé stessa dopo k mosse, lo farà anche dopo 2k mosse, dopo 3k mosse, e così via”.
“Mi pare ovvio”.
“Allora, facciamo questo calcolo: dividiamo il numero p di perline per k”.
“Non so quanto possa risultare”.
“Beh, vogliamo una formula, non un risultato esatto. Cosa significa che p diviso k dà quoziente h e resto r?”.
“Non ne ho assolutamente idea”.
“Ma sì, lo sai dalle elementari. La maestra non ti faceva fare la prova?”.
“Ah, sì, dovevo moltiplicare il quoziente per il divisore e aggiungere il resto”.
“Esatto: vale la formula p = hk + r”.
“Vabbé. Questo mi aiuta?”.
“Certo. Cosa mi dici di r?”.
“So che è il resto”.
“E il resto, in una divisione, può essere grande quanto si vuole?”.
“Eh, no, il resto è sempre più piccolo del divisore”.
“Perfetto: quindi r è un numero compreso tra 0 e k”.
“Però non può essere uguale a k, solo a 0, no?”.
“Certo. Ora, se prendiamo una stringa di lunghezza p e facciamo p spostamenti di perline, la stringa torna a essere uguale a sé stessa indipendentemente dal valore di p, sei d'accordo”.
“Ah, certo, sposto tutte le perline fino a che non tornano nella posizione iniziale”.
“Benissimo. E anche se faccio hk spostamenti la stringa torna a essere uguale a sé stessa”.
“Perché?”.
“L'abbiamo detto prima: k è proprio quel numero di spostamenti da fare perché la stringa non cambi, e se ne puoi fare k ne puoi anche fare 2k, 3k, eccetera. Anche hk”.
“Ah, ok.”.
“Ora riprendiamo l'uguaglianza che definisce la divisione: p = hk + r. Questa ci dice che se prendiamo una stringa e facciamo hk spostamenti, questa diventa uguale a com'era all'inizio. Se poi ne facciamo altri r, in tutto ne abbiamo fatti hk + r, cioè p. Questo significa che di nuovo la stringa ritorna com'era all'inizio”.
“Giusto”.
“Mica tanto giusto, perché questo significherebbe che ci bastano r spostamenti per riportare la stringa alla posizione iniziale”.
“E perché non è possibile?”.
“Perché il resto di una divisione è minore del divisore: r è minore di k”.
“Vabbé, r sarà minore di k, qual è il problema?”.
“Il problema è che k dovrebbe essere il numero minimo di spostamenti da fare, e invece così facendo avremmo trovato un numero ancora più piccolo”.
“Ah. Allora c'è qualcosa di sbagliato nel ragionamento?”.
“No, c'è un'unica conclusione coerente con tutto quanto abbiamo detto: r deve essere 0”.
“Ah! Allora p è multiplo di k, e tutto torna”.
“Giusto. E cosa potremmo dire se p fosse un numero primo?”.
“O k è uguale a 1…”.
“Questo vorrebbe dire che le stringhe sono monocromatiche”.
“Giusto, e noi l'abbiamo escluso. Allora k e p devono essere uguali”.
“Ottimo. Riassumendo: avevamo p perline di n colori diversi, con le quali abbiamo costruito np stringhe diverse”.
“Poi abbiamo tolto tutte le stringhe monocolori, che sono tante quante i colori, cioè n”.
“E quindi sono rimaste np − n stringhe. E ci siamo chiesti quante di queste generano braccialetti uguali”.
“Uhm, abbiamo detto che potevamo raggrupparle k alla volta. Ah, k è p, quindi possiamo raggrupparle a gruppi di p”.
“Ed ecco il risultato, quindi: il numero di stringhe, escluse quelle monocromatiche, è divisibile per p”.
“Questo è un teorema? np − n è divisibile per p?”.
“Sì, si chiama piccolo teorema di Fermat, e ne avevamo già parlato, in altri termini”.
“Braccialetti”.
“Cosa c'entrano i braccialetti con la matematica?”.
“I nostri braccialetti sono formati da perline colorate”.
“Ah, va bene. Quindi?”.
“Più precisamente: da un numero primo di perline colorate”.
“Uhm”.
“Chiamiamolo p, e per fare un esempio supponiamo che p sia uguale a 3”.
“Braccialetti con tre perline: una miseria”.
“Lo so, ma vorrei fare qualche disegnino, se aumentiamo il numero non finiamo più”.
“Ok, allora facciamo questi braccialetti con tre perline colorate. Ah, come le coloriamo?”.
“Con un certo numero di colori diversi, diciamo n colori diversi”.
“E anche in questo caso fissiamo un n di esempio?”.
“Sì, facciamo tre colori”.
“Uhm, non è che ci confondiamo tra n e p?”.
“Direi di no, perché faremo qualche schema: se indichiamo i colori con i numeri 1, 2 e 3, ci basta scrivere tre numeri per avere un braccialetto. Si dovrebbe distinguere bene tra il numero di cifre scritte e il fatto che le cifre vanno da 1 a 3”.
“Vediamo”.
“Allora, prima di rappresentare i braccialetti, risolviamo un problema più semplice: calcoliamo il numero di stringhe che si possono creare con tre perline colorate. Insomma, rispetto ai braccialetti qui abbiamo delle posizioni predefinite: una perlina può essere messa al primo posto, al secondo o al terzo. Nel caso dei braccialetti, invece, non esistono un primo, un secondo e un terzo posto, perché ogni posizione in cui compare la perlina è indistinguibile dalle altre”.
“A meno che non indichiamo anche dove si mette la fibbia di chiusura”.
“Esatto. Quella la nascondiamo, fabbrichiamo un braccialetto senza fibbia. Prima, però, le stringhe”.
“Forse riesco a calcolare le possibilità: ci sono tre posizioni, e in ogni posizione posso mettere uno dei tre colori. Quindi dovrei avere 3 possibilità per la prima posizione, 3 per la seconda e 3 anche per la terza. Totale: 27”.
“O, meglio, 33”.
“Va bene”.
“Eccole qua:”.
123
312
231
132
213
321
133
313
331
122
212
221
112
211
121
223
322
232
113
311
131
332
233
323
111
222
333
“Vedo”.
“Ora, le tre stringhe monocolori le mettiamo da parte”.
“Sono le ultime tre: perché le mettiamo da parte?”.
“Perché per loro servono conteggi diversi: dopo le recuperiamo. Per ora ragioniamo sulle prime 24”.
“Ok”.
“Trasformiamo ogni stringa in un braccialetto: ogni stringa può essere ruotata in tutti i modi possibili, e quindi ogni braccialetto può essere generato da più stringhe diverse”.
“Fammi capire meglio”.
“Le tre stringhe 123, 312 e 231 generano lo stesso braccialetto, perché non importa quale sia il punto di partenza”.
“Ah, hai ragione, l'importante è che 1 sia seguito da 2, 2 da 3 e 3 di nuovo da 1”.
“Esatto. Ora si tratta di contare i braccialetti”.
“Beh, è facile, li hai già raggruppati quando li hai elencati”.
“Sì, in questo esempio. Vorrei trovare una formula generale”.
“Ah”.
“Allora: noi possiamo prendere l'ultima perlina di una stringa, sfilarla dalla sua posizione e reinserirla all'inizio. Così facendo otteniamo una stringa diversa ma lo stesso braccialetto, giusto?”.
“Giusto”.
“Quante di queste alterazioni si possono fare prima che la stringa torni a essere uguale a com'era all'inizio?”.
“Direi 3, no? A parte le stringhe monocolore”.
“Non fissare le idee su questo esempio, che è solo un esempio. Come funziona in generale? Il numero di alterazioni possibili sarà sempre uguale al numero di palline?”.
“Pensavo di sì, dici di no?”.
“Guarda questo braccialetto composto da 6 perline:”.
121212
“Ah. Dopo il primo movimento diventa 212121 e dopo il secondo torna come prima”.
“Esattamente”.
“E allora come facciamo a calcolare questo numero di spostamenti?”.
“Bisogna pensare a qualche formuletta”.
“Era quello che temevo”.
“Non sarà difficile. Chiamiamo k il minimo numero di spostamenti di perline da fare perché il braccialetto torni uguale a com'era all'inizio”.
“Va bene. Ah, è per questo che hai messo da parte le stringhe monocromatiche?”.
“Molto bene! Per quelle k vale 1, naturalmente, perché sono sempre uguali a sé stesse.”.
“Ho capito, anche se avrei detto che per esse k dovrebbe essere 0 ”.
“Beh, 0 allora va bene per tutte, no? Tutte quante con 0 mosse diventano uguali a sé stesse”.
“Già, hai ragione. Quindi k deve essere positivo”.
“Bene. E, escludendo le stringhe monocromatiche, k deve essere maggiore di 1”.
“Giusto”.
“Ora, supponi di aver trovato un valore di k che funziona per una certa stringa: se essa diventa uguale a sé stessa dopo k mosse, lo farà anche dopo 2k mosse, dopo 3k mosse, e così via”.
“Mi pare ovvio”.
“Allora, facciamo questo calcolo: dividiamo il numero p di perline per k”.
“Non so quanto possa risultare”.
“Beh, vogliamo una formula, non un risultato esatto. Cosa significa che p diviso k dà quoziente h e resto r?”.
“Non ne ho assolutamente idea”.
“Ma sì, lo sai dalle elementari. La maestra non ti faceva fare la prova?”.
“Ah, sì, dovevo moltiplicare il quoziente per il divisore e aggiungere il resto”.
“Esatto: vale la formula p = hk + r”.
“Vabbé. Questo mi aiuta?”.
“Certo. Cosa mi dici di r?”.
“So che è il resto”.
“E il resto, in una divisione, può essere grande quanto si vuole?”.
“Eh, no, il resto è sempre più piccolo del divisore”.
“Perfetto: quindi r è un numero compreso tra 0 e k”.
“Però non può essere uguale a k, solo a 0, no?”.
“Certo. Ora, se prendiamo una stringa di lunghezza p e facciamo p spostamenti di perline, la stringa torna a essere uguale a sé stessa indipendentemente dal valore di p, sei d'accordo”.
“Ah, certo, sposto tutte le perline fino a che non tornano nella posizione iniziale”.
“Benissimo. E anche se faccio hk spostamenti la stringa torna a essere uguale a sé stessa”.
“Perché?”.
“L'abbiamo detto prima: k è proprio quel numero di spostamenti da fare perché la stringa non cambi, e se ne puoi fare k ne puoi anche fare 2k, 3k, eccetera. Anche hk”.
“Ah, ok.”.
“Ora riprendiamo l'uguaglianza che definisce la divisione: p = hk + r. Questa ci dice che se prendiamo una stringa e facciamo hk spostamenti, questa diventa uguale a com'era all'inizio. Se poi ne facciamo altri r, in tutto ne abbiamo fatti hk + r, cioè p. Questo significa che di nuovo la stringa ritorna com'era all'inizio”.
“Giusto”.
“Mica tanto giusto, perché questo significherebbe che ci bastano r spostamenti per riportare la stringa alla posizione iniziale”.
“E perché non è possibile?”.
“Perché il resto di una divisione è minore del divisore: r è minore di k”.
“Vabbé, r sarà minore di k, qual è il problema?”.
“Il problema è che k dovrebbe essere il numero minimo di spostamenti da fare, e invece così facendo avremmo trovato un numero ancora più piccolo”.
“Ah. Allora c'è qualcosa di sbagliato nel ragionamento?”.
“No, c'è un'unica conclusione coerente con tutto quanto abbiamo detto: r deve essere 0”.
“Ah! Allora p è multiplo di k, e tutto torna”.
“Giusto. E cosa potremmo dire se p fosse un numero primo?”.
“O k è uguale a 1…”.
“Questo vorrebbe dire che le stringhe sono monocromatiche”.
“Giusto, e noi l'abbiamo escluso. Allora k e p devono essere uguali”.
“Ottimo. Riassumendo: avevamo p perline di n colori diversi, con le quali abbiamo costruito np stringhe diverse”.
“Poi abbiamo tolto tutte le stringhe monocolori, che sono tante quante i colori, cioè n”.
“E quindi sono rimaste np − n stringhe. E ci siamo chiesti quante di queste generano braccialetti uguali”.
“Uhm, abbiamo detto che potevamo raggrupparle k alla volta. Ah, k è p, quindi possiamo raggrupparle a gruppi di p”.
“Ed ecco il risultato, quindi: il numero di stringhe, escluse quelle monocromatiche, è divisibile per p”.
“Questo è un teorema? np − n è divisibile per p?”.
“Sì, si chiama piccolo teorema di Fermat, e ne avevamo già parlato, in altri termini”.
giovedì 8 dicembre 2016
La formula del piccolo Gauss senza parole
“Uh, bello, hai fatto l'albero di Natale?”.
“…”.
“Ah, non volevi fare l'albero di Natale”.
“Vedi tu”.
“Allora cos'è?”.
“È una dimostrazione senza parole della formula del piccolo Gauss”.
“Oh, mamma, ancora con questa storia, ma la sanno già tutti!”.
“Ti ricordi anche cosa dice?”.
“Ehm, dice che per calcolare la somma dei primi numeri naturali mi basta moltiplicare l'ultimo numero per il successivo e dividere tutto per due”.
“Sai anche perché?”.
“Mh, ecco, forse no”.
“Una dimostrazione semplice è questa: se vogliamo provare a calcolare la somma dei numeri da 1 a 100, possiamo scriverli due volte in fila, una sopra all'altra; nella prima fila mettiamo i numeri in ordine crescente, nella seconda in ordine decrescente, così:”.
1 + 2 + 3 + ... + 98 + 99 + 100 100 + 99 + 98 + ... + 3 + 2 + 1
“E perché facciamo così?”.
“Prova a sommare le varie colonne”.
“Allora, dalla prima risulta 1 + 100 che fa 101, dalla seconda 2 + 99 che fa ancora 101… ehi, risulta sempre 101!”.
“Esatto. E quante colonne hai?”.
“Sono 100”.
“E quindi la somma totale è uguale a 100×101”.
“Ah! E siccome ho contato tutto due volte, la somma dei numeri da 1 a 100 è uguale alla metà di 100×101, cioè 5050”.
“Esatto. E se invece di arrivare fino a 100 vuoi arrivare fino a n?”.
“In questo caso ho n colonne la cui somma è n + 1. Quindi la somma dei numeri che stanno in una singola fila è uguale a n(n + 1)/2”.
“E questa è la famosa formula del piccolo Gauss.”.
“E quindi? Cosa c'entra la figura con l'albero di Natale?”.
“Ora te la spiego. Osserva i cerchi gialli: nella prima fila ne hai uno solo”.
“Nella seconda fila ce ne sono due”.
“Nella terza tre”.
“Eh, va bene, in ogni fila ce n'è uno in più”.
“Ok, tu vuoi sommarli”.
“Ah! La somma dei primi numeri interi vista sotto forma di triangolo”.
“Proprio così, infatti i numeri come 1, 1 + 2, 1 + 2 + 3, eccetera, vengono proprio chiamati numeri triangolari”.
“Ah. E i dischi che si accendono? E i collegamenti con l'ultima fila?”.
“Dimmi se sei d'accordo su questa affermazione: a ogni disco giallo è associata un'unica coppia di dischi blu e, viceversa, a ogni coppia di dischi blu è associato un unico disco giallo”.
“Fammi vedere bene la figura, uhm. Ah, ora capisco perché vengono evidenziati quei collegamenti, servono per mostrare la tua affermazione!”.
“Infatti. Da ogni disco giallo puoi tracciare due collegamenti, uno che va verso sinistra e un altro che va verso destra: entrambi finiscono su due dischi blu. L'accoppiamento disco giallo-coppia di dischi blu è unico”.
“È come se io associassi un sistema di coordinate ai dischi gialli?”.
“Benissimo! È esattamente così: puoi numerare i dischi blu con i numeri da 1 a 7, e ogni disco giallo è caratterizzato da una coppia di quei numeri. Per esempio, il disco più in alto corrisponde a (1,7).”.
“Vediamo se ho capito: i dischi della seconda fila sono (1,6) e (2,7), quelli della terza sono (1,5), (2,6) e (3,7), giusto?”.
“Esatto. L'unica differenza, rispetto ai sistemi di coordinate a cui siamo abituati, è che qui non conta l'ordine in cui disponi le due coordinate. Per esempio, le coppie di dischi blu (1,5) e (5,1) identificano lo stesso disco giallo”.
“Giusto, sono d'accordo. Non ho capito però cosa abbiamo dimostrato?”.
“Che la somma dei dischi gialli corrisponde al numero degli accoppiamenti dei dischi blu”.
“Ah. E quanti sono?”.
“Hai 7 dischi, ne vuoi scegliere 2. In quanti modi puoi farlo?”.
“Mi sembra semplice: ho 7 scelte per il primo disco e 6 per il secondo, totale 6×7 = 42, che è sempre un bel numero”.
“Però, così facendo, li conti due volte”.
“Perché?”.
“Perché, appunto, non distingui tra (1,5) e (5,1). In generale, non distingui tra (a,b) e (b,a)”.
“E quindi devo dividere per due il mio calcolo. Ci sono quindi 21 modi di accoppiare due dischi blu”.
“E quindi ci sono 21 dischi gialli”.
“Vediamo, la formula per la somma dei numeri da 1 a 6 dice che devo fare 6×7/2… ehi, è lo stesso calcolo fatto adesso con gli accoppiamenti”.
“Eh, certo.”.
“Ehm, già, sennò non sarebbe una dimostrazione”.
“Eh. Ora, generalizza: vuoi sommare n file di dischi”.
“Quindi voglio calcolare la somma dei numeri da 1 a n”.
“Quanti dischi blu ti servono?”.
“Uno in più, cioè n + 1”.
“E quanti accoppiamenti puoi fare?”.
“Ho n + 1 scelte per il primo disco blu, n per il secondo, però devo dividere tutto per 2 perché non conta l'ordine con cui li prendo”.
“Quanto viene?”.
“(n + 1)n/2”.
“Ed ecco la formula del piccolo Gauss”.
“Fatta con l'albero di Natale”.
“Santo cielo”.
domenica 6 novembre 2016
L'identità del bastone da hockey
“Tutti conoscono il triangolo di Tartaglia”.
“Tutti”.
“Oh, insomma, tanti… Mai visto uno schema del genere?”.
“Mh, sì, l'ho visto. Ogni numero si ottiene sommando i due numeri che si trovano sopra di lui”.
“Esatto. Sul contorno si mettono degli 1, e poi si segue la regola che dici tu. Questo schema si chiama triangolo di Tartaglia e ha un sacco di proprietà. Oggi ci concentriamo su una di queste: l'identità del bastone da hockey”.
“Bel nome. Cosa c'entra poi l'hockey?”.
“Assolutamente niente”.
“Benissimo”.
“Ma vedrai cosa c'entra il bastone da hockey tra un po'. Scegli una casella del triangolo, abbastanza in basso”.
“Ok, scelgo 126”.
“Ora, il numero che hai scelto è uguale alla somma dei due numeri che gli stanno sopra”.
“Vero, 126 = 56 + 70”.
“Bene, ecco una figura: la somma dei due numeri azzurri è uguale al numero rosso”.
“Fin qua ci sono”.
“A loro volta, i due numeri che hai indicato sono ottenuti dalla somma di altri numeri: concentriamoci sul 56”.
“56 è la somma di 21 + 35”.
“Bene. A questo punto possiamo dire che il tuo 126 è uguale alla somma di 70 + 21 + 35. Riassumo questo risultato con un'altra figura: la somma dei numeri nelle caselle azzurre è uguale al numero scritto nella casella rossa”.
“Ah, certo”.
“E ora continua con lo stesso procedimento: il 21 a cosa è uguale?”.
“Alla somma di 6 + 15”.
“Ecco la figura aggiornata:”.
“Uh, capisco dove vuoi arrivare. Ogni numero a sinistra viene scomposto nella somma dei due numeri che gli stanno sopra”.
“Proprio così, fino a che non arrivo alla fine”.
“Vedo. E adesso?”.
“Bé, faccio un ultimo passo: invece di evidenziare quel numero 1 che sta a sinistra di 5, evidenzio quello più in alto”.
“Ok”.
“Ed ecco il bastone da hockey”.
“L'insieme delle caselle evidenziate?”.
“Certo, vedi come assomiglia a un bastone da hockey?”.
“Roba da matti”.
“Ma come, non apprezzi la capacità dei Veri Matematici di dare nomi divertenti alle cose?”.
“Ah, guarda, divertentissimi”.
“Almeno serve a qualcosa, questo bastone da hockey?”.
“Direi di no, se non a fare giochi matematici”.
“Benissimo. Sai cosa ti dico?”.
“Cosa?”.
“Che nel dare nomi divertenti alle cose, quelli imbattibili sono i fisici”.
“Tutti”.
“Oh, insomma, tanti… Mai visto uno schema del genere?”.
“Mh, sì, l'ho visto. Ogni numero si ottiene sommando i due numeri che si trovano sopra di lui”.
“Esatto. Sul contorno si mettono degli 1, e poi si segue la regola che dici tu. Questo schema si chiama triangolo di Tartaglia e ha un sacco di proprietà. Oggi ci concentriamo su una di queste: l'identità del bastone da hockey”.
“Bel nome. Cosa c'entra poi l'hockey?”.
“Assolutamente niente”.
“Benissimo”.
“Ma vedrai cosa c'entra il bastone da hockey tra un po'. Scegli una casella del triangolo, abbastanza in basso”.
“Ok, scelgo 126”.
“Ora, il numero che hai scelto è uguale alla somma dei due numeri che gli stanno sopra”.
“Vero, 126 = 56 + 70”.
“Bene, ecco una figura: la somma dei due numeri azzurri è uguale al numero rosso”.
“Fin qua ci sono”.
“A loro volta, i due numeri che hai indicato sono ottenuti dalla somma di altri numeri: concentriamoci sul 56”.
“56 è la somma di 21 + 35”.
“Bene. A questo punto possiamo dire che il tuo 126 è uguale alla somma di 70 + 21 + 35. Riassumo questo risultato con un'altra figura: la somma dei numeri nelle caselle azzurre è uguale al numero scritto nella casella rossa”.
“Ah, certo”.
“E ora continua con lo stesso procedimento: il 21 a cosa è uguale?”.
“Alla somma di 6 + 15”.
“Ecco la figura aggiornata:”.
“Uh, capisco dove vuoi arrivare. Ogni numero a sinistra viene scomposto nella somma dei due numeri che gli stanno sopra”.
“Proprio così, fino a che non arrivo alla fine”.
“Vedo. E adesso?”.
“Bé, faccio un ultimo passo: invece di evidenziare quel numero 1 che sta a sinistra di 5, evidenzio quello più in alto”.
“Ok”.
“Ed ecco il bastone da hockey”.
“L'insieme delle caselle evidenziate?”.
“Certo, vedi come assomiglia a un bastone da hockey?”.
“Roba da matti”.
“Ma come, non apprezzi la capacità dei Veri Matematici di dare nomi divertenti alle cose?”.
“Ah, guarda, divertentissimi”.
“Almeno serve a qualcosa, questo bastone da hockey?”.
“Direi di no, se non a fare giochi matematici”.
“Benissimo. Sai cosa ti dico?”.
“Cosa?”.
“Che nel dare nomi divertenti alle cose, quelli imbattibili sono i fisici”.
giovedì 6 ottobre 2016
Sconvolgimenti
“Jacopo ha appena finito di imbustare le ultime lettere che ha scritto e si sta accingendo a scrivere gli indirizzi. Ma il suo gatto è molto giocherellone e, mentre Jacopo apre il cassetto, la belva salta sulla scrivania, Jacopo si spaventa, la mano gli scivola, perde l'equilibrio, si sbraccia e, sbam, colpisce inavvertitamente la pila delle buste e la scaraventa in aria.
Scocciatissimo, si alza dalla sedia, le raccoglie, e le rimette sulla scrivania. Ma ha un problema: ha perso l'ordine.
Che fare? Aprire nuovamente tutte le buste, vedere a chi sono indirizzate le lettere, e scrivere gli indirizzi? Una noia mortale. No: Jacopo piuttosto si affida al caso. Prende una busta, e ci scrive sopra il primo indirizzo della sua lista. Prende una seconda busta, e via col secondo indirizzo. E prosegue così fino alla fine.“
“Chissà quanti errori ha fatto.”
“Gli è andata male, in effetti: ha fatto il massimo numero di errori
possibile.”
“Ma dai, non ha beccato nemmeno un indirizzo?”
“No, nessuna lettera ha l'indirizzo giusto.”
“Non è possibile, è stato sfortunatissimo.”
“Chissà. Bisognerebbe fare i conti.”
“Oh, no, dai, un problema anche qui?”
“Eh, la vita è fatta di problemi.”
“...”
“Questo è un problema di dismutazioni.”
“Di cosa?.”
“Dismutazioni, o sconvolgimenti. Sono le permutazioni senza punti fissi.“
“Quelle in cui mescolo tutto?”
“Esatto. Quelle in cui nessun elemento rimane al suo posto.”
“Io so calcolare le permutazioni, ma queste sono casi particolari che non saprei gestire.”
“Eh, non è facile calcolarle, infatti. Il modo più bello per farlo è scrivere una formula ricorsiva.”
“Ah, certo, formula ricorsiva, bellissima, certo, certo.”
“Noto dell'ironia.”
“Daai?”
“Il concetto di funzione ricorsiva è la quintessenza dello spirito matematico. È il cercare di ottenere il massimo rendimento con il minimo sforzo, è il non fare fatica inutile, è lo stare seduti lungo la sponda di un fiume, allungare la mano e pescare il pesce, e scoprire che è già cotto e pulito.”
“Ok, va bene, rinuncio. Vediamo questa fantomatica formula.”
“L'idea è questa: supponiamo di avere 10 caselle numerate da 1 a 10 e riempite con i numeri da 1 a 10, e di mescolare il tutto in modo tale che in nessuna casella cada il numero corrispondente.”
“Cioè nella casella 1 non cade il numero 1, nella casella 2 non cade il numero 2, eccetera?”
“Esatto. Vogliamo contare in quanti modi possibili si possa realizzare una situazione di questo tipo”.
“E come si fa?”
“Si comincia a guardare la prima casella. Cosa c'è dentro?”
“Ah, boh? Certamente non c'è il numero 1.”
“Bene: cosa ci mettiamo? Scegli.”
“Ah, non saprei. Diciamo che ci sia il numero 7?”
“Va bene, nella prima casella c'è il numero 7. Ora andiamo nella casella numero 7: cosa contiene?”
“Certamente non contiene il numero 7, no?”
“Esatto. Ora la domanda è: contiene 1?”
“Beh, potrebbe contenerlo oppure no.”
“E allora facciamo due casi. O 1 è contenuto nella casella 7 oppure no.”
“E questi due casi a cosa ci servono?”
“Analizziamoli. Primo caso: la casella 1 contiene 7 e la casella 7 contiene 1.”
“Ok. Quindi?”
“Quindi abbiamo già sistemato i due numeri 1 e 7, ora dobbiamo risolvere un problema analogo al precedente, con una importante differenza: se prima avevamo a che fare con 10 elementi, ora ne abbiamo 8. Un problema più semplice.”
“Mh, vabbé, ma se non sapevo risolvere quello di prima non so nemmeno risolvere questo.”
“Fammi finire: c'è anche il caso 2: la casella 1 contiene 7 ma la casella 7 non contiene 1.”
“Ok, conterrà qualcos'altro.”
“Certo. Vogliamo capire se si tratta di un problema già risolto in precedenza.”
“Mh, credo di aver capito a cosa ti riferisci: prima abbiamo ricondotto il problema al caso di 8 elementi. Ma adesso?”
“Adesso dobbiamo riempire le caselle da 2 a 10…”
“Quindi abbiamo 9 caselle.”
“E in ognuna di esse non possiamo mettere un numero.”
“Aspetta, perché? Cioè, ho capito che nella casella 2 non posso mettere 2, nella 3 non posso mettere 3, eccetera. Ma nella 7? Il 7 è già stato usato per riempire la 1, quindi quale numero non posso mettere dentro alla casella 7?”
“Ricordati che siamo nel secondo caso: la casella 7 non contiene 1.”
“Ah, ma certo, altrimenti cado nel primo caso che ho già studiato.”
“Esatto. Quindi, praticamente, in questo secondo caso ti sei ricondotto al problema con 9 buste.”
“Giusto.”
“Per concludere: ricorda che siamo partiti da un esempio: abbiamo detto che dentro alla casella 1 è contenuto il 7. Ma 7 è stato scelto a caso.”
“Certo, l'ho scelto io.”
“E quante scelte avevi?”
“Dieci?”
“No, non dieci: nella casella 1 è vietato mettere il numero 1.”
“Allora ho 9 scelte. Quindi il calcolo che stiamo facendo va moltiplicato per 9.”
“Perfetto. A questo punto è fatta la formula ricorsiva: il numero di dismutazioni di 10 elementi lo puoi calcolare sommando il numero di dismutazioni di 8 elementi più quello di 9 elementi, e moltiplicando il risultato per 9.”
“Ma io non so calcolare il numero di dismutazioni di 8 elementi! E nemmeno quello di 9!”
“Ed ecco la magia della ricorsività: ha qualcosa di speciale il numero 10?”
“Eh, uhm, no, direi di no, l'hai scelto tu come esempio, suppongo.”
“Esatto, quindi in realtà io potrei scrivere una formula ricorsiva generica, per il calcolo delle dismutazioni di n elementi.”
“Penso di sì. Anzi, forse ci riesco anche io: posso indicarle con D(n)?”
“Certo.”
“Allora la formula dovrebbe essere questa: il numero di dismutazioni di n elementi, D(n), è uguale a quello di n−1 elementi, cioè D(n−1), sommato a quello di n−2 elementi, cioè D(n−2), il tutto moltiplicato per n−1.”
“Molto bene! La formula è esattamente questa: D(n) = (n−1)(D(n−1) + D(n−2)).”
“Questo ancora non mi aiuta. Se io non so calcolare D(8) e D(9) non mi muovo.”
“Puoi muoverti invece, andando all'indietro. Sai calcolare D(8)?”
“Ho detto di no!”
“Hai detto male: secondo la tua formula, D(8) = 7(D(7) + D(6)).”
“Ma così si complica ancora di più! Non so calcolare niente!”
“Invece no: se continui ad andare indietro, arrivi a calcoli molto facili che puoi ottenere immediatamente.”
“Ah.”
“Per esempio, quanto vale D(1)?”
“Dismutazioni con 1 elemento? Ma si può fare? Un solo elemento non si permuta, rimane fermo al suo posto!”
“Certo, e quindi quante sono le dismutazioni di 1 elemento?”
“Non esistono. Ah, ho capito, sono i giochini che fate voi Veri Matematici con lo zero… Dato che non esistono, dico che il loro numero è 0”
“Bene, vedo che ti stai abituando alla mentalità matematica. Adesso: quanto vale D(2)?”
“Vediamo: con 2 elementi posso fare solo due cose. O li lascio fermi, e non ho una dismutazione, o li scambio tra loro, e questa volta ho una dismutazione. Quindi D(2) = 1”
“Ottimo, ecco fatto. Ora puoi calcolare tutto, basta usare la formula ricorsiva tante volte fino a che non arrivi a dover calcolare D(1) e D(2)”
“Ahh, molto bene!”
“Ecco i risultati:”
“Quindi, volendo rispondere alla mia domanda iniziale, cioè se è stato un caso sfortunato oppure no, dovrei calcolarmi il rapporto tra queste dismutazioni e tutte le possibili permutazioni di 10 elementi”
“Che sono 10 fattoriale, cioè 3628800.”
“Il rapporto risulta circa 0.37, è stato sfortunato”
“Già. E del fatto che questo risultato sia molto vicino a 1/e ne parliamo un'altra volta.”
“Oh!”
“Eh.”
Scocciatissimo, si alza dalla sedia, le raccoglie, e le rimette sulla scrivania. Ma ha un problema: ha perso l'ordine.
Che fare? Aprire nuovamente tutte le buste, vedere a chi sono indirizzate le lettere, e scrivere gli indirizzi? Una noia mortale. No: Jacopo piuttosto si affida al caso. Prende una busta, e ci scrive sopra il primo indirizzo della sua lista. Prende una seconda busta, e via col secondo indirizzo. E prosegue così fino alla fine.“
“Chissà quanti errori ha fatto.”
“Gli è andata male, in effetti: ha fatto il massimo numero di errori
possibile.”
“Ma dai, non ha beccato nemmeno un indirizzo?”
“No, nessuna lettera ha l'indirizzo giusto.”
“Non è possibile, è stato sfortunatissimo.”
“Chissà. Bisognerebbe fare i conti.”
“Oh, no, dai, un problema anche qui?”
“Eh, la vita è fatta di problemi.”
“...”
“Questo è un problema di dismutazioni.”
“Di cosa?.”
“Dismutazioni, o sconvolgimenti. Sono le permutazioni senza punti fissi.“
“Quelle in cui mescolo tutto?”
“Esatto. Quelle in cui nessun elemento rimane al suo posto.”
“Io so calcolare le permutazioni, ma queste sono casi particolari che non saprei gestire.”
“Eh, non è facile calcolarle, infatti. Il modo più bello per farlo è scrivere una formula ricorsiva.”
“Ah, certo, formula ricorsiva, bellissima, certo, certo.”
“Noto dell'ironia.”
“Daai?”
“Il concetto di funzione ricorsiva è la quintessenza dello spirito matematico. È il cercare di ottenere il massimo rendimento con il minimo sforzo, è il non fare fatica inutile, è lo stare seduti lungo la sponda di un fiume, allungare la mano e pescare il pesce, e scoprire che è già cotto e pulito.”
“Ok, va bene, rinuncio. Vediamo questa fantomatica formula.”
“L'idea è questa: supponiamo di avere 10 caselle numerate da 1 a 10 e riempite con i numeri da 1 a 10, e di mescolare il tutto in modo tale che in nessuna casella cada il numero corrispondente.”
“Cioè nella casella 1 non cade il numero 1, nella casella 2 non cade il numero 2, eccetera?”
“Esatto. Vogliamo contare in quanti modi possibili si possa realizzare una situazione di questo tipo”.
“E come si fa?”
“Si comincia a guardare la prima casella. Cosa c'è dentro?”
“Ah, boh? Certamente non c'è il numero 1.”
“Bene: cosa ci mettiamo? Scegli.”
“Ah, non saprei. Diciamo che ci sia il numero 7?”
“Va bene, nella prima casella c'è il numero 7. Ora andiamo nella casella numero 7: cosa contiene?”
“Certamente non contiene il numero 7, no?”
“Esatto. Ora la domanda è: contiene 1?”
“Beh, potrebbe contenerlo oppure no.”
“E allora facciamo due casi. O 1 è contenuto nella casella 7 oppure no.”
“E questi due casi a cosa ci servono?”
“Analizziamoli. Primo caso: la casella 1 contiene 7 e la casella 7 contiene 1.”
“Ok. Quindi?”
“Quindi abbiamo già sistemato i due numeri 1 e 7, ora dobbiamo risolvere un problema analogo al precedente, con una importante differenza: se prima avevamo a che fare con 10 elementi, ora ne abbiamo 8. Un problema più semplice.”
“Mh, vabbé, ma se non sapevo risolvere quello di prima non so nemmeno risolvere questo.”
“Fammi finire: c'è anche il caso 2: la casella 1 contiene 7 ma la casella 7 non contiene 1.”
“Ok, conterrà qualcos'altro.”
“Certo. Vogliamo capire se si tratta di un problema già risolto in precedenza.”
“Mh, credo di aver capito a cosa ti riferisci: prima abbiamo ricondotto il problema al caso di 8 elementi. Ma adesso?”
“Adesso dobbiamo riempire le caselle da 2 a 10…”
“Quindi abbiamo 9 caselle.”
“E in ognuna di esse non possiamo mettere un numero.”
“Aspetta, perché? Cioè, ho capito che nella casella 2 non posso mettere 2, nella 3 non posso mettere 3, eccetera. Ma nella 7? Il 7 è già stato usato per riempire la 1, quindi quale numero non posso mettere dentro alla casella 7?”
“Ricordati che siamo nel secondo caso: la casella 7 non contiene 1.”
“Ah, ma certo, altrimenti cado nel primo caso che ho già studiato.”
“Esatto. Quindi, praticamente, in questo secondo caso ti sei ricondotto al problema con 9 buste.”
“Giusto.”
“Per concludere: ricorda che siamo partiti da un esempio: abbiamo detto che dentro alla casella 1 è contenuto il 7. Ma 7 è stato scelto a caso.”
“Certo, l'ho scelto io.”
“E quante scelte avevi?”
“Dieci?”
“No, non dieci: nella casella 1 è vietato mettere il numero 1.”
“Allora ho 9 scelte. Quindi il calcolo che stiamo facendo va moltiplicato per 9.”
“Perfetto. A questo punto è fatta la formula ricorsiva: il numero di dismutazioni di 10 elementi lo puoi calcolare sommando il numero di dismutazioni di 8 elementi più quello di 9 elementi, e moltiplicando il risultato per 9.”
“Ma io non so calcolare il numero di dismutazioni di 8 elementi! E nemmeno quello di 9!”
“Ed ecco la magia della ricorsività: ha qualcosa di speciale il numero 10?”
“Eh, uhm, no, direi di no, l'hai scelto tu come esempio, suppongo.”
“Esatto, quindi in realtà io potrei scrivere una formula ricorsiva generica, per il calcolo delle dismutazioni di n elementi.”
“Penso di sì. Anzi, forse ci riesco anche io: posso indicarle con D(n)?”
“Certo.”
“Allora la formula dovrebbe essere questa: il numero di dismutazioni di n elementi, D(n), è uguale a quello di n−1 elementi, cioè D(n−1), sommato a quello di n−2 elementi, cioè D(n−2), il tutto moltiplicato per n−1.”
“Molto bene! La formula è esattamente questa: D(n) = (n−1)(D(n−1) + D(n−2)).”
“Questo ancora non mi aiuta. Se io non so calcolare D(8) e D(9) non mi muovo.”
“Puoi muoverti invece, andando all'indietro. Sai calcolare D(8)?”
“Ho detto di no!”
“Hai detto male: secondo la tua formula, D(8) = 7(D(7) + D(6)).”
“Ma così si complica ancora di più! Non so calcolare niente!”
“Invece no: se continui ad andare indietro, arrivi a calcoli molto facili che puoi ottenere immediatamente.”
“Ah.”
“Per esempio, quanto vale D(1)?”
“Dismutazioni con 1 elemento? Ma si può fare? Un solo elemento non si permuta, rimane fermo al suo posto!”
“Certo, e quindi quante sono le dismutazioni di 1 elemento?”
“Non esistono. Ah, ho capito, sono i giochini che fate voi Veri Matematici con lo zero… Dato che non esistono, dico che il loro numero è 0”
“Bene, vedo che ti stai abituando alla mentalità matematica. Adesso: quanto vale D(2)?”
“Vediamo: con 2 elementi posso fare solo due cose. O li lascio fermi, e non ho una dismutazione, o li scambio tra loro, e questa volta ho una dismutazione. Quindi D(2) = 1”
“Ottimo, ecco fatto. Ora puoi calcolare tutto, basta usare la formula ricorsiva tante volte fino a che non arrivi a dover calcolare D(1) e D(2)”
“Ahh, molto bene!”
“Ecco i risultati:”
D(3) = 2(D(2) + D(1)) = 2(1 + 0) = 2 D(4) = 3(D(3) + D(2)) = 3(2 + 1) = 9 D(5) = 4(D(4) + D(3)) = 4(9 + 2) = 44 D(6) = 5(D(5) + D(4)) = 5(44 + 9) = 265 D(7) = 6(D(6) + D(5)) = 6(265 + 44) = 1854 D(8) = 7(D(7) + D(6)) = 7(1854 + 265) = 14833 D(9) = 8(D(8) + D(7)) = 8(14833 + 1854) = 133496 D(10) = 9(D(9) + D(8)) = 9(133496 + 14833) = 1334961
“Quindi, volendo rispondere alla mia domanda iniziale, cioè se è stato un caso sfortunato oppure no, dovrei calcolarmi il rapporto tra queste dismutazioni e tutte le possibili permutazioni di 10 elementi”
“Che sono 10 fattoriale, cioè 3628800.”
“Il rapporto risulta circa 0.37, è stato sfortunato”
“Già. E del fatto che questo risultato sia molto vicino a 1/e ne parliamo un'altra volta.”
“Oh!”
“Eh.”
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 n + 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.
“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 n + 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: n × (n − 1) × (n − 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! = n × (n − 1) × (n − 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 × 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”.
“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: n × (n − 1) × (n − 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! = n × (n − 1) × (n − 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 × 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:”.
“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”.
sabato 28 febbraio 2015
Polinomi e dadi
“Mi hanno proposto un quesito che mi sembrava facile, e invece…”.
“Eh, succede spesso con le cose che sembrano facili. Uno dice dai, è semplice, si farà così e cosà, poi quando prova a risolvere si pianta”.
“Già”.
“Ma il quesito in questione qual è?”.
“Questo: abbiamo dei dadi a sei facce numerate in un modo non standard, cioè con i numeri 0, 0, 1, 2, 3, 4. Ne lanciamo cinque e sommiamo le cifre che vediamo: quali sono le probabilità di ottenere i numeri da 0 a 20?”.
“Hai ragione, non è per niente facile. Esiste un metodo per provare a risolvere quesiti del genere, metodo che fornisce una soluzione semplice da scrivere ma comunque difficile da calcolare”.
“Andiamo bene”.
“Eh, lo so, alcuni problemi sono proprio difficili, non si riescono a trovare (o non esistono, chissà) formule semplici per risolverli.”.
“Ma quindi questo si risolve o no?”.
“In un certo senso, sì”.
“Uhm”.
“Ma il bello non è tanto il risultato, quanto la strada percorsa per arrivarci”.
“Ti sento molto zen”.
“Quando la strada ti permette di vedere un problema da tanti punti di vista che apparentemente sembrano scollegati uno dall'altro, nel momento in cui scopri un filo conduttore che li lega tutti quanti ecco che ti sembra di raggiungere l'illuminazione”.
“Sempre più zen”.
“Provo a spiegarti il metodo, ok?”.
“Vai”.
“Partiamo da un caso semplice, però”.
“Mi sembra giusto”.
“Prendiamo un dado a due facce…”.
“Una moneta, insomma”.
“Sì, ma numeriamo le facce con i due numeri 0 e 1, poi lanciamo un po' di monete e cerchiamo di calcolare quello che succede”.
“Va bene”.
“Con una moneta è facile, puoi ottenere solo 0 e 1”.
“E vabbé”.
“Con due monete puoi ottenere i valori 0, 1 e 2”.
“Ma non con la stessa probabilità, no?”.
“Esattamente. Facciamo uno schema di quello che può succedere:”.
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 2
“È più facile ottenere 1 che non 0 oppure 2”.
“Certo. Se riportiamo questo problema al tuo problema, hai solo molti più conti da fare, ma compilando uno schema come questo ce la fai sempre”.
“Grazie! Ma uno schema come questo è lunghissimo da fare. Ho provato, sai? Ma poi ho lasciato lì in fretta, i valori intermedi tra 0 e 20 si possono ottenere in un'infinità di modi diversi, ci si perde”.
“Perfetto, questo è esattamente il problema: troppi conti da fare senza nessuna regola semplice che ci permetta di evitarli”.
“Eh, e quindi?”.
“Quindi adesso cambio completamente problema, te ne propongo un altro che non ha niente a che fare con questo, e poi scopriremo invece che non è così”.
“Sono curioso, sentiamo”.
“Sai calcolare il quadrato di un binomio?”.
“Uh, ma cosa c'entra… ok, ok, come non detto. Sì, se mi ricordo bene, sì: quadrato del primo più doppio prodotto del primo per il secondo più quadrato del secondo”.
“Ricordi bene. Sai applicarlo a questo binomio?”.
(1 + x)2
“Direi proprio di sì, viene 1 + 2x + x2”.
“Ok. Ora, dimmi, perché si fa il doppio prodotto?”.
“Eh, uh, perché… perché sì!”.
“…”.
“Ok, ora non ricordo bene, ehm. Ma, boh, probabilmente uno ha provato una volta a fare la moltiplicazione e si sarà accorto che va bene così”.
“Vuoi provare tu?”.
“A calcolare il quadrato come se fosse (1 + x)(1 + x)?”.
“Sì”.
“Ah, va bene, allora: 1 + x + x + x2. I due termini di primo grado si sommano e risulta quello che avevo detto”.
“Bene. Come potresti spiegare il motivo per cui risultano due termini di primo grado che si sommano e uno solo di secondo grado?”.
“Beh, i due termini di primo grado sarebbero uno 1·x, l'altro x·1. Insomma, una volta moltiplico l'uno che si trova nella prima parentesi con la x che si trova nella seconda, l'altra invece moltiplico la x che si trova nella prima parentesi con l'uno che si trova nella seconda”.
“E il termine di secondo grado, invece?”.
“Per quello è ancora più semplice: c'è un solo modo di ottenerlo”.
“Quale?”.
“Moltiplicare la x della prima parentesi con la x della seconda”.
“Quindi, riassumendo: nel risultato hai tre termini, uno di grado 2, uno di grado 1, e un termine noto che è di grado 0”.
“Giusto”.
“Il termine di grado 0 lo puoi ottenere soltanto moltiplicando due termini di grado 0”.
“Certo”.
“In simboli: 0 + 0 = 0”.
“Già”.
“Il termine di grado 2 lo puoi ottenere in un solo modo, moltiplicando due termini di grado 1”.
“Vero anche questo”.
“In simboli: 1 + 1 = 2”.
“Uh, ma questa è la tabella che hai fatto prima coi possibili risultati dei dadi!”.
“Già: concludi tu”.
“Il termine di grado 1 lo posso ottenere in due modi, moltiplicando un termine di grado 0 per uno di grado 1, oppure viceversa, moltiplicando un termine di grado 1 per uno di grado 0. In simboli: 0 + 1 = 1 e anche 1 + 0 = 0”.
“Ecco il filo conduttore: nel lancio di due dadi con i numeri 0 e 1 sulle facce e nel calcolo dello sviluppo del quadrato di (1 + x) si fanno gli stessi calcoli”.
“Roba da matti”.
“Proviamo a farlo con tre dadi?”.
“Sempre con due facce?”.
“Per adesso sì. Facciamo prima una tabellina coi risultati possibili, con tre dadi ci si riesce ancora”.
“Faccio subito, dovrebbe essere questa:”.
0 + 0 + 0 = 0
1 + 0 + 0 = 1
0 + 1 + 0 = 1
0 + 0 + 1 = 1
1 + 1 + 0 = 2
1 + 0 + 1 = 2
0 + 1 + 1 = 2
1 + 1 + 1 = 3
“Bene, quindi hai un modo per fare 0, tre modi per fare 1 oppure 2, e un modo per fare 3”.
“Ok. E il quadrato di binomio?”.
“Questo non sarà più un quadrato, perché puoi anche ottenere 3 come risultato. Prima hai calcolato il quadrato perché il risultato più alto che potevi ottenere lanciando due dadi era 2, e analogamente il grado più alto che puoi ottenere facendo il quadrato di (1 + x) è 2”.
“Adesso quindi devo fare il cubo, dato che ho un massimo uguale a 3?”.
“Esatto”.
“Vediamo, ehm, non ricordo bene, mumble mumble, uno più x al quadrato, poi ancora per uno più x, puff pant…”.
“Tutto bene?”.
“Ehh, sì, ecco, due più uno, fatto! Mi viene così: 1 + 3x + 3x2 + x3”.
“Perfetto. Hai capito la corrispondenza tra questo polinomio e la tabella che abbiamo fatto prima?”.
“Sì, sì! Molto bella! Quell'uno che ho trovato corrisponde all'unico modo che ho di ottenere 0”.
“E osserva che 0 è proprio il grado del monomio 1”.
“Giusto. Invece 3x corrisponde ai 3 modi di ottenere 1. In effetti 3x è 3x1, il grado della x corrisponde al risultato”.
“Molto bene. Poi hai visto che hai altri tre modi di ottenere 2”.
“E questo fatto si traduce nella presenza del monomio 3x2. Alla fine poi ho un solo modo di ottenere 3, e infatti nello sviluppo del cubo di binomio ho proprio un solo termine x3”.
“Perfetto. Ora generalizziamo in un'altra direzione”.
“In che senso?”.
“Abbiamo due dadi, questa volta con tre facce”.
“E come sono fatti?”.
“Beh, non importa, fai finta che esistano. Nella pratica puoi prendere un dado a sei facce e numerate 0, 0, 1, 1, 2, 2, ma non complichiamo le cose, vorrei ragionare proprio su tre sole facce”.
“Ah, va bene. Numerate da 0 a 2, allora?”.
“Esatto. Fai la tabellina dei possibili risultati?”.
“Pronti.”.
0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
2 + 0 = 2
1 + 1 = 2
0 + 2 = 2
2 + 1 = 3
1 + 2 = 3
2 + 2 = 4
“Ora pensiamo a come costruire il polinomio che corrisponde a questo dado”.
“Uhm, tre facce, come si fa?”.
“Pensa a dove memorizzavi, nel caso precedente, i valori scritti sulle facce”.
“Erano gli esponenti della x, i gradi dei singoli monomi, insomma”.
“Ora hai tre facce…”.
“E quindi tre valori, allora devo scrivere un trinomio questa volta?”.
“Esatto”.
“Va bene (1 + x + x2)?”.
“Va benissimo, è lui. Il numero di lanci, invece, dove lo utilizzavi?”.
“Era l'esponente del polinomio. Quindi adesso dovrei calcolarmi (1 + x + x2)2?”.
“Già”.
“Eh, ehm, devo farlo a mano?”.
“Permettimi di ricordarti la formula, così facciamo prima”.
“Ne hai facoltà”.
“Devi calcolarti tre quadrati e poi aggiungere i tre possibili doppi prodotti”.
“Ah. Allora faccio i conti”.
(1 + x + x2)2 = 1 + x2 + x4 + 2x + 2x2 + 2x3.
“Bene, ma non hai finito, metti insieme i termini simili”.
“Ah, già. Ecco:”.
(1 + x + x2)2 = 1 + 2x + 3x2 + 2x3 + x4.
“E, come vedi, i conti tornano, il risultato corrisponde alla tabella di prima”.
“Devo dire che questa connessione tra dadi e polinomi è affascinante. Quindi potrei risolvere in questo modo anche il mio problema originale?”.
“Esatto. Ma, per fare un'analisi completa, lasciami fare prima un'altra domanda: cosa succederebbe se le facce del nostro dado non avessero la stessa probabilità di uscire?”.
“Uh?”.
“Supponi che il dado a due facce non sia equilibrato, ma che 2 volte su 3 esca lo zero, mentre 1 volta su 3 esca l'uno. Come facciamo l'analisi?”.
“Boh?”.
“Fai una tabella…”.
“Eh, ma con probabilità diverse come si fa?”.
“Fai finta che il dado abbia tre facce”.
“Ah! Un dado con le facce numerate così: 0, 0, 1”.
“Già. Prova a lanciarlo due volte”.
“Ok, ecco la tabella:”.
0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 2
“Siamo sicuri?”.
“Eh, in effetti mi viene uguale a quella del dado a due facce. Come faccio a tener conto del fatto che ci sono due facce uguali?”.
“Fai finta, inizialmente, che siano diverse. Invece di numerarle con 0, 0, 1 usa un'altra simbologia, in modo da distinguere i due zeri”.
“Ah, allora numero i due zeri in modo diverso, li chiamo 01 e 02. Ecco quello che potrei ottenere”.
01 + 01 = 0
01 + 02 = 0
02 + 01 = 0
02 + 02 = 0
01 + 1 = 1
02 + 1 = 1
1 + 01 = 1
1 + 02 = 1
1 + 1 = 2
“Ok, quindi hai quattro modi per fare 0, quattro modi per fare 1 e un solo modo per fare 2”.
“E coi polinomi come faccio?”.
“Prova a calcolare il quadrato di (2 + x)”.
“Ah! Risulta 4 + 4x + x2”.
“Come vedi, tutto torna”.
“Ma quindi uso (2 + x) invece di (1 + x) perché ci sono due facce uguali?”.
“Puoi ragionare in due modi diversi. Il primo è questo: usi 2 al posto di 1 perché hai 2 casi in cui esce il numero 0, e non uno solo. Altrimenti puoi sempre immaginare di avere una faccia in più, e quindi in realtà quello che stai calcolando è il quadrato del trinomio (1 + 1 + x) ”.
“Perfetto”.
“In sostanza, i coefficienti delle incognite nel polinomio sono legati alla probabilità di uscita della corrispondente faccia del dado”.
“Mentre il valore presente sulla faccia corrisponde all'esponente dell'incognita in ogni monomio”.
“È così. Tutto si basa sulla regola che trasforma la moltiplicazione di potenze con la stessa base in una somma di esponenti”.
“E questa è la somma dei valori delle facce”.
“Sì, mentre la probabilità di uscita di ogni faccia può essere vista come un peso assegnato al valore corrispondente: nel nostro esempio lo zero pesa più dell'uno, perché ha più probabilità di uscita”.
“E allora di zeri ce ne mettiamo due”.
“Già. Volendo potresti mettere come coefficiente della x proprio la probabilità di uscita di quella faccia, in questo caso avresti a che fare con coefficienti frazionari, ma siccome essi avrebbero tutti lo stesso denominatore, potresti raccoglierlo a fattor comune e portarlo fuori dalla parentesi”.
“In sostanza farei gli stessi calcoli”.
“Sì, si tratta di vedere se preferisci lasciare sottinteso il denominatore, o se invece vuoi esplicitarlo: non cambia niente. E ora sei pronto a risolvere il problema del tuo dado”.
“Provo, eh. Allora, sei facce, quindi devo costruire un… esanomio?”.
“Facciamo un polinomio di sei termini”.
“Forse è meglio, sì. Le facce hanno valore 0, 0, 1, 2, 3, 4: questi sono gli esponenti dell'incognita”.
“E sono anche tutte equiprobabili”.
“Giusto, quindi i coefficienti sono uguali a 1. Il polinomio dovrebbe essere questo: (1 + 1 + x + x2 + x3 + x4)”.
“E siccome lanci il dado cinque volte…”.
“Devo elevare il polinomio alla quinta. Ecco la formula finale:”.
(1 + 1 + x + x2 + x3 + x4)5
“Bene”.
“Sì, ma, ehm, quanto fa?”.
“Ah, boh, bisogna farsi tutti i calcoli. Ricordi che all'inizio di questo discorso avevamo detto che il quesito si risolve in un certo senso?”.
“Eh”.
“Beh, in teoria è risolto, devi solo metterti lì a fare i conti. Rispetto a farsi tutta la tabella con tutte le possibili combinazioni dei risultati è comunque un passo avanti”.
“Questo è vero, però è una soluzione deludente”.
“Non si può fare di meglio, i calcoli sono proprio brutti. Un punto chiave del problema è capire in quanti modi puoi ottenere un numero, per esempio 8, sommando cinque valori presi dall'insieme che contiene 0, 1, 2, 3, 4”.
“È proprio quello il problema, avevo cominciato a fare i conti ma sono tantissimi”.
“Già: sono 905”.
“Cosa? Così tanti? E come hai fatto a calcolarlo?”.
“Beh, oggi certi calcoli possiamo farli fare alle macchine. Ecco qua lo sviluppo del tuo polinomio elevato alla quinta:”.
x20 + 5x19 + 15x18 + 35x17 + 75x16 + 141x15 + 235x14 + 355x13 + 505x12 + 655x11 + 781x10 + 865x9 + 905x8 + 855x7 + 745x6 + 601x5 + 450x4 + 280x3 + 160x2 + 80x + 32.
“Santo cielo”.
“Pensa a quando questi conti si facevano tutti a mano”.
“Mo'c lavòr”.
[EDIT: ho dimenticato di inserire i ringraziamenti a chi ha partecipato alla risoluzione del problema. La discussione è iniziata sul socialino dell'amore, raggiungibile (finché dura) a questo link]
“Eh, succede spesso con le cose che sembrano facili. Uno dice dai, è semplice, si farà così e cosà, poi quando prova a risolvere si pianta”.
“Già”.
“Ma il quesito in questione qual è?”.
“Questo: abbiamo dei dadi a sei facce numerate in un modo non standard, cioè con i numeri 0, 0, 1, 2, 3, 4. Ne lanciamo cinque e sommiamo le cifre che vediamo: quali sono le probabilità di ottenere i numeri da 0 a 20?”.
“Hai ragione, non è per niente facile. Esiste un metodo per provare a risolvere quesiti del genere, metodo che fornisce una soluzione semplice da scrivere ma comunque difficile da calcolare”.
“Andiamo bene”.
“Eh, lo so, alcuni problemi sono proprio difficili, non si riescono a trovare (o non esistono, chissà) formule semplici per risolverli.”.
“Ma quindi questo si risolve o no?”.
“In un certo senso, sì”.
“Uhm”.
“Ma il bello non è tanto il risultato, quanto la strada percorsa per arrivarci”.
“Ti sento molto zen”.
“Quando la strada ti permette di vedere un problema da tanti punti di vista che apparentemente sembrano scollegati uno dall'altro, nel momento in cui scopri un filo conduttore che li lega tutti quanti ecco che ti sembra di raggiungere l'illuminazione”.
“Sempre più zen”.
“Provo a spiegarti il metodo, ok?”.
“Vai”.
“Partiamo da un caso semplice, però”.
“Mi sembra giusto”.
“Prendiamo un dado a due facce…”.
“Una moneta, insomma”.
“Sì, ma numeriamo le facce con i due numeri 0 e 1, poi lanciamo un po' di monete e cerchiamo di calcolare quello che succede”.
“Va bene”.
“Con una moneta è facile, puoi ottenere solo 0 e 1”.
“E vabbé”.
“Con due monete puoi ottenere i valori 0, 1 e 2”.
“Ma non con la stessa probabilità, no?”.
“Esattamente. Facciamo uno schema di quello che può succedere:”.
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 2
“È più facile ottenere 1 che non 0 oppure 2”.
“Certo. Se riportiamo questo problema al tuo problema, hai solo molti più conti da fare, ma compilando uno schema come questo ce la fai sempre”.
“Grazie! Ma uno schema come questo è lunghissimo da fare. Ho provato, sai? Ma poi ho lasciato lì in fretta, i valori intermedi tra 0 e 20 si possono ottenere in un'infinità di modi diversi, ci si perde”.
“Perfetto, questo è esattamente il problema: troppi conti da fare senza nessuna regola semplice che ci permetta di evitarli”.
“Eh, e quindi?”.
“Quindi adesso cambio completamente problema, te ne propongo un altro che non ha niente a che fare con questo, e poi scopriremo invece che non è così”.
“Sono curioso, sentiamo”.
“Sai calcolare il quadrato di un binomio?”.
“Uh, ma cosa c'entra… ok, ok, come non detto. Sì, se mi ricordo bene, sì: quadrato del primo più doppio prodotto del primo per il secondo più quadrato del secondo”.
“Ricordi bene. Sai applicarlo a questo binomio?”.
(1 + x)2
“Direi proprio di sì, viene 1 + 2x + x2”.
“Ok. Ora, dimmi, perché si fa il doppio prodotto?”.
“Eh, uh, perché… perché sì!”.
“…”.
“Ok, ora non ricordo bene, ehm. Ma, boh, probabilmente uno ha provato una volta a fare la moltiplicazione e si sarà accorto che va bene così”.
“Vuoi provare tu?”.
“A calcolare il quadrato come se fosse (1 + x)(1 + x)?”.
“Sì”.
“Ah, va bene, allora: 1 + x + x + x2. I due termini di primo grado si sommano e risulta quello che avevo detto”.
“Bene. Come potresti spiegare il motivo per cui risultano due termini di primo grado che si sommano e uno solo di secondo grado?”.
“Beh, i due termini di primo grado sarebbero uno 1·x, l'altro x·1. Insomma, una volta moltiplico l'uno che si trova nella prima parentesi con la x che si trova nella seconda, l'altra invece moltiplico la x che si trova nella prima parentesi con l'uno che si trova nella seconda”.
“E il termine di secondo grado, invece?”.
“Per quello è ancora più semplice: c'è un solo modo di ottenerlo”.
“Quale?”.
“Moltiplicare la x della prima parentesi con la x della seconda”.
“Quindi, riassumendo: nel risultato hai tre termini, uno di grado 2, uno di grado 1, e un termine noto che è di grado 0”.
“Giusto”.
“Il termine di grado 0 lo puoi ottenere soltanto moltiplicando due termini di grado 0”.
“Certo”.
“In simboli: 0 + 0 = 0”.
“Già”.
“Il termine di grado 2 lo puoi ottenere in un solo modo, moltiplicando due termini di grado 1”.
“Vero anche questo”.
“In simboli: 1 + 1 = 2”.
“Uh, ma questa è la tabella che hai fatto prima coi possibili risultati dei dadi!”.
“Già: concludi tu”.
“Il termine di grado 1 lo posso ottenere in due modi, moltiplicando un termine di grado 0 per uno di grado 1, oppure viceversa, moltiplicando un termine di grado 1 per uno di grado 0. In simboli: 0 + 1 = 1 e anche 1 + 0 = 0”.
“Ecco il filo conduttore: nel lancio di due dadi con i numeri 0 e 1 sulle facce e nel calcolo dello sviluppo del quadrato di (1 + x) si fanno gli stessi calcoli”.
“Roba da matti”.
“Proviamo a farlo con tre dadi?”.
“Sempre con due facce?”.
“Per adesso sì. Facciamo prima una tabellina coi risultati possibili, con tre dadi ci si riesce ancora”.
“Faccio subito, dovrebbe essere questa:”.
0 + 0 + 0 = 0
1 + 0 + 0 = 1
0 + 1 + 0 = 1
0 + 0 + 1 = 1
1 + 1 + 0 = 2
1 + 0 + 1 = 2
0 + 1 + 1 = 2
1 + 1 + 1 = 3
“Bene, quindi hai un modo per fare 0, tre modi per fare 1 oppure 2, e un modo per fare 3”.
“Ok. E il quadrato di binomio?”.
“Questo non sarà più un quadrato, perché puoi anche ottenere 3 come risultato. Prima hai calcolato il quadrato perché il risultato più alto che potevi ottenere lanciando due dadi era 2, e analogamente il grado più alto che puoi ottenere facendo il quadrato di (1 + x) è 2”.
“Adesso quindi devo fare il cubo, dato che ho un massimo uguale a 3?”.
“Esatto”.
“Vediamo, ehm, non ricordo bene, mumble mumble, uno più x al quadrato, poi ancora per uno più x, puff pant…”.
“Tutto bene?”.
“Ehh, sì, ecco, due più uno, fatto! Mi viene così: 1 + 3x + 3x2 + x3”.
“Perfetto. Hai capito la corrispondenza tra questo polinomio e la tabella che abbiamo fatto prima?”.
“Sì, sì! Molto bella! Quell'uno che ho trovato corrisponde all'unico modo che ho di ottenere 0”.
“E osserva che 0 è proprio il grado del monomio 1”.
“Giusto. Invece 3x corrisponde ai 3 modi di ottenere 1. In effetti 3x è 3x1, il grado della x corrisponde al risultato”.
“Molto bene. Poi hai visto che hai altri tre modi di ottenere 2”.
“E questo fatto si traduce nella presenza del monomio 3x2. Alla fine poi ho un solo modo di ottenere 3, e infatti nello sviluppo del cubo di binomio ho proprio un solo termine x3”.
“Perfetto. Ora generalizziamo in un'altra direzione”.
“In che senso?”.
“Abbiamo due dadi, questa volta con tre facce”.
“E come sono fatti?”.
“Beh, non importa, fai finta che esistano. Nella pratica puoi prendere un dado a sei facce e numerate 0, 0, 1, 1, 2, 2, ma non complichiamo le cose, vorrei ragionare proprio su tre sole facce”.
“Ah, va bene. Numerate da 0 a 2, allora?”.
“Esatto. Fai la tabellina dei possibili risultati?”.
“Pronti.”.
0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
2 + 0 = 2
1 + 1 = 2
0 + 2 = 2
2 + 1 = 3
1 + 2 = 3
2 + 2 = 4
“Ora pensiamo a come costruire il polinomio che corrisponde a questo dado”.
“Uhm, tre facce, come si fa?”.
“Pensa a dove memorizzavi, nel caso precedente, i valori scritti sulle facce”.
“Erano gli esponenti della x, i gradi dei singoli monomi, insomma”.
“Ora hai tre facce…”.
“E quindi tre valori, allora devo scrivere un trinomio questa volta?”.
“Esatto”.
“Va bene (1 + x + x2)?”.
“Va benissimo, è lui. Il numero di lanci, invece, dove lo utilizzavi?”.
“Era l'esponente del polinomio. Quindi adesso dovrei calcolarmi (1 + x + x2)2?”.
“Già”.
“Eh, ehm, devo farlo a mano?”.
“Permettimi di ricordarti la formula, così facciamo prima”.
“Ne hai facoltà”.
“Devi calcolarti tre quadrati e poi aggiungere i tre possibili doppi prodotti”.
“Ah. Allora faccio i conti”.
(1 + x + x2)2 = 1 + x2 + x4 + 2x + 2x2 + 2x3.
“Bene, ma non hai finito, metti insieme i termini simili”.
“Ah, già. Ecco:”.
(1 + x + x2)2 = 1 + 2x + 3x2 + 2x3 + x4.
“E, come vedi, i conti tornano, il risultato corrisponde alla tabella di prima”.
“Devo dire che questa connessione tra dadi e polinomi è affascinante. Quindi potrei risolvere in questo modo anche il mio problema originale?”.
“Esatto. Ma, per fare un'analisi completa, lasciami fare prima un'altra domanda: cosa succederebbe se le facce del nostro dado non avessero la stessa probabilità di uscire?”.
“Uh?”.
“Supponi che il dado a due facce non sia equilibrato, ma che 2 volte su 3 esca lo zero, mentre 1 volta su 3 esca l'uno. Come facciamo l'analisi?”.
“Boh?”.
“Fai una tabella…”.
“Eh, ma con probabilità diverse come si fa?”.
“Fai finta che il dado abbia tre facce”.
“Ah! Un dado con le facce numerate così: 0, 0, 1”.
“Già. Prova a lanciarlo due volte”.
“Ok, ecco la tabella:”.
0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 2
“Siamo sicuri?”.
“Eh, in effetti mi viene uguale a quella del dado a due facce. Come faccio a tener conto del fatto che ci sono due facce uguali?”.
“Fai finta, inizialmente, che siano diverse. Invece di numerarle con 0, 0, 1 usa un'altra simbologia, in modo da distinguere i due zeri”.
“Ah, allora numero i due zeri in modo diverso, li chiamo 01 e 02. Ecco quello che potrei ottenere”.
01 + 01 = 0
01 + 02 = 0
02 + 01 = 0
02 + 02 = 0
01 + 1 = 1
02 + 1 = 1
1 + 01 = 1
1 + 02 = 1
1 + 1 = 2
“Ok, quindi hai quattro modi per fare 0, quattro modi per fare 1 e un solo modo per fare 2”.
“E coi polinomi come faccio?”.
“Prova a calcolare il quadrato di (2 + x)”.
“Ah! Risulta 4 + 4x + x2”.
“Come vedi, tutto torna”.
“Ma quindi uso (2 + x) invece di (1 + x) perché ci sono due facce uguali?”.
“Puoi ragionare in due modi diversi. Il primo è questo: usi 2 al posto di 1 perché hai 2 casi in cui esce il numero 0, e non uno solo. Altrimenti puoi sempre immaginare di avere una faccia in più, e quindi in realtà quello che stai calcolando è il quadrato del trinomio (1 + 1 + x) ”.
“Perfetto”.
“In sostanza, i coefficienti delle incognite nel polinomio sono legati alla probabilità di uscita della corrispondente faccia del dado”.
“Mentre il valore presente sulla faccia corrisponde all'esponente dell'incognita in ogni monomio”.
“È così. Tutto si basa sulla regola che trasforma la moltiplicazione di potenze con la stessa base in una somma di esponenti”.
“E questa è la somma dei valori delle facce”.
“Sì, mentre la probabilità di uscita di ogni faccia può essere vista come un peso assegnato al valore corrispondente: nel nostro esempio lo zero pesa più dell'uno, perché ha più probabilità di uscita”.
“E allora di zeri ce ne mettiamo due”.
“Già. Volendo potresti mettere come coefficiente della x proprio la probabilità di uscita di quella faccia, in questo caso avresti a che fare con coefficienti frazionari, ma siccome essi avrebbero tutti lo stesso denominatore, potresti raccoglierlo a fattor comune e portarlo fuori dalla parentesi”.
“In sostanza farei gli stessi calcoli”.
“Sì, si tratta di vedere se preferisci lasciare sottinteso il denominatore, o se invece vuoi esplicitarlo: non cambia niente. E ora sei pronto a risolvere il problema del tuo dado”.
“Provo, eh. Allora, sei facce, quindi devo costruire un… esanomio?”.
“Facciamo un polinomio di sei termini”.
“Forse è meglio, sì. Le facce hanno valore 0, 0, 1, 2, 3, 4: questi sono gli esponenti dell'incognita”.
“E sono anche tutte equiprobabili”.
“Giusto, quindi i coefficienti sono uguali a 1. Il polinomio dovrebbe essere questo: (1 + 1 + x + x2 + x3 + x4)”.
“E siccome lanci il dado cinque volte…”.
“Devo elevare il polinomio alla quinta. Ecco la formula finale:”.
(1 + 1 + x + x2 + x3 + x4)5
“Bene”.
“Sì, ma, ehm, quanto fa?”.
“Ah, boh, bisogna farsi tutti i calcoli. Ricordi che all'inizio di questo discorso avevamo detto che il quesito si risolve in un certo senso?”.
“Eh”.
“Beh, in teoria è risolto, devi solo metterti lì a fare i conti. Rispetto a farsi tutta la tabella con tutte le possibili combinazioni dei risultati è comunque un passo avanti”.
“Questo è vero, però è una soluzione deludente”.
“Non si può fare di meglio, i calcoli sono proprio brutti. Un punto chiave del problema è capire in quanti modi puoi ottenere un numero, per esempio 8, sommando cinque valori presi dall'insieme che contiene 0, 1, 2, 3, 4”.
“È proprio quello il problema, avevo cominciato a fare i conti ma sono tantissimi”.
“Già: sono 905”.
“Cosa? Così tanti? E come hai fatto a calcolarlo?”.
“Beh, oggi certi calcoli possiamo farli fare alle macchine. Ecco qua lo sviluppo del tuo polinomio elevato alla quinta:”.
x20 + 5x19 + 15x18 + 35x17 + 75x16 + 141x15 + 235x14 + 355x13 + 505x12 + 655x11 + 781x10 + 865x9 + 905x8 + 855x7 + 745x6 + 601x5 + 450x4 + 280x3 + 160x2 + 80x + 32.
“Santo cielo”.
“Pensa a quando questi conti si facevano tutti a mano”.
“Mo'c lavòr”.
[EDIT: ho dimenticato di inserire i ringraziamenti a chi ha partecipato alla risoluzione del problema. La discussione è iniziata sul socialino dell'amore, raggiungibile (finché dura) a questo link]
mercoledì 28 gennaio 2015
Soluzione al quizzino del sabato sera (in cui si mostra come, a volte, si possano davvero sfruttare evidenti ragioni di simmetria)
Il problema chiedeva di colorare una scacchiera quadrata con due colori, in modo tale che qualunque rettangolo contenuto in essa (non degenere) abbia i quattro angoli colorati con entrambi i colori.
Per scacchiere piccole ci si riesce, il post forniva degli esempi. Per scacchiere grandi, invece, che succede?
Primo fatto: se per un certo valore di n la scacchiera n×n non è colorabile, allora non lo sono nemmeno quelle il cui lato ha una lunghezza maggiore di n, dato che non siamo in grado di colorarne nemmeno una loro parte. Quindi il problema diventa: n può essere grande quanto si vuole, oppure esiste un valore massimo?
Bene, si dimostra che se n = 5 la scacchiera non è colorabile come richiesto, e se invece n = 4 ci si riesce.
Prima la parte facile: ecco una possibile colorazione di una scacchiera 4×4:
Ora vediamo cosa succede con una scacchiera 5×5. Essa è composta da 25 caselle, quindi se la colorazione richiesta fosse possibile, dovremmo essere in grado di colorarne almeno 13. Questa affermazione è giustificata da evidenti ragioni di simmetria: se non fossimo in grado di colorare 13 caselle digiallo quel colore che ho usato nel disegno qua sopra, ce ne sarebbero almeno 13 bianche. Bene, allora coloriamo quelle bianche e facciamo diventare bianche le altre, e siamo da capo.
E quindi il problema si è ridotto a questo: riusciamo a colorare almeno 13 caselle?
Se nella prima riga ne colorassimo cinque (ricordiamo che non è importante che sia proprio la prima riga):
nella seconda ne potremmo mettere soltanto una, e così pure nella terza, nella quarta e nell'ultima: se ne mettessimo di più, avremmo dei rettangoli con gli angoli monocolore. In questo modo saremmo in grado di colorare solo 5 + 1 + 1 + 1 + 1 = 9 caselle, poche.
Proviamo con quattro caselle colorate nella prima riga:
In questo caso potremmo colorarne due nelle righe successive, e non di più. In questo modo otterremmo 4 + 2 + 2 + 2 + 2 = 12 caselle: troppo poche.
Se poi la prima riga avesse solo tre caselle colorate, ne potremmo inserire tre anche nella seconda:
e poi però nelle righe successive non potremmo inserirne più di due, una in una delle prime tre caselle, e l'altra in una delle altre due. Se ne inserissimo di più, formeremmo un rettangolo con gli angoli monocolore.
Quindi in questo caso il massimo numero di caselle colorate sarà 3 + 3 + 2 + 2 + 2 = 12, ancora troppo poche.
Fine della dimostrazione: 13 caselle non si possono colorare, quindi le uniche scacchiere colorabili nel modo richiesto sono quelle aventi n uguale a 2, 3 oppure 4.
Per scacchiere piccole ci si riesce, il post forniva degli esempi. Per scacchiere grandi, invece, che succede?
Primo fatto: se per un certo valore di n la scacchiera n×n non è colorabile, allora non lo sono nemmeno quelle il cui lato ha una lunghezza maggiore di n, dato che non siamo in grado di colorarne nemmeno una loro parte. Quindi il problema diventa: n può essere grande quanto si vuole, oppure esiste un valore massimo?
Bene, si dimostra che se n = 5 la scacchiera non è colorabile come richiesto, e se invece n = 4 ci si riesce.
Prima la parte facile: ecco una possibile colorazione di una scacchiera 4×4:
Ora vediamo cosa succede con una scacchiera 5×5. Essa è composta da 25 caselle, quindi se la colorazione richiesta fosse possibile, dovremmo essere in grado di colorarne almeno 13. Questa affermazione è giustificata da evidenti ragioni di simmetria: se non fossimo in grado di colorare 13 caselle di
E quindi il problema si è ridotto a questo: riusciamo a colorare almeno 13 caselle?
Se nella prima riga ne colorassimo cinque (ricordiamo che non è importante che sia proprio la prima riga):
nella seconda ne potremmo mettere soltanto una, e così pure nella terza, nella quarta e nell'ultima: se ne mettessimo di più, avremmo dei rettangoli con gli angoli monocolore. In questo modo saremmo in grado di colorare solo 5 + 1 + 1 + 1 + 1 = 9 caselle, poche.
Proviamo con quattro caselle colorate nella prima riga:
In questo caso potremmo colorarne due nelle righe successive, e non di più. In questo modo otterremmo 4 + 2 + 2 + 2 + 2 = 12 caselle: troppo poche.
Se poi la prima riga avesse solo tre caselle colorate, ne potremmo inserire tre anche nella seconda:
e poi però nelle righe successive non potremmo inserirne più di due, una in una delle prime tre caselle, e l'altra in una delle altre due. Se ne inserissimo di più, formeremmo un rettangolo con gli angoli monocolore.
Quindi in questo caso il massimo numero di caselle colorate sarà 3 + 3 + 2 + 2 + 2 = 12, ancora troppo poche.
Fine della dimostrazione: 13 caselle non si possono colorare, quindi le uniche scacchiere colorabili nel modo richiesto sono quelle aventi n uguale a 2, 3 oppure 4.
Iscriviti a:
Commenti (Atom)