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]

2 commenti:

ilcomizietto ha detto...

Su frienfi avete elaborato anche una parte di programmazione su questo problema.

Riesci a farci una sintesi in forma di dialogo di quanto ricavato?

(sono ancora qui con gli occhi sgranati per la soluzione in SQL.)

(Sei bravissimo a spiegare, ma questo l'avevo già detto. :-) )

zar ha detto...

Uh, la parte di programmazione non l'ho mica ancora capita tutta :-)

Però non ho messo i link alla discussione su ff, rimedio subito.