«Applichiamo il principio di inclusione-esclusione alla soluzione di questo quesito: sapendo che ci sono 168 numeri primi minori di 1000, quanti sono i numeri primi da ingegnere minori di 1000? Con numero primo da ingegnere intendiamo ogni numero composito non divisibile per 2, per 3 e per 5».
«Poveri ingegneri…».
«Ma no, hanno le spalle robuste. Poi, con le calcolatrici si sbagliano anche meno, adesso».
«MA DAI!».
«Ok, ok, la smetto. Risolviamo il quesito, allora?».
«Forse è meglio. Da dove cominciamo?».
«Cominciamo a contare: quanti sono i numeri divisibili per 2 minori di 1000?».
«Facile, 500».
«Sbagliato! Minori di 1000, non minori o uguali!».
«Ah. Allora, ci sono 999 numeri minori di 1000, quelli pari sono 499».
«Oh, andiamo meglio. Bisogna prendere la parte intera inferiore di 999/2, cioè bisogna buttare via i decimali senza approssimare».
«Ho capito».
«Quanti sono, allora, i numeri divisibili per 3 minori di 1000?».
«Sono la parte intera inferiore di 999/3, cioè 333».
«E quelli divisibili per 5?».
«Sono la parte intera inferiore di 999/5, cioè 199».
«Perfetto. È come se avessimo tre insiemi A, B e C, tali che |A| = 499, |B| = 333 e |C| = 199».
«Ah, ho capito: per trovare i numeri divisibili per 2, 3 oppure 5 non possiamo semplicemente sommare questi valori, perché alcuni numeri verrebbero contati due volte. Per esempio 6 sta sia in A che in B».
«Proprio così, dobbiamo quindi sottrarre |A∩B|, |A∩C| e |B∩C|».
«Vediamo, i numeri che stanno sia in A che in B sono quelli divisibili sia per 2 che per 3».
«Cioè sono quelli divisibili per 6».
«Giusto: sono la parte intera inferiore di 999/6, cioè 166».
«Poi ci sono quelli divisibili per 2 e per 5».
«Sono quelli divisibili per 10, e sono quindi la parte intera inferiore di 999/10, cioè 99».
«E infine ci sono quelli divisibili per 3 e per 5».
«Che sono la parte intera inferiore di 999/15, cioè 66».
«Ma ancora non basta: se sottraiamo questi valori, togliamo troppo. Cosa dobbiamo riaggiungere?».
«Tutti i numeri divisibili per 2, 3 e 5, cioè quelli divisibili per 30. Sono la parte intera inferiore di 999/30, cioè 33».
«Quindi il calcolo finale che risultato ti dà?».
«Allora, vediamo: ho calcolato che ci sono 499 + 333 + 199 - 166 - 99 - 66 + 33 = 733 numeri divisibili per 2, per 3 oppure per 5».
«Quindi quanti sono i numeri primi da ingegnere?».
«Ho 999 numeri che vanno da 1 a 999; escludo 1 che non è primo e non è composito, e questo dovrebbe saperlo anche un ingegnere».
«Ah, ti metti a fare battute anche tu!».
«Ehm, mi è scappata. Dicevo, escludo 1 e mi rimangono 998 numeri. Sottraggo i numeri divisibili per 2, 3 oppure 5, che sono 733, e mi rimangono 265 numeri. Sottraggo anche i 168 numeri primi compresi tra 1 e 100…».
«Attenzione!».
«Cosa succede?».
«Tra i 168 numeri primi che stai sottraendo ci sono anche 2, 3 e 5».
«Ah, cavolo!».
«Non li puoi sottrarre due volte».
«Giusto, quindi da 265 non devo sottrarre 168, ma 165: mi rimane 100».
«Che è la soluzione giusta: ci sono 100 numeri primi da ingegnere minori di 1000».
«Sono tanti! Poveri ingegneri, chissà quanti errori faranno… Per fortuna hanno le calcolatrici».
«Per fortuna».
lunedì 28 ottobre 2013
venerdì 25 ottobre 2013
Inclusione—esclusione, parte 3: con quattro è difficile anche fare i disegni
«Non vorrai fare i conti con quattro insiemi, adesso?».
«Sì, ma non è un problema fare i conti. È più complicato fare il disegno».
«Uh, davvero?».
«Davvero. Quante zone si possono avere intersecando quattro insiemi?».
«Compresa la zona esterna, 24, cioè 16».
«Bene, se provi a disegnarle nella maniera che ti verrebbe naturale, non ce la fai a farle tutte».
«Davvero?».
«Prova».
«No, no, mi fido… Ma quindi come si fa il disegno?».
«Ci sono varie possibilità; quella proposta da Venn è la seguente:».
«Venn? Quello dei diagrammi di Eulero-Venn?».
«Lui. Del resto, questi disegnini che stiamo facendo sono proprio quei diagrammi».
«Ah, ecco. Comunque quel disegno è proprio brutto, eh».
«Sono d'accordo. Se ne vuoi uno più bello devi passare in tre dimensioni e intersecare quattro sfere».
«Brr, no, no, va bene così».
«Facciamo i conti, allora?».
«Facciamoli. Con 16 zone mi sa che si complicheranno un po'».
«Un pochino, ma non tanto se capiamo come funziona il meccanismo. Ripensiamo al sistema dei gettoni che abbiamo utilizzato con due e tre insiemi».
«Ok».
«Allora, quando mi dicono che gli elementi di A sono tot, io conto tante zone: riesci a elencarle tutte?».
«Credo di sì, sono tutte le combinazioni in cui compare A e non il suo complementare. Eccole qua:».
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D.
«Bene, sono loro. Metterai dunque un gettone in ognuna di queste; quando dovrai tener conto di B metterai altri 8 gettoni in altrettante zone, tutte quelle che corrispondono a combinazioni in cui compare B e non il suo complementare».
«Stessa cosa per C e per D».
«Esatto. Ora prendo una combinazione a caso, per esempio questa: A∩B∩C∩D. Sai dirmi quanti gettoni avrà?».
«Uhm, direi due: uno che viene messo quando conto gli elementi di A, e uno per gli elementi di D».
«Benissimo. Due gettoni sono però troppi, ne dovremo poi togliere uno».
«Come abbiamo fatto l'altra volta».
«Sì, e come l'altra volta, però, dobbiamo stare attenti. Se sottraiamo gli elementi di A∩D, perché li abbiamo contati due volte, sottraiamo un gettone a tutte queste zone:».
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D.
«Giusto. E allora come si fa?».
«E allora si ripresenta il problema di prima: se sottraiamo troppo, dobbiamo tornare ad aggiungere».
«Ah-ha! Ogni volta ci riconduciamo al caso precedente».
«Esatto. Prima sommiamo gli elementi dei quattro insiemi, poi sottraiamo gli elementi che stanno nelle intersezioni di due insiemi, poi riaggiungiamo gli elementi che stanno nelle intersezioni di tre insiemi, e infine sottraiamo gli elementi che stanno nell'intersezione di tutti e quattro».
«Ho capito, provo a scrivere la formula:».
|A∪B∪C∪D| =
= |A| + |B| + |C| + |D|
-|A∩B| - |A∩C| - |A∩D| - |B∩C| - |B∩D| - |C∩D|
+|A∩B∩C| + |A∩B∩D| + |A∩C∩D| + |B∩C∩D|
-|A∩B∩C∩D|.
«Benissimo. Ora hai anche capito come si generalizza a un numero qualsiasi di elementi: si ripete il procedimento sempre alla stessa maniera. Questa regola viene detta principio di inclusione-esclusione, e viene utilizzata per risolvere molti problemi».
«Per esempio?».
«Per esempio questo: sapendo che ci sono 168 numeri primi minori di 1000, quanti sono i numeri primi da ingegnere minori di 1000?».
«Cosa sono i numeri primi da ingegnere?».
«Sono numeri compositi ma non divisibili per 2, per 3 e per 5. Tipo 49».
«Sì, ma non è un problema fare i conti. È più complicato fare il disegno».
«Uh, davvero?».
«Davvero. Quante zone si possono avere intersecando quattro insiemi?».
«Compresa la zona esterna, 24, cioè 16».
«Bene, se provi a disegnarle nella maniera che ti verrebbe naturale, non ce la fai a farle tutte».
«Davvero?».
«Prova».
«No, no, mi fido… Ma quindi come si fa il disegno?».
«Ci sono varie possibilità; quella proposta da Venn è la seguente:».
«Venn? Quello dei diagrammi di Eulero-Venn?».
«Lui. Del resto, questi disegnini che stiamo facendo sono proprio quei diagrammi».
«Ah, ecco. Comunque quel disegno è proprio brutto, eh».
«Sono d'accordo. Se ne vuoi uno più bello devi passare in tre dimensioni e intersecare quattro sfere».
«Brr, no, no, va bene così».
«Facciamo i conti, allora?».
«Facciamoli. Con 16 zone mi sa che si complicheranno un po'».
«Un pochino, ma non tanto se capiamo come funziona il meccanismo. Ripensiamo al sistema dei gettoni che abbiamo utilizzato con due e tre insiemi».
«Ok».
«Allora, quando mi dicono che gli elementi di A sono tot, io conto tante zone: riesci a elencarle tutte?».
«Credo di sì, sono tutte le combinazioni in cui compare A e non il suo complementare. Eccole qua:».
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D.
«Bene, sono loro. Metterai dunque un gettone in ognuna di queste; quando dovrai tener conto di B metterai altri 8 gettoni in altrettante zone, tutte quelle che corrispondono a combinazioni in cui compare B e non il suo complementare».
«Stessa cosa per C e per D».
«Esatto. Ora prendo una combinazione a caso, per esempio questa: A∩B∩C∩D. Sai dirmi quanti gettoni avrà?».
«Uhm, direi due: uno che viene messo quando conto gli elementi di A, e uno per gli elementi di D».
«Benissimo. Due gettoni sono però troppi, ne dovremo poi togliere uno».
«Come abbiamo fatto l'altra volta».
«Sì, e come l'altra volta, però, dobbiamo stare attenti. Se sottraiamo gli elementi di A∩D, perché li abbiamo contati due volte, sottraiamo un gettone a tutte queste zone:».
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D.
«Giusto. E allora come si fa?».
«E allora si ripresenta il problema di prima: se sottraiamo troppo, dobbiamo tornare ad aggiungere».
«Ah-ha! Ogni volta ci riconduciamo al caso precedente».
«Esatto. Prima sommiamo gli elementi dei quattro insiemi, poi sottraiamo gli elementi che stanno nelle intersezioni di due insiemi, poi riaggiungiamo gli elementi che stanno nelle intersezioni di tre insiemi, e infine sottraiamo gli elementi che stanno nell'intersezione di tutti e quattro».
«Ho capito, provo a scrivere la formula:».
|A∪B∪C∪D| =
= |A| + |B| + |C| + |D|
-|A∩B| - |A∩C| - |A∩D| - |B∩C| - |B∩D| - |C∩D|
+|A∩B∩C| + |A∩B∩D| + |A∩C∩D| + |B∩C∩D|
-|A∩B∩C∩D|.
«Benissimo. Ora hai anche capito come si generalizza a un numero qualsiasi di elementi: si ripete il procedimento sempre alla stessa maniera. Questa regola viene detta principio di inclusione-esclusione, e viene utilizzata per risolvere molti problemi».
«Per esempio?».
«Per esempio questo: sapendo che ci sono 168 numeri primi minori di 1000, quanti sono i numeri primi da ingegnere minori di 1000?».
«Cosa sono i numeri primi da ingegnere?».
«Sono numeri compositi ma non divisibili per 2, per 3 e per 5. Tipo 49».
mercoledì 23 ottobre 2013
Inclusione—esclusione, parte 2: con tre le cose si complicano
«Nella solita classe abbiamo, questa volta, 10 studenti che giocano a pallavolo, 11 che suonano la chitarra e 9 che fanno parte del gruppo teatrale».
«Sì, vabbé, te la sogni una classe così».
«Ok, ok, è un esempio. Ogni riferimento con la realtà è assolutamente casuale».
«Va bene. Allora, ci saranno studenti che giocano a pallavolo e suonano la chitarra, ad esempio, altri che giocano e fanno teatro, e così via».
«Infatti, abbiamo varie possibilità. Quante?».
«Uhm, aspetta che le conto».
«Contale con l'idea di poter poi generalizzare in futuro».
«Non credo di saperlo fare».
«Cominciamo col dare un nome agli insiemi: A sono i pallavolisti, B i chitarristi e C gli attori».
«Va bene».
«Se facciamo un disegnino con gli insiemi, quante zone si creeranno?».
«Aspetta che le conto».
«Contale con l'idea di poter poi generalizzare in futuro».
«Ma allora è un vizio!».
«Eh, sì. Dai, prova».
«Uff. Allora, parto dal centro, c'è la zona in comune ai tre insiemi».
«Come la indichiamo?».
«Con A∩B∩C».
«Perfetto. Poi?».
«Poi ci saranno quelli che fanno due attività».
«Cosa significa? Almeno due, al più due, esattamente due?».
«Mamma mia quanto siete pignoli voi Veri Matematici! Ci sono quelli che fanno esattamente due attività, ok?».
«Bene, e come li indichiamo?».
«Mh, quelli che giocano a pallavolo e suonano la chitarra potremmo indicarli con A∩B, no?».
«No, con quel simbolo comprendi anche quelli che giocano a pallavolo, suonano la chitarra e eventualmente fanno teatro».
«Ah, allora dovrei escludere C da A∩B, ma come faccio?».
«Escludere C significa prendere gli elementi che non stanno in C, cioè che stanno fuori da C».
«Se non sbaglio, stiamo parlando dell'insieme complementare di C, vero?».
«Esatto: lo indichiamo con C».
«Ah, ecco. Allora l'insieme di quelli che giocano a pallavolo e suonano la chitarra diventa A∩B∩C».
«Molto bene. Come indichiamo gli altri insiemi composti da studenti che fanno esattamente due attività?».
«Saranno questi: A∩B∩C e A∩B∩C».
«Benissimo. Poi ci saranno gli insiemi che contengono studenti che svolgono una sola attività».
«Cioè pallavolo e non chitarra e non teatro, oppure chitarra e non pallavolo e non teatro, oppure teatro e non chitarra e non pallavolo: ho capito! In simboli è molto facile:».
A∩B∩C,
A∩B∩C,
A∩B∩C.
«Ottimo. Ora facciamo un riassunto: abbiamo tre lettere, A, B e C, e le loro negazioni A, B e C. Possiamo combinarle come vogliamo, purché compaiano tutte, o negate o non negate».
«In sostanza, abbiamo queste possibilità:».
A∩B∩C,
A∩B∩C,
A∩B∩C,
A∩B∩C,
A∩B∩C,
A∩B∩C,
A∩B∩C,
A∩B∩C.
«Molto bene. Ah, cosa rappresenta l'ultima possibilità?».
«Uhm… sì, ci sono! Sono gli studenti lavativi, quelli che non fanno nulla».
«Dai, diciamo che sono quelli che studiano».
«Ecco, diciamo così».
«Ma eravamo rimasti all'idea di generalizzare: quante combinazioni abbiamo?».
«Allora, per ogni lettera abbiamo due possibilità: possiamo negarla oppure no. Quindi due possibilità per la prima lettera, due per la seconda, due per la terza, totale 23, cioè 8».
«Ottimo. Se disegniamo il diagramma con tre insiemi, contiamo 8 zone. In realtà una zona è quella esterna a tutti e tre gli insiemi, le altre sette sono invece interne almeno a uno di loro. Il problema, come nel caso precedente con due insiemi, è che quando diciamo che 10 studenti giocano a pallavolo, prendiamo in considerazione sia quelli che davvero giocano solo a pallavolo e non fanno altro, sia quelli che svolgono due attività, sia quelli che le svolgono tutte e tre».
«Quindi, se usiamo l'idea dei gettoni come l'altra volta, ne mettiamo tanti».
«Quanti?».
«Vediamo… uno per ogni combinazione dei tre insiemi che contiene A non negato? Sarebbero queste:».
A∩B∩C,
A∩B∩C,
A∩B∩C,
A∩B∩C.
«Esatto, ecco il disegnino».
«Quindi, vediamo se ho capito bene, sommando i 10 studenti sportivi, gli 11 musicisti e i 9 attori conto due volte le zone in comune».
«Non esattamente: c'è una zona che conti tre volte, perché fa parte sia di A, sia di B e anche di C».
«Ah, è vero! Non è come con due insiemi, qui c'è anche la zona che abbiamo indicato con A∩B∩C».
«Sì, ecco la figurina completa:».
«E quindi come facciamo?».
«Se facciamo come prima, contando gli elementi di A, quelli di B e quelli di C, e sottraendo poi gli elementi di A∩B, quelli di B∩C e quelli di A∩C, commettiamo un errore».
«Già, abbiamo tolto completamente la zona interna, quella dell'intersezione comune: se facciamo tre sottrazioni togliamo tutti e tre i gettoni, dovremmo invece lasciarne uno».
«Perfetto, vorrà dire che lo riaggiungeremo alla fine».
«Cioè dobbiamo fare una cosa del genere?».
|A∪B∪C| = |A| + |B| + |C| - |A∩B∩C| - |A∩B∩C| - |A∩B∩C| + |A∩B∩C|.
«Proprio così. Quindi, per completare l'esempio con cui abbiamo iniziato: abbiamo 10 pallavolisti, 11 chitarristi e 9 attori, 3 studenti che giocano a pallavolo e fanno gli attori, 4 studenti che giocano a pallavolo e suonano la chitarra, 5 studenti che suonano la chitarra e fanno gli attori. Infine, abbiamo 2 studenti che svolgono tutte e tre le attività. Quanti studenti in tutto, dunque?».
«Allora, ce ne sono 10 + 11 + 9 - 3 - 4 - 5 + 2, cioè 20. Ah, sono sempre quella meravigliosa classe di 20 studenti».
«Sì, continuiamo a sognare per un po'».
«Sì, vabbé, te la sogni una classe così».
«Ok, ok, è un esempio. Ogni riferimento con la realtà è assolutamente casuale».
«Va bene. Allora, ci saranno studenti che giocano a pallavolo e suonano la chitarra, ad esempio, altri che giocano e fanno teatro, e così via».
«Infatti, abbiamo varie possibilità. Quante?».
«Uhm, aspetta che le conto».
«Contale con l'idea di poter poi generalizzare in futuro».
«Non credo di saperlo fare».
«Cominciamo col dare un nome agli insiemi: A sono i pallavolisti, B i chitarristi e C gli attori».
«Va bene».
«Se facciamo un disegnino con gli insiemi, quante zone si creeranno?».
«Aspetta che le conto».
«Contale con l'idea di poter poi generalizzare in futuro».
«Ma allora è un vizio!».
«Eh, sì. Dai, prova».
«Uff. Allora, parto dal centro, c'è la zona in comune ai tre insiemi».
«Come la indichiamo?».
«Con A∩B∩C».
«Perfetto. Poi?».
«Poi ci saranno quelli che fanno due attività».
«Cosa significa? Almeno due, al più due, esattamente due?».
«Mamma mia quanto siete pignoli voi Veri Matematici! Ci sono quelli che fanno esattamente due attività, ok?».
«Bene, e come li indichiamo?».
«Mh, quelli che giocano a pallavolo e suonano la chitarra potremmo indicarli con A∩B, no?».
«No, con quel simbolo comprendi anche quelli che giocano a pallavolo, suonano la chitarra e eventualmente fanno teatro».
«Ah, allora dovrei escludere C da A∩B, ma come faccio?».
«Escludere C significa prendere gli elementi che non stanno in C, cioè che stanno fuori da C».
«Se non sbaglio, stiamo parlando dell'insieme complementare di C, vero?».
«Esatto: lo indichiamo con C».
«Ah, ecco. Allora l'insieme di quelli che giocano a pallavolo e suonano la chitarra diventa A∩B∩C».
«Molto bene. Come indichiamo gli altri insiemi composti da studenti che fanno esattamente due attività?».
«Saranno questi: A∩B∩C e A∩B∩C».
«Benissimo. Poi ci saranno gli insiemi che contengono studenti che svolgono una sola attività».
«Cioè pallavolo e non chitarra e non teatro, oppure chitarra e non pallavolo e non teatro, oppure teatro e non chitarra e non pallavolo: ho capito! In simboli è molto facile:».
A∩B∩C,
A∩B∩C,
A∩B∩C.
«Ottimo. Ora facciamo un riassunto: abbiamo tre lettere, A, B e C, e le loro negazioni A, B e C. Possiamo combinarle come vogliamo, purché compaiano tutte, o negate o non negate».
«In sostanza, abbiamo queste possibilità:».
A∩B∩C,
A∩B∩C,
A∩B∩C,
A∩B∩C,
A∩B∩C,
A∩B∩C,
A∩B∩C,
A∩B∩C.
«Molto bene. Ah, cosa rappresenta l'ultima possibilità?».
«Uhm… sì, ci sono! Sono gli studenti lavativi, quelli che non fanno nulla».
«Dai, diciamo che sono quelli che studiano».
«Ecco, diciamo così».
«Ma eravamo rimasti all'idea di generalizzare: quante combinazioni abbiamo?».
«Allora, per ogni lettera abbiamo due possibilità: possiamo negarla oppure no. Quindi due possibilità per la prima lettera, due per la seconda, due per la terza, totale 23, cioè 8».
«Ottimo. Se disegniamo il diagramma con tre insiemi, contiamo 8 zone. In realtà una zona è quella esterna a tutti e tre gli insiemi, le altre sette sono invece interne almeno a uno di loro. Il problema, come nel caso precedente con due insiemi, è che quando diciamo che 10 studenti giocano a pallavolo, prendiamo in considerazione sia quelli che davvero giocano solo a pallavolo e non fanno altro, sia quelli che svolgono due attività, sia quelli che le svolgono tutte e tre».
«Quindi, se usiamo l'idea dei gettoni come l'altra volta, ne mettiamo tanti».
«Quanti?».
«Vediamo… uno per ogni combinazione dei tre insiemi che contiene A non negato? Sarebbero queste:».
A∩B∩C,
A∩B∩C,
A∩B∩C,
A∩B∩C.
«Esatto, ecco il disegnino».
«Quindi, vediamo se ho capito bene, sommando i 10 studenti sportivi, gli 11 musicisti e i 9 attori conto due volte le zone in comune».
«Non esattamente: c'è una zona che conti tre volte, perché fa parte sia di A, sia di B e anche di C».
«Ah, è vero! Non è come con due insiemi, qui c'è anche la zona che abbiamo indicato con A∩B∩C».
«Sì, ecco la figurina completa:».
«E quindi come facciamo?».
«Se facciamo come prima, contando gli elementi di A, quelli di B e quelli di C, e sottraendo poi gli elementi di A∩B, quelli di B∩C e quelli di A∩C, commettiamo un errore».
«Già, abbiamo tolto completamente la zona interna, quella dell'intersezione comune: se facciamo tre sottrazioni togliamo tutti e tre i gettoni, dovremmo invece lasciarne uno».
«Perfetto, vorrà dire che lo riaggiungeremo alla fine».
«Cioè dobbiamo fare una cosa del genere?».
|A∪B∪C| = |A| + |B| + |C| - |A∩B∩C| - |A∩B∩C| - |A∩B∩C| + |A∩B∩C|.
«Proprio così. Quindi, per completare l'esempio con cui abbiamo iniziato: abbiamo 10 pallavolisti, 11 chitarristi e 9 attori, 3 studenti che giocano a pallavolo e fanno gli attori, 4 studenti che giocano a pallavolo e suonano la chitarra, 5 studenti che suonano la chitarra e fanno gli attori. Infine, abbiamo 2 studenti che svolgono tutte e tre le attività. Quanti studenti in tutto, dunque?».
«Allora, ce ne sono 10 + 11 + 9 - 3 - 4 - 5 + 2, cioè 20. Ah, sono sempre quella meravigliosa classe di 20 studenti».
«Sì, continuiamo a sognare per un po'».
lunedì 21 ottobre 2013
Inclusione—esclusione, parte 1: con due è facile
«In una classe ci sono dieci studenti maschi e dieci femmine».
«Beati loro».
«Chi?».
«Tutti! Gli studenti, i professori…».
«Eh, vero. Comunque: quanti studenti ci sono?».
«Venti, naturalmente, che domanda è?».
«Era una domanda di riscaldamento».
«Vai con le domande serie, allora».
«In una classe ci sono sei studenti che hanno avuto il debito in matematica e cinque che l'hanno avuto in italiano. Quanti studenti hanno avuto almeno un debito in italiano o in matematica?».
«Mh, non devo fare sei più cinque, ci sono anche i somari che hanno avuto il debito sia in italiano che in matematica!».
«Quindi?».
«Quindi devi dirmi quanti sono questi somari».
«Sono due».
«Ok, allora ci sono nove studenti indebitati».
«Bene, possiamo visualizzare la situazione con un disegnino:».
«Uh, gli insiemi».
«Sì, loro. Ci sono 6 elementi nell'insieme di sinistra…».
«…compresa la parte in comune con quello di destra».
«Esatto; e ci sono cinque elementi in quello di destra, compresa la parte in comune con quello di sinistra».
«E 2 nella parte in comune».
«Quindi qual è l'operazione da fare per calcolare il totale degli studenti?».
«Dobbiamo fare 6 + 5 - 2».
«Giusto. Sai spiegare in modo convincente perché si toglie 2?».
«Perché quando calcoliamo 6 + 5 teniamo conto della zona in comune per due volte, mentre dovremmo contarla una volta sola: la zona in comune non deve contare doppio, o la inseriamo nell'insieme di sinistra, o la inseriamo in quello di destra, ma non in entrambi».
«Molto bene. È come se noi segnassimo con un gettone le parti degli insiemi che stiamo contando: quando utilizziamo il 6, teniamo conto di queste due zone:».
«Ah, ho capito: quando utilizziamo il 5 teniamo conto della zona di destra e, nuovamente, della zona centrale. In questo modo la zona centrale ha due gettoni:».
«Proprio così: ecco che si capisce il motivo per cui dobbiamo sottrarre la parte centrale».
«Perché l'abbiamo contata due volte!».
«Già. Ora, se chiamiamo A e B i due insiemi, riusciamo a scrivere una formula per il calcolo del numero totale degli elementi contenuti nella loro unione?».
«Aspetta, dunque: unione è tutto ciò che contengono gli insiemi, senza distinzione, vero?».
«Sì, è la parte colorata, non importa di quale colore. I Veri Matematici dicono che l'unione dei due insiemi (che si scrive A∪B) contiene gli elementi che stanno in A oppure in B (dove oppure non è da intendersi in senso esclusivo, va bene qualsiasi elemento appartenga ad almeno uno dei due insiemi)».
«Vero, mi ricordo. Invece l'intersezione è la parte in comune, giusto?».
«Esatto. L'intersezione A∩B tra due insiemi contiene gli elementi che appartengono all'insieme A e all'insieme B».
«Ok, allora direi che la formula sia… uhm, come indico il numero di elementi di un insieme?».
«Puoi usare questo simbolo: |A|. Ricordi che abbiamo parlato per tanto tempo di cardinalità di un insieme, vero?».
«Come potrei dimenticare?».
«Ecco, bene. Allora, come scrivi la formula?».
«|A∪B| = |A| + |B| - |A∩B|».
«Perfetto».
«E adesso?».
«Adesso lo facciamo con tre insiemi».
«Beati loro».
«Chi?».
«Tutti! Gli studenti, i professori…».
«Eh, vero. Comunque: quanti studenti ci sono?».
«Venti, naturalmente, che domanda è?».
«Era una domanda di riscaldamento».
«Vai con le domande serie, allora».
«In una classe ci sono sei studenti che hanno avuto il debito in matematica e cinque che l'hanno avuto in italiano. Quanti studenti hanno avuto almeno un debito in italiano o in matematica?».
«Mh, non devo fare sei più cinque, ci sono anche i somari che hanno avuto il debito sia in italiano che in matematica!».
«Quindi?».
«Quindi devi dirmi quanti sono questi somari».
«Sono due».
«Ok, allora ci sono nove studenti indebitati».
«Bene, possiamo visualizzare la situazione con un disegnino:».
«Uh, gli insiemi».
«Sì, loro. Ci sono 6 elementi nell'insieme di sinistra…».
«…compresa la parte in comune con quello di destra».
«Esatto; e ci sono cinque elementi in quello di destra, compresa la parte in comune con quello di sinistra».
«E 2 nella parte in comune».
«Quindi qual è l'operazione da fare per calcolare il totale degli studenti?».
«Dobbiamo fare 6 + 5 - 2».
«Giusto. Sai spiegare in modo convincente perché si toglie 2?».
«Perché quando calcoliamo 6 + 5 teniamo conto della zona in comune per due volte, mentre dovremmo contarla una volta sola: la zona in comune non deve contare doppio, o la inseriamo nell'insieme di sinistra, o la inseriamo in quello di destra, ma non in entrambi».
«Molto bene. È come se noi segnassimo con un gettone le parti degli insiemi che stiamo contando: quando utilizziamo il 6, teniamo conto di queste due zone:».
«Ah, ho capito: quando utilizziamo il 5 teniamo conto della zona di destra e, nuovamente, della zona centrale. In questo modo la zona centrale ha due gettoni:».
«Proprio così: ecco che si capisce il motivo per cui dobbiamo sottrarre la parte centrale».
«Perché l'abbiamo contata due volte!».
«Già. Ora, se chiamiamo A e B i due insiemi, riusciamo a scrivere una formula per il calcolo del numero totale degli elementi contenuti nella loro unione?».
«Aspetta, dunque: unione è tutto ciò che contengono gli insiemi, senza distinzione, vero?».
«Sì, è la parte colorata, non importa di quale colore. I Veri Matematici dicono che l'unione dei due insiemi (che si scrive A∪B) contiene gli elementi che stanno in A oppure in B (dove oppure non è da intendersi in senso esclusivo, va bene qualsiasi elemento appartenga ad almeno uno dei due insiemi)».
«Vero, mi ricordo. Invece l'intersezione è la parte in comune, giusto?».
«Esatto. L'intersezione A∩B tra due insiemi contiene gli elementi che appartengono all'insieme A e all'insieme B».
«Ok, allora direi che la formula sia… uhm, come indico il numero di elementi di un insieme?».
«Puoi usare questo simbolo: |A|. Ricordi che abbiamo parlato per tanto tempo di cardinalità di un insieme, vero?».
«Come potrei dimenticare?».
«Ecco, bene. Allora, come scrivi la formula?».
«|A∪B| = |A| + |B| - |A∩B|».
«Perfetto».
«E adesso?».
«Adesso lo facciamo con tre insiemi».
venerdì 4 ottobre 2013
Il problema del carro armato tedesco
C'era un mio amico che voleva avviare una piccola azienda in proprio. Si era organizzato per tutta la burocrazia (suppongo poca, essendo lui l'unico titolare e dipendente) e, una volta pronto per lavorare, aveva fatto mettere un po' di pubblicità sulla sua auto, sulla quale aveva anche appiccicato un piccolo adesivo con un numero: 2.
Perché 2, gli domandai. Perché, mi rispose, se metto 1 sembro un poveraccio, se metto 2 vuol dire che ho una azienda bene avviata con almeno due auto, e magari anche qualcuna di più, vai a sapere.
Niente da dire, di fronte al genio ci si può solo inchinare.
Mi è venuta in mente questa storiella dopo aver letto l'ultimo what if di xkcd, quello in cui si cerca di dare una risposta alla domanda seguente: quanto sarebbero lunghe le nostre timeline di twitter se si potessero estendere lungo lo schermo in entrambe le direzioni?
In un futuro più o meno remoto, dice Randall Munroe, tutti gli account che seguiamo su twitter smetteranno di scrivere. Questo è abbastanza ovvio, (anche se account come quello del Big Ben potrebbero andare avanti per tanto); stabilire quando succederà, però, non è facile.
In inglese questo tipo di stima viene chiamato German Tank Problem, perché è un problema che si è presentato realmente durante la seconda guerra mondiale quando si è trattato di organizzare lo sbarco in Normandia: gli alleati, avendo notato la presenza del carro armato Panther negli eserciti tedeschi, si preoccuparono un po', perché erano sicuri che i loro Sherman si sarebbero comportati bene in eventuali scontri con carri tedeschi di vecchia generazione, ma questi Panther sembravano un po' troppo veloci e potenti.
Insomma, quanti Panther hanno questi tedeschi?, si domandarono i generali alleati.
Ah, saperlo!, fu la risposta un po' troppo evasiva.
Al che si decise di risolvere il problema seguendo due strade: lo spionaggio e la matematica. Sullo spionaggio c'è poco da dire, funziona più o meno in questo modo: trova qualcuno che sappia e usa qualunque mezzo per ottenere l'informazione. Sulla matematica invece diciamo qualcosa di più.
Alcuni pezzi con i quali venivano costruiti i Panther avevano dei numeri di serie: il cambio, il telaio, il motore e le ruote. Numeri di serie progressivi, come le auto fittizie del mio amico.
E quindi, ecco il problema: abbiamo catturato il Panther numero 60: quanti ce ne sono ancora in giro?
Citando xkcd, diciamo che la risposta ha a che fare con il problema di statistica più discusso su internet: usiamo l'approccio frequentista o bayesiano? In ogni caso, come ragioniamo?
Una prima, facile, considerazione: ci sono almeno 60 carri armati: la probabilità che il numero dei carri sia un valore compreso tra 0 e 59 è nulla.
Andiamo avanti: supponiamo che esistano N carri; la probabilità di incontrare il numero 60 è naturalmente di 1/N (ovviamente questa è la probabilità di incontrare un certo carro, non importa quale sia il suo numero di serie), se N è maggiore di 60, altrimenti la probabilità è zero. Quindi la probabilità massima la abbiamo quando N = 60.
Naturalmente non abbiamo la certezza che il numero sia proprio quello (come ci dice anche l'intuizione). Come possiamo fare una stima migliore? Sarebbe opportuno vedere qualche altro carro.
Facciamo un esempio numerico, per poi arrivare alla formula. Supponiamo che ci siano N = 200 carri, e supponiamo di averne visti 3. Supponiamo anche di essere stati fortunati, e di aver trovato 3 numeri di serie equidistanti tra di loro: 50, 100 e 150. Se il primo numero fosse 0, avremmo quindi questa situazione:
Se dunque m è il massimo numero di serie che abbiamo trovato (150) e k è il numero di carri ispezionati (3), possiamo stimare il valore di N calcolando la distanza m/k tra un numero di serie e il successivo (150/3 = 50) e sommandola a m.
In realtà, però, se vogliamo contare i carri armati non possiamo partire da 0: immaginiamo che il primo numero di serie sia 1. Per mantenere la simmetria nella suddivisione in k parti uguali, supponiamo allora che l'ultimo termine sia N+1. Insomma, invece di fare i conti sull'intervallo 1,…, N li facciamo sull'intervallo 0,…, N+1. La formula che abbiamo trovato sopra per stimare il valore di N stima, in realtà, N+1. Dunque sottraiamo 1 e siamo a posto. Il risultato è questo:
N = m + m/k - 1.
Se, quindi, abbiamo catturato 5 carri, e il numero di serie maggiore che abbiamo visto è 60, la stima che facciamo sul totale è N = 60 + 60/5 - 1 = 71.
Ho fatto una simulazione per verificare il tutto: ho imposto N = 200, poi ho cominciato a estrarre numeri casuali (cioè numeri di serie di carri) da 1 a 200, e ho calcolato il valore presunto di N man mano che il numero di carri aumentava. Ecco qua:
Si vede che, quando capita un numero fortunato, la stima migliora notevolmente, e verso i 50 carri è ormai indistinguibile dal valore reale (50 su 200 sono tanti, sì, ma anche con numeri notevolmente inferiori si possono avere stime molto buone: se devi sbarcare in Normandia un conto è sapere che ci sarà un qualche centinaio di carri, un altro è sapere che ce ne saranno a migliaia).
Questo è quello che fanno i frequentisti. I bayesiani, invece, ragionano in modo diverso (dopo aver litigato un po' con i frequentisti). Quando trovano il primo carro armato fanno una prima stima del numero totale dei carri; più precisamente, assegnano un valore di probabilità a tutti i numeri da 1 a un certo valore massimo sufficientemente alto. Ogni volta che trovano un nuovo carro ricalcolano tutta la distribuzione di probabilità, tenendo conto delle nuove informazioni.
Ecco un grafico (i conti no, non li metto, sono complicati, però si può dare un'occhiata qua, a pagina 102, dove viene segnalato anche un programma che fa tutto da solo, programma che ho leggermente modificato per produrre il grafico qua sotto):
Va letto in questo modo: la curva viola (quella più a sinistra) è la stima del numero massimo di carri fatta utilizzando un solo numero di serie. Le curve più a destra sono state ottenute aggiungendo nuovi numeri di serie, fino a 10. Si vede che la distribuzione di probabilità diventa più stretta e più alta, cioè più precisa.
Ecco come si presenta la distribuzione dopo 20 estrazioni:
Un'ultima considerazione prima di concludere: come ha funzionato l'altro metodo, quello dello spionaggio, nella realtà?
Bé, dopo la guerra molte informazioni segrete sono diventate pubbliche, tra cui anche il numero di carri prodotti nei vari mesi della guerra. Per esempio, nel giugno 1940 l'analisi statistica ha stimato una produzione di 169 unità, mentre lo spionaggio pensava che ne venissero costruiti 1000. Il dato reale era 122. L'anno dopo, nel giugno 1941, la statistica fornì una stima di 244 carri, contrapposta al dato fornito dallo spionaggio di 1550 unità. Il dato reale fu 271. Infine, nell'agosto del 1942 la statistica stimò una produzione di 327 carri, le spie invece una produzione di 1550, e il dato reale era 342.
Credo che ci sia una morale, in questo.
Perché 2, gli domandai. Perché, mi rispose, se metto 1 sembro un poveraccio, se metto 2 vuol dire che ho una azienda bene avviata con almeno due auto, e magari anche qualcuna di più, vai a sapere.
Niente da dire, di fronte al genio ci si può solo inchinare.
Mi è venuta in mente questa storiella dopo aver letto l'ultimo what if di xkcd, quello in cui si cerca di dare una risposta alla domanda seguente: quanto sarebbero lunghe le nostre timeline di twitter se si potessero estendere lungo lo schermo in entrambe le direzioni?
In un futuro più o meno remoto, dice Randall Munroe, tutti gli account che seguiamo su twitter smetteranno di scrivere. Questo è abbastanza ovvio, (anche se account come quello del Big Ben potrebbero andare avanti per tanto); stabilire quando succederà, però, non è facile.
In inglese questo tipo di stima viene chiamato German Tank Problem, perché è un problema che si è presentato realmente durante la seconda guerra mondiale quando si è trattato di organizzare lo sbarco in Normandia: gli alleati, avendo notato la presenza del carro armato Panther negli eserciti tedeschi, si preoccuparono un po', perché erano sicuri che i loro Sherman si sarebbero comportati bene in eventuali scontri con carri tedeschi di vecchia generazione, ma questi Panther sembravano un po' troppo veloci e potenti.
Insomma, quanti Panther hanno questi tedeschi?, si domandarono i generali alleati.
Ah, saperlo!, fu la risposta un po' troppo evasiva.
Al che si decise di risolvere il problema seguendo due strade: lo spionaggio e la matematica. Sullo spionaggio c'è poco da dire, funziona più o meno in questo modo: trova qualcuno che sappia e usa qualunque mezzo per ottenere l'informazione. Sulla matematica invece diciamo qualcosa di più.
Alcuni pezzi con i quali venivano costruiti i Panther avevano dei numeri di serie: il cambio, il telaio, il motore e le ruote. Numeri di serie progressivi, come le auto fittizie del mio amico.
E quindi, ecco il problema: abbiamo catturato il Panther numero 60: quanti ce ne sono ancora in giro?
Citando xkcd, diciamo che la risposta ha a che fare con il problema di statistica più discusso su internet: usiamo l'approccio frequentista o bayesiano? In ogni caso, come ragioniamo?
Una prima, facile, considerazione: ci sono almeno 60 carri armati: la probabilità che il numero dei carri sia un valore compreso tra 0 e 59 è nulla.
Andiamo avanti: supponiamo che esistano N carri; la probabilità di incontrare il numero 60 è naturalmente di 1/N (ovviamente questa è la probabilità di incontrare un certo carro, non importa quale sia il suo numero di serie), se N è maggiore di 60, altrimenti la probabilità è zero. Quindi la probabilità massima la abbiamo quando N = 60.
Naturalmente non abbiamo la certezza che il numero sia proprio quello (come ci dice anche l'intuizione). Come possiamo fare una stima migliore? Sarebbe opportuno vedere qualche altro carro.
Facciamo un esempio numerico, per poi arrivare alla formula. Supponiamo che ci siano N = 200 carri, e supponiamo di averne visti 3. Supponiamo anche di essere stati fortunati, e di aver trovato 3 numeri di serie equidistanti tra di loro: 50, 100 e 150. Se il primo numero fosse 0, avremmo quindi questa situazione:
Se dunque m è il massimo numero di serie che abbiamo trovato (150) e k è il numero di carri ispezionati (3), possiamo stimare il valore di N calcolando la distanza m/k tra un numero di serie e il successivo (150/3 = 50) e sommandola a m.
In realtà, però, se vogliamo contare i carri armati non possiamo partire da 0: immaginiamo che il primo numero di serie sia 1. Per mantenere la simmetria nella suddivisione in k parti uguali, supponiamo allora che l'ultimo termine sia N+1. Insomma, invece di fare i conti sull'intervallo 1,…, N li facciamo sull'intervallo 0,…, N+1. La formula che abbiamo trovato sopra per stimare il valore di N stima, in realtà, N+1. Dunque sottraiamo 1 e siamo a posto. Il risultato è questo:
N = m + m/k - 1.
Se, quindi, abbiamo catturato 5 carri, e il numero di serie maggiore che abbiamo visto è 60, la stima che facciamo sul totale è N = 60 + 60/5 - 1 = 71.
Ho fatto una simulazione per verificare il tutto: ho imposto N = 200, poi ho cominciato a estrarre numeri casuali (cioè numeri di serie di carri) da 1 a 200, e ho calcolato il valore presunto di N man mano che il numero di carri aumentava. Ecco qua:
Si vede che, quando capita un numero fortunato, la stima migliora notevolmente, e verso i 50 carri è ormai indistinguibile dal valore reale (50 su 200 sono tanti, sì, ma anche con numeri notevolmente inferiori si possono avere stime molto buone: se devi sbarcare in Normandia un conto è sapere che ci sarà un qualche centinaio di carri, un altro è sapere che ce ne saranno a migliaia).
Questo è quello che fanno i frequentisti. I bayesiani, invece, ragionano in modo diverso (dopo aver litigato un po' con i frequentisti). Quando trovano il primo carro armato fanno una prima stima del numero totale dei carri; più precisamente, assegnano un valore di probabilità a tutti i numeri da 1 a un certo valore massimo sufficientemente alto. Ogni volta che trovano un nuovo carro ricalcolano tutta la distribuzione di probabilità, tenendo conto delle nuove informazioni.
Ecco un grafico (i conti no, non li metto, sono complicati, però si può dare un'occhiata qua, a pagina 102, dove viene segnalato anche un programma che fa tutto da solo, programma che ho leggermente modificato per produrre il grafico qua sotto):
Va letto in questo modo: la curva viola (quella più a sinistra) è la stima del numero massimo di carri fatta utilizzando un solo numero di serie. Le curve più a destra sono state ottenute aggiungendo nuovi numeri di serie, fino a 10. Si vede che la distribuzione di probabilità diventa più stretta e più alta, cioè più precisa.
Ecco come si presenta la distribuzione dopo 20 estrazioni:
Un'ultima considerazione prima di concludere: come ha funzionato l'altro metodo, quello dello spionaggio, nella realtà?
Bé, dopo la guerra molte informazioni segrete sono diventate pubbliche, tra cui anche il numero di carri prodotti nei vari mesi della guerra. Per esempio, nel giugno 1940 l'analisi statistica ha stimato una produzione di 169 unità, mentre lo spionaggio pensava che ne venissero costruiti 1000. Il dato reale era 122. L'anno dopo, nel giugno 1941, la statistica fornì una stima di 244 carri, contrapposta al dato fornito dallo spionaggio di 1550 unità. Il dato reale fu 271. Infine, nell'agosto del 1942 la statistica stimò una produzione di 327 carri, le spie invece una produzione di 1550, e il dato reale era 342.
Credo che ci sia una morale, in questo.
Iscriviti a:
Post (Atom)