Come probabilmente avrete già letto qua e là in giro per l'internet, oggi è stato annunciato ufficialmente il lancio della collana Altramatematica, della casa editrice 40k Unofficial, un progetto di Bookrepublic.
Si tratta di una collana di ebook che parlano principalmente di matematica, fisica e informatica: non roba pesante, però. Il nome della casa editrice, 40k, dà un'idea delle dimensioni di ogni ebook: più o meno 40000 battute.
Anche il tono sarà leggero, perché tra gli autori sono gente strana: c'è il curatore della collana, .mau., con Matematica e infinito, c'è Peppe Liberti, con Più per meno diviso, ci saranno Paolo Alessandrini e i Rudi Mathematici.
Bé, tra qualche giorno ci sarò anche io.
Divertitevi.
giovedì 19 dicembre 2013
martedì 26 novembre 2013
La vita privata nell'epoca della sua riproducibilità tecnica
Si dice che nell'epoca di internet se uno vuole tenere per sé le sue faccende private non le deve mettere in rete. Bene, ora violerò questo saggio consiglio.
Sono un matematico estroverso, uno di quelli che quando parla con qualcuno guarda le scarpe dell'altro. Ho parlato, qui sul blog e anche sui socialini che frequento, di mia moglie, la Signora, che tra l'altro qui compare ancora come collaboratrice.
Bene, i fatti della vita (quelli, sì, rimangono privati) ci hanno portati ad allontanarci troppo. Ora lei non abita più con me.
Amici: non ce la farò a parlare a tutte le vostre scarpe, a spiegare e a raccontare. Portate pazienza. Un "come va?" e un pat-pat sono sempre graditi, comunque.
Amici elettronici: non ci siamo mai visti, ma visto che condividiamo una piccolissima parte delle nostre storie, ecco, ora sapete.
Studenti, colleghi: portate pazienza se dico cose strane o se sorrido meno.
C'è, comunque, una frase che rispecchia il mio modo di vivere e che mi guiderà ancora. È questa:
Tutto andrà bene, alla fine. Se non va bene, non è la fine.
Sono un matematico estroverso, uno di quelli che quando parla con qualcuno guarda le scarpe dell'altro. Ho parlato, qui sul blog e anche sui socialini che frequento, di mia moglie, la Signora, che tra l'altro qui compare ancora come collaboratrice.
Bene, i fatti della vita (quelli, sì, rimangono privati) ci hanno portati ad allontanarci troppo. Ora lei non abita più con me.
Amici: non ce la farò a parlare a tutte le vostre scarpe, a spiegare e a raccontare. Portate pazienza. Un "come va?" e un pat-pat sono sempre graditi, comunque.
Amici elettronici: non ci siamo mai visti, ma visto che condividiamo una piccolissima parte delle nostre storie, ecco, ora sapete.
Studenti, colleghi: portate pazienza se dico cose strane o se sorrido meno.
C'è, comunque, una frase che rispecchia il mio modo di vivere e che mi guiderà ancora. È questa:
Tutto andrà bene, alla fine. Se non va bene, non è la fine.
giovedì 14 novembre 2013
Sui pregiudizi concettuali, ovvero Newton che si ribalta nella tomba
«E, dunque, dato che l'ellisse, la parabola e l'iperbole si ottengono tutte sezionando un cono in vari modi, queste curve vengono dette coniche».
«Ma, prof, di fronte a un grafico che ne mostra solo una parte è difficile distinguerle, vero?».
«Eh, sì, si assomigliano molto. Per esempio, vi ricorderete dalla fisica che avete studiato al biennio che se prendete un sasso e lo lanciate, cadrà lungo una traiettoria parabolica[citation needed]».
«Uhm, può darsi».
«Ma sì, dai, una componente ha moto uniforme, l'altra moto uniformemente accelerato, la curva è una parabola, avrete pure calcolato la gittata, cose così».
«Ah, sì, è vero».
«Ecco, in realtà non è così. Se io faccio un disegnino non in scala, ecco… questa è la terra, questo è il sasso che cade da una torre altissima, la traiettoria in realtà è ellittica».
«Ah, ma allora abbiamo imparato cose sbagliate?».
«Ma no, in un mondo piatto in cui l'accelerazione di gravità è costante, la traiettoria è davvero parabolica. Se non lanciamo un sasso da un'altezza incredibile, ma ci limitiamo a quote normali, non riusciamo a distinguere la parabola dall'ellisse: si assomigliano molto. Se invece lanciamo il sasso da molto in alto e molto lontano potrebbe anche entrare in orbita, ad esempio».
«Uhm».
«Naturalmente se trascuriamo tutto ciò che possiamo, cioè se non consideriamo l'aria, ci mettiamo in una situazione ideale, eccetera. In teoria potremmo lanciare il sasso, girarci indietro, aspettare un po' e riprenderlo al volo. Il sasso è diventato un satellite. Per renderlo geostazionario, come i satelliti che usiamo per le trasmissioni televisive, dobbiamo invece portarlo molto distante dal centro della terra. Sapete come funzionano i satelliti geostazionari?».
«Sono fermi».
«Bé, diciamo che sono fermi rispetto a un osservatore che si trova sulla terra, in realtà ruotano insieme alla terra».
«No, no, prof, io volevo dire che sono proprio fermi».
«Ma no! Scusa, come fanno a stare fermi?».
«Eh, sono lontani, dove non c'è gravità, stanno fermi».
«…».
«Prof, perché mi puntina?[1] Cosa ho detto?».
«Ma i satelliti non sono fermi! Se fossero fermi cadrebbero, no?».
«No, prof, non cadono perché non c'è gravità».
«Ma come fa a non esserci gravità?».
«Eh, oh, non c'è aria, non c'è gravità, scusi».
«NOAOAOAO».
«No?».
«Proprio no! Secondo te per mettere un satellite in orbita si spara un missile in verticale, si arriva alla posizione giusta, ci si ferma, si molla lì il satellite e si torna indietro?».
«Certo, c'è un altro modo?».
Ecco.
«Ma, prof, di fronte a un grafico che ne mostra solo una parte è difficile distinguerle, vero?».
«Eh, sì, si assomigliano molto. Per esempio, vi ricorderete dalla fisica che avete studiato al biennio che se prendete un sasso e lo lanciate, cadrà lungo una traiettoria parabolica[citation needed]».
«Uhm, può darsi».
«Ma sì, dai, una componente ha moto uniforme, l'altra moto uniformemente accelerato, la curva è una parabola, avrete pure calcolato la gittata, cose così».
«Ah, sì, è vero».
«Ecco, in realtà non è così. Se io faccio un disegnino non in scala, ecco… questa è la terra, questo è il sasso che cade da una torre altissima, la traiettoria in realtà è ellittica».
«Ah, ma allora abbiamo imparato cose sbagliate?».
«Ma no, in un mondo piatto in cui l'accelerazione di gravità è costante, la traiettoria è davvero parabolica. Se non lanciamo un sasso da un'altezza incredibile, ma ci limitiamo a quote normali, non riusciamo a distinguere la parabola dall'ellisse: si assomigliano molto. Se invece lanciamo il sasso da molto in alto e molto lontano potrebbe anche entrare in orbita, ad esempio».
«Uhm».
«Naturalmente se trascuriamo tutto ciò che possiamo, cioè se non consideriamo l'aria, ci mettiamo in una situazione ideale, eccetera. In teoria potremmo lanciare il sasso, girarci indietro, aspettare un po' e riprenderlo al volo. Il sasso è diventato un satellite. Per renderlo geostazionario, come i satelliti che usiamo per le trasmissioni televisive, dobbiamo invece portarlo molto distante dal centro della terra. Sapete come funzionano i satelliti geostazionari?».
«Sono fermi».
«Bé, diciamo che sono fermi rispetto a un osservatore che si trova sulla terra, in realtà ruotano insieme alla terra».
«No, no, prof, io volevo dire che sono proprio fermi».
«Ma no! Scusa, come fanno a stare fermi?».
«Eh, sono lontani, dove non c'è gravità, stanno fermi».
«…».
«Prof, perché mi puntina?[1] Cosa ho detto?».
«Ma i satelliti non sono fermi! Se fossero fermi cadrebbero, no?».
«No, prof, non cadono perché non c'è gravità».
«Ma come fa a non esserci gravità?».
«Eh, oh, non c'è aria, non c'è gravità, scusi».
«NOAOAOAO».
«No?».
«Proprio no! Secondo te per mettere un satellite in orbita si spara un missile in verticale, si arriva alla posizione giusta, ci si ferma, si molla lì il satellite e si torna indietro?».
«Certo, c'è un altro modo?».
Ecco.
lunedì 28 ottobre 2013
Inclusione—esclusione, parte 4: la soluzione del quesito
«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».
«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».
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.
sabato 14 settembre 2013
Carnevale della Matematica #65, o 5512, o 1018, o 10014, o 10000012, o LXV, o 5×13, o 12+82, o 42+72, o O5, o anche 15+24+33+42+51.
Benvenuti al Carnevale della Matematica numero 65 (in base 10), dedicato al tema della navigazione.
Una notizia curiosa che riporta Wikipedia in inglese sul numero 65 è la seguente:
Ok, era una battuta. Parlando invece di cose serie, 65 è il numero identificativo della prima portaerei statunitense nucleare, dismessa il 1 dicembre 2012; il suo nome è USS Enterprise. La prossima nave che porterà il glorioso nome sarà la CVN-80, pronta probabilmente intorno al 2025 — ci riaggiorniamo al Carnevale della Matematica #80, perché, come dice il Capitano, Let's make sure history never forgets the name Enterprise.
Veniamo ai contributi di questo mese, elencati in rigoroso ordine di arrivo, senza tenere conto dell'attinenza al tema del Carnevale (che, si sa, è solo un pretesto per poter scrivere cose strane nell'introduzione).
Martino, dal suo blog Termueske, parla del Google Pagerank: come fa Google a indovinare quasi sempre dove volete andare quando navigate su internet?
Spartaco Mencaroni, da Il coniglio mannaro, ci propone un racconto dal titolo Prima dell'autunno che parla di navigazione e, più o meno metaforicamente, di come la scienza può essere una via per superare i limiti che si crederebbero assoluti.
Marco Fulvio Barozzi, su Popinga, ha scritto tre contributi:
Paolo Alessandrini pubblica, su Mr. Palomar, un post dal titolo Parole informatiche: navigare (che non è uguale a surfare, eh).
Annarita Ruberto, da Matem@ticaMente, ci propone
Leonardo Petrillo pubblica, nel blog Al Tamburo Riparato, un post sulle spirali logaritmiche e la lossodromia, curva utilizzata come riferimento nella navigazione terrestre.
Jean M.M. ha scritto tre post sul blog Con le mele | e con le pere:
Giungiamo ora ai Rudi Mathematici, che sul loro blog hanno pubblicato tanto:
Ora passiamo a Roberto Natalini, che su MaddMaths! ha scritto:
Chris Sorrentino ha parlato, su Natura Mat3matica, della geometria del taxi (o di Manhattan, o di Torino, vedete voi). Come cambia la geometria se cambia il concetto di distanza?
.mau. dice che ha scritto poco, vediamo. Sul Post ha pubblicato:
Bene, il Carnevale finisce qui. Il prossimo sarà ospitato da .mau. stesso sul Post e avrà come tema Parole e Numeri. Cominciate a pensarci.
Una notizia curiosa che riporta Wikipedia in inglese sul numero 65 è la seguente:
The traditional age for retirement in the United Kingdom, Germany, the United States, Canada, and several other countries.
Ok, era una battuta. Parlando invece di cose serie, 65 è il numero identificativo della prima portaerei statunitense nucleare, dismessa il 1 dicembre 2012; il suo nome è USS Enterprise. La prossima nave che porterà il glorioso nome sarà la CVN-80, pronta probabilmente intorno al 2025 — ci riaggiorniamo al Carnevale della Matematica #80, perché, come dice il Capitano, Let's make sure history never forgets the name Enterprise.
Veniamo ai contributi di questo mese, elencati in rigoroso ordine di arrivo, senza tenere conto dell'attinenza al tema del Carnevale (che, si sa, è solo un pretesto per poter scrivere cose strane nell'introduzione).
Martino, dal suo blog Termueske, parla del Google Pagerank: come fa Google a indovinare quasi sempre dove volete andare quando navigate su internet?
Spartaco Mencaroni, da Il coniglio mannaro, ci propone un racconto dal titolo Prima dell'autunno che parla di navigazione e, più o meno metaforicamente, di come la scienza può essere una via per superare i limiti che si crederebbero assoluti.
Marco Fulvio Barozzi, su Popinga, ha scritto tre contributi:
- La successione di Vauban (altro che porcheria!). Il marchese di Vauban, generale, stratega, ingegnere militare, è stato una delle figure più importanti del lungo regno del Re Sole. Si occupò di calcoli per motivi di servizio, pur non essendo un matematico di professione. In tarda età cominciò a scrivere una serie di saggi contenenti memorie e congetture, tra cui la curiosa “Porcheria, o calcolo stimato per conoscere fino a dove può giungere la produzione di una scrofa in un periodo di dieci anni”, nella quale propose l’allevamento generalizzato del maiale, concludendo che in sole dodici generazioni «vi sarebbero così tanti [maiali] da nutrire l’Europa». I calcoli del marchese danno origine a una successione numerica che oggi fa parte del repertorio OEIS.
- Nunes, tra ortodromie e lossodromie. Il problema della rotta più breve tra due punti sulla sfera terrestre cominciò a porsi in termini stringenti quando le navi incominciarono ad attraversare gli oceani, nei decenni successivi al viaggio di Colombo. Della questione si occupò il matematico portoghese Pedro Nunes, il quale pubblicò nel 1537 due trattati sui problemi di navigazione, in cui sosteneva che gli archi di circoli massimi (le ortodromie), che costituiscono i percorsi più brevi tra due punti, non sono, tranne che nel caso dell’'equatore e dei meridiani, rotte costanti: se si vuole seguire un’ortodromia è necessario cambiare continuamente rotta (cioè l’angolo con il meridiano). Il cammino seguito con angolo costante rispetto ai meridiani è invece costituito da una curva che egli descrive per primo, la lossodromia.
- Matematica applicata e filosofia. Un originale contributo alla secolare discussione sulla natura della matematica è fornito da un articolo di Paul Wilson, un matematico applicato neozelandese, il quale si chiede “Che cosa ci dice l’applicabilità della matematica riguardo ai suoi fondamenti?” Nel porre questa domanda egli dà per acquisito che non esiste alcun serio disaccordo sul fatto che la matematica sia applicabile. Nessuna delle spiegazioni fornite finora sembra soddisfacente, perciò Wilson propone la costruzione di un nuovo paradigma basato sull’applicabilità, che potrebbe portare a una migliore comprensione della natura della matematica e dell’universo fisico.
Paolo Alessandrini pubblica, su Mr. Palomar, un post dal titolo Parole informatiche: navigare (che non è uguale a surfare, eh).
Annarita Ruberto, da Matem@ticaMente, ci propone
- Simmetria, l'enigma della realtà: si tratta di un talk del TED con sottotitoli in lingua italiana e traduzione a seguire, in cui Marcus du Sautoy offre uno sguardo ai numeri invisibili che uniscono tutti gli oggetti simmetrici.
- I cerchi di Villarceau: particolari sezioni toriche.
- Pythagoras Tree Fractal: un post in inglese riguardante un particolare frattale, la cui costruzione è legata al teorema di Pitagora.
- Una animazione sulla circonferenza: applet realizzato con GeoGebra per gli studenti della prof.
Leonardo Petrillo pubblica, nel blog Al Tamburo Riparato, un post sulle spirali logaritmiche e la lossodromia, curva utilizzata come riferimento nella navigazione terrestre.
Jean M.M. ha scritto tre post sul blog Con le mele | e con le pere:
- La cosa più meravigliosa del mondo, che è un approssimatore universale di funzioni. Nientemeno. Ed una delle sue capacità più sorprendenti è la memoria. E così, scivolando sulla curva dell'oblio, si arriva ad un problemino di matematica discreta.
- Ferrara 2013 – Divertissement 18-20. Tre problemini di geometria che prendono spunto dai particolari di fotografie scattate durante una gita a Ferrara. Per arrivarci si può saltare a piè pari un lunghetto (s)prologo che parla di meta-vanitas.
- Che convoluzione, un tetraedro! Una semplice immagine rappresenta graficamente una formula alternativa per il calcolo dei numeri tetraedrici. Nel testo, una spiegazione della stessa insieme a una comparazione con la formula standard che ci porta, a sorpresa, ad imbatterci in altri numeri figurati, quelli piramidali.
Giungiamo ora ai Rudi Mathematici, che sul loro blog hanno pubblicato tanto:
- Il compleanno di Fermat, che io avevo già letto su carta un po' di anni fa (ahimé), dove Piotr parla della Fetta di Polenta, un palazzo di Torino. Dopo averne letto la storia sono stato anche a vederla di persona, ai tempi.
- Costruzioni complicate – Seconda parte, boing… BoinG… BoInG…BOING… thump: la seconda parte di un articolo della serie Paraphernalia Mathematica scritto da Rudi riguardante tanti insiemi numerici, dai reali fino ai sedenioni (c'è anche una mia figurina, che bello).
- La soluzione al problema di agosto, Inviti Improvvisati.
- Un secondo compleanno, quello di Mersenne.
- Infine, Piotr sottolinea soddisfatto il fatto che il numero 176 della prestigiosa rivista di matematica ricreativa è uscito prima del Carnevale della Matematica.
Ora passiamo a Roberto Natalini, che su MaddMaths! ha scritto:
- A che serve la matematica? La domanda dalle cento risposte. Se si è professore di matematica, matematico, studente di matematica o semplicemente genitore di uno studente, inevitabilmente ci si dovrà confrontare con LA grande domanda: a che cosa serve la matematica? Che si presenti sotto la forma di “A che cosa serve la trigonometria / il calcolo degli integrali / sapere che apiùbialquadratougualeadaduepiùdueabipiùbidue?” o nella variante affermativa “Ad ogni modo, la matematica non serve a niente”, il senso è sempre lo stesso. A che diavolo può servire la matematica? Traduzione, con pregevoli licenze, dell’articolo A quoi ça sert, les maths? - a cura di Kees Popinga.
- Vita da Matematico: Silvia Poles. Silvia Poles si è laureata in matematica all'Università di Padova nel 1996. Dal 2000 lavora alla EnginSoft alla identificazione dei “problemi industriali e delle possibili soluzioni matematiche in termini di metodi, impegno e tempi”. Da quest'anno fa parte del Consiglio Direttivo della SIMAI.
- Alfabeto matematico: G come Gradiente, di Corrado Mascia. Carlo ne è sicuro: ogni fenomeno in natura avviene a causa della presenza di un gradiente. Un gradiente topografico genera un fiume ed un gradiente di energia elastica, accumulata poco a poco all'interno della crosta terrestre, è responsabile di un terremoto. Carlo ne è convinto ed io, a modo mio, gli vado dietro. Entro al supermercato, reparto frutta e verdura, e mi congelo: tutta colpa di un gradiente di temperatura. Ne esco, e mi pare di morire dal caldo. Nuova imprecazione contro il gradiente, unico responsabile di questa sgradevole variazione termica.
- Facebook e la teoria dei grafi. Presentiamo un nuovo progetto realizzato dagli alunni del triennio corso programmatori P/A e P/C dell'Istituto Tecnico Economico G. Calò di Francavilla Fontana (Br).
- Radio3 Scienza: Il matematico e i manga. Abiti da dandy, una grande spilla a forma di ragno e una passione sfrenata per i fumetti giapponesi. Oltre a una medaglia Fields, il premio Nobel dei matematici, vinta nel 2010. A Radio3 Scienza Cédric Villani, direttore dell’Institut Henri Poincaré di Parigi e autore di Il teorema vivente (Rizzoli, 2013), ha raccontato le sue passioni e il suo lavoro matematico. Roberto Natalini e Fabio Pagan ne parlano nella puntata del 16 agosto 2013.
- La gioia dei Numeri di Steven Strogatz. Roberto Natalini recensisce il nuovo libro di Steven Strogatz, una guida per tutti al piacere della matematica.
- L'equazione del Millennio e la matematica come divertimento. L'Equation du Millénaire (L'equazione del millennio), una graphic novel prodotta dalla Fondation Science Mathématiques de Paris e recensita da Roberto Natalini.
Chris Sorrentino ha parlato, su Natura Mat3matica, della geometria del taxi (o di Manhattan, o di Torino, vedete voi). Come cambia la geometria se cambia il concetto di distanza?
.mau. dice che ha scritto poco, vediamo. Sul Post ha pubblicato:
- i problemini di ferragosto con relative soluzioni;
- una pillola con la recensione di un gioco (A game of Numbers);
- un pippone filosofico su quanto è irragionevolmente efficace la matematica;
- alcune considerazioni sul Teorema della pizza.
Sulle Notiziole ha recensito due libri:
- Da zero a infinito, di Constance Reid: Forse non impararete molto, ma apprezzerete.
- The Universal Computer, di Martin Davis; la storia che ha portato alla costruzione dei computer.
Bene, il Carnevale finisce qui. Il prossimo sarà ospitato da .mau. stesso sul Post e avrà come tema Parole e Numeri. Cominciate a pensarci.
mercoledì 7 agosto 2013
Nim — 14. La strategia vincente
«Alcuni libri, tra cui anche quello di Martin Gardner, suggeriscono di fare i conti con i nimeri in modo diverso rispetto a quello che abbiamo usato noi».
«E perché?».
«Mah, non saprei dirlo esattamente. Forse perché danno il metodo bello e pronto, senza spiegare niente, o forse perché in origine lo studio del Nim è stato fatto proprio in questo modo».
«Uh, un articolo del 1901».
«Sì, la teoria di Sprague-Grundy è venuta dopo».
«Ah, ecco. E come faceva l'autore…».
«Charles L. Bouton».
«Come faceva Bouton a vincere al Nim?».
«La regola base per le operazioni era questa: scrivi i numeri in binario e fai la somma senza riporto».
«Cosacosa?».
«Ti faccio vedere con i calcoli che abbiamo fatto l'altra volta. Abbiamo visto, per esempio, che *5 + *3 = *6. Bouton diceva di trasformare 5 e 3 in binario…».
«Cioè 510 = 1012 e 310 = 112».
«Sì. Poi metti in colonna e fai la somma senza tener conto del riporto. In pratica usi queste regole: 0 + 0 = 0, 1 + 0 = 1 e 1 + 1 = 0».
«Vediamo, ecco qua:».
«Molto bene. Quanto fa 1102?».
«Fa 4 + 2 = 6, giusto!».
«Prova anche con *11 + *22 + *33».
«Pronti:».
«E 1111002 = 6010».
«Giusto anche questo. Come mai funziona?».
«Bé, sono le regole che abbiamo scoperto l'altra volta: due numeri uguali si cancellano quando vengono sommati, no?».
«Sì».
«E questo significa che quando sommi trascuri il riporto: 1 + 1 = 0 è una cancellazione, in pratica».
«Ah, già. E l'altra regola diceva che le potenze di 2 si sommano normalmente, come se usassimo la somma usuale».
«E infatti quando passiamo da forma binaria a forma decimale sommiamo potenze di 2, tutto qua».
«Bella roba. Ma questo cosa ha a che fare con la strategia vincente?».
«Ci arriviamo subito: ricorderai la nostra partita a Nim (3,2,1)».
«Certo, ho cominciato io, ma dato che *3 + *2 + *1 = 0 hai vinto tu».
«Ottimo riassunto: se tu giochi a un gioco nullo, hai perso. Io, per vincere, devo fare in modo che tu abbia sempre a che fare con un gioco nullo».
«E come fai?».
«Ti faccio vedere con un esempio: inventati un Nim con quante pile vuoi».
«Boh, per esempio (3,14,15,9)».
«Bene, per prima cosa scomponiamo in potenze di 2 tutti i numeri:».
3 = 2+1
14 = 8+4+2
15 = 8+4+2+1
9 = 8+1
«Va bene, poi?».
«Ora faccio i conti, quanto vale la somma-nim di quei quattro numeri?».
«Devo fare la somma in colonna, dopo aver trasformato in binario?».
«Non c'è bisogno: con la scomposizione in somme di potenze di 2 puoi fare a mente, guarda prima cosa si cancella».
«Se non sbaglio, cancellando le cifre a 2 a 2 uguali, mi rimane 8+2+1».
«Che fa 11. Siccome 11 è diverso da 0, comincio io».
«Fai pure, immagino che mi passerai un gioco nullo».
«Naturalmente. Il problema è: come faccio a farlo diventare nullo?».
«Come fai?».
«Visto che dopo le semplificazioni avanzano i numeri 8, 2 e 1, li cancello: sottraggo 11 dalla terza pila».
3 = 2+1
14 = 8+4+2
4 = 4
9 = 8+1
«Ah, adesso il gioco fa zero. Ora tocca a me?».
«Sì. Qualunque mossa tu farai, il gioco non potrà valere ancora zero».
«Perché?».
«Perché puoi togliere pedine solo da una pila, quindi sbilancerai certamente le coppie che prima si cancellavano».
«Ah, già. Bé, allora cancello tutta la pila da 14».
3 = 2+1
4 = 4
9 = 8+1
«Siamo a 8 + 4 + 2 = 14».
«Ora come fai a tornare a zero? Non puoi cancellare l'otto, il quattro e il due, sono in pile diverse!».
«Sottraggo due pedine dalla terza pila».
«Perché?».
«Pensa all'8 che vedi nella terza pila: se sottrai due pedine diventa 6, cioè 4 + 2, che è quello che mi serve per bilanciare tutto:».
3 = 2+1
4 = 4
7 = 4+2+1
«Ah, ecco! Ancora una volta è 0. Se ora togliessi 5 pedine dalla terza pila?».
3 = 2+1
4 = 4
2 = 2
«Dimmi tu cosa dovrei fare».
«Hai 2+1 sopra, hai 2 sotto, ti basta trasformare il 4 in 1».
3 = 2+1
1 = 1
2 = 2
«Già. E siamo arrivati al nostro vecchio conoscente: (3,2,1). Direi che possiamo concludere la partita, no?».
«Eh, sì. Ma ci si riesce sempre a far diventare nullo un gioco non nullo?».
«Sì, pensa a come fai i calcoli: se il gioco non è nullo significa che nelle semplificazioni c'è qualche potenza di 2 sbilanciata. Se queste potenze sbilanciate si trovano su una pila sola, le cancelli tutte».
«E se si trovano su pile diverse?».
«Cerchi la più grande, e la diminuisci fino a farla diventare uguale alla somma delle altre».
«Uh, possiamo vedere un altro esempio?».
«Eccolo qua: (11,22,33)».
«Chi comincia?».
«Vai, per questa volta comincia tu. Devi vincere, visto che abbiamo già calcolato la somma-nim di questo gioco e sappiamo che vale 60».
«Allora, mi scrivo i numeri come somme di potenze di 2:».
11 = 8 + 2 + 1
22 = 16 + 4 + 2
33 = 32 + 1
«Bene, ho visto che hai messo anche i termini che si semplificano. Adesso?».
«Scelgo la potenza più alta, che è 32, e devo trasformarla in 16+8+4, che fa 28. Tolgo 4 pedine dalla terza pila:».
11 = 8 + 2 + 1
22 = 16 + 4 + 2
29 = 16 + 8 + 4 + 1
«Uh, ma cadrebbe tutta la teoria che abbiamo sviluppato!».
«Ottima risposta, ma riesci a darmene una più pratica? Perché non posso diminuire una qualche pila fino a bilanciare di nuovo tutto?».
«Mh, non saprei dirlo».
«Diciamo che scelgo la pila più grande, quella da 29. Se tolgo il 16, rimane un 16 sbilanciato».
«Ma non sei obbligato a togliere proprio 16, no?».
«No, ma se comunque tolgo almeno una pedina da quella pila, succede che almeno una delle potenze di 2 che la compongono deve diminuire».
«Già».
«E allora la sua gemella, che necessariamente si trova in un'altra pila, sarà sbilanciata».
«Ah, certo, non posso avere due potenze di 2 uguali nella stessa pila!».
«Potenza della notazione posizionale, se mi concedi la battuta».
«Battuta?».
«Ehm, ok, non faceva ridere. Comunque, andiamo avanti, tolgo 5 pedine dalla pila da 29:».
11 = 8 + 2 + 1
22 = 16 + 4 + 2
24 = 16 + 8
«Avanzano un 4 e un 1. Qui ho molte scelte, posso prendere uno dei due 16 e diminuirlo fino a farlo diventare 4+1».
«No, no, 16 è già bilanciato! Devi prendere la potenza più alta tra quelle non bilanciate».
«Ah, ecco. Allora devo trasformare il 4 della seconda fila in 1: sottraggo 3 dalla seconda pila:».
11 = 8 + 2 + 1
19 = 16 + 2 + 1
24 = 16 + 8
«Ormai hai capito, no? Ogni volta che io sbilancio, tu ribilanci.».
«Direi proprio di aver capito tutto».
«Perfetto, a questo punto allora direi che possiamo fermarci».
«Fine degli studi sul Nim?».
«Fine, ora si tratta di giocare».
«E perché?».
«Mah, non saprei dirlo esattamente. Forse perché danno il metodo bello e pronto, senza spiegare niente, o forse perché in origine lo studio del Nim è stato fatto proprio in questo modo».
«Uh, un articolo del 1901».
«Sì, la teoria di Sprague-Grundy è venuta dopo».
«Ah, ecco. E come faceva l'autore…».
«Charles L. Bouton».
«Come faceva Bouton a vincere al Nim?».
«La regola base per le operazioni era questa: scrivi i numeri in binario e fai la somma senza riporto».
«Cosacosa?».
«Ti faccio vedere con i calcoli che abbiamo fatto l'altra volta. Abbiamo visto, per esempio, che *5 + *3 = *6. Bouton diceva di trasformare 5 e 3 in binario…».
«Cioè 510 = 1012 e 310 = 112».
«Sì. Poi metti in colonna e fai la somma senza tener conto del riporto. In pratica usi queste regole: 0 + 0 = 0, 1 + 0 = 1 e 1 + 1 = 0».
«Vediamo, ecco qua:».
1 0 1 1 1 ----- 1 1 0
«Molto bene. Quanto fa 1102?».
«Fa 4 + 2 = 6, giusto!».
«Prova anche con *11 + *22 + *33».
«Pronti:».
11 = 1 0 1 1
22 = 1 0 1 1 0
33 = 1 0 0 0 0 1
----------------
1 1 1 1 0 0
«E 1111002 = 6010».
«Giusto anche questo. Come mai funziona?».
«Bé, sono le regole che abbiamo scoperto l'altra volta: due numeri uguali si cancellano quando vengono sommati, no?».
«Sì».
«E questo significa che quando sommi trascuri il riporto: 1 + 1 = 0 è una cancellazione, in pratica».
«Ah, già. E l'altra regola diceva che le potenze di 2 si sommano normalmente, come se usassimo la somma usuale».
«E infatti quando passiamo da forma binaria a forma decimale sommiamo potenze di 2, tutto qua».
«Bella roba. Ma questo cosa ha a che fare con la strategia vincente?».
«Ci arriviamo subito: ricorderai la nostra partita a Nim (3,2,1)».
«Certo, ho cominciato io, ma dato che *3 + *2 + *1 = 0 hai vinto tu».
«Ottimo riassunto: se tu giochi a un gioco nullo, hai perso. Io, per vincere, devo fare in modo che tu abbia sempre a che fare con un gioco nullo».
«E come fai?».
«Ti faccio vedere con un esempio: inventati un Nim con quante pile vuoi».
«Boh, per esempio (3,14,15,9)».
«Bene, per prima cosa scomponiamo in potenze di 2 tutti i numeri:».
3 = 2+1
14 = 8+4+2
15 = 8+4+2+1
9 = 8+1
«Va bene, poi?».
«Ora faccio i conti, quanto vale la somma-nim di quei quattro numeri?».
«Devo fare la somma in colonna, dopo aver trasformato in binario?».
«Non c'è bisogno: con la scomposizione in somme di potenze di 2 puoi fare a mente, guarda prima cosa si cancella».
«Se non sbaglio, cancellando le cifre a 2 a 2 uguali, mi rimane 8+2+1».
«Che fa 11. Siccome 11 è diverso da 0, comincio io».
«Fai pure, immagino che mi passerai un gioco nullo».
«Naturalmente. Il problema è: come faccio a farlo diventare nullo?».
«Come fai?».
«Visto che dopo le semplificazioni avanzano i numeri 8, 2 e 1, li cancello: sottraggo 11 dalla terza pila».
3 = 2+1
14 = 8+4+2
4 = 4
9 = 8+1
«Ah, adesso il gioco fa zero. Ora tocca a me?».
«Sì. Qualunque mossa tu farai, il gioco non potrà valere ancora zero».
«Perché?».
«Perché puoi togliere pedine solo da una pila, quindi sbilancerai certamente le coppie che prima si cancellavano».
«Ah, già. Bé, allora cancello tutta la pila da 14».
3 = 2+1
4 = 4
9 = 8+1
«Siamo a 8 + 4 + 2 = 14».
«Ora come fai a tornare a zero? Non puoi cancellare l'otto, il quattro e il due, sono in pile diverse!».
«Sottraggo due pedine dalla terza pila».
«Perché?».
«Pensa all'8 che vedi nella terza pila: se sottrai due pedine diventa 6, cioè 4 + 2, che è quello che mi serve per bilanciare tutto:».
3 = 2+1
4 = 4
7 = 4+2+1
«Ah, ecco! Ancora una volta è 0. Se ora togliessi 5 pedine dalla terza pila?».
3 = 2+1
4 = 4
2 = 2
«Dimmi tu cosa dovrei fare».
«Hai 2+1 sopra, hai 2 sotto, ti basta trasformare il 4 in 1».
3 = 2+1
1 = 1
2 = 2
«Già. E siamo arrivati al nostro vecchio conoscente: (3,2,1). Direi che possiamo concludere la partita, no?».
«Eh, sì. Ma ci si riesce sempre a far diventare nullo un gioco non nullo?».
«Sì, pensa a come fai i calcoli: se il gioco non è nullo significa che nelle semplificazioni c'è qualche potenza di 2 sbilanciata. Se queste potenze sbilanciate si trovano su una pila sola, le cancelli tutte».
«E se si trovano su pile diverse?».
«Cerchi la più grande, e la diminuisci fino a farla diventare uguale alla somma delle altre».
«Uh, possiamo vedere un altro esempio?».
«Eccolo qua: (11,22,33)».
«Chi comincia?».
«Vai, per questa volta comincia tu. Devi vincere, visto che abbiamo già calcolato la somma-nim di questo gioco e sappiamo che vale 60».
«Allora, mi scrivo i numeri come somme di potenze di 2:».
11 = 8 + 2 + 1
22 = 16 + 4 + 2
33 = 32 + 1
«Bene, ho visto che hai messo anche i termini che si semplificano. Adesso?».
«Scelgo la potenza più alta, che è 32, e devo trasformarla in 16+8+4, che fa 28. Tolgo 4 pedine dalla terza pila:».
11 = 8 + 2 + 1
22 = 16 + 4 + 2
29 = 16 + 8 + 4 + 1
«Molto bene, ora tutto è bilanciato e tocca a me: siamo sicuri che io non possa passare a un'altra configurazione nulla?».
«Uh, ma cadrebbe tutta la teoria che abbiamo sviluppato!».
«Ottima risposta, ma riesci a darmene una più pratica? Perché non posso diminuire una qualche pila fino a bilanciare di nuovo tutto?».
«Mh, non saprei dirlo».
«Diciamo che scelgo la pila più grande, quella da 29. Se tolgo il 16, rimane un 16 sbilanciato».
«Ma non sei obbligato a togliere proprio 16, no?».
«No, ma se comunque tolgo almeno una pedina da quella pila, succede che almeno una delle potenze di 2 che la compongono deve diminuire».
«Già».
«E allora la sua gemella, che necessariamente si trova in un'altra pila, sarà sbilanciata».
«Ah, certo, non posso avere due potenze di 2 uguali nella stessa pila!».
«Potenza della notazione posizionale, se mi concedi la battuta».
«Battuta?».
«Ehm, ok, non faceva ridere. Comunque, andiamo avanti, tolgo 5 pedine dalla pila da 29:».
11 = 8 + 2 + 1
22 = 16 + 4 + 2
24 = 16 + 8
«Avanzano un 4 e un 1. Qui ho molte scelte, posso prendere uno dei due 16 e diminuirlo fino a farlo diventare 4+1».
«No, no, 16 è già bilanciato! Devi prendere la potenza più alta tra quelle non bilanciate».
«Ah, ecco. Allora devo trasformare il 4 della seconda fila in 1: sottraggo 3 dalla seconda pila:».
11 = 8 + 2 + 1
19 = 16 + 2 + 1
24 = 16 + 8
«Direi proprio di aver capito tutto».
«Perfetto, a questo punto allora direi che possiamo fermarci».
«Fine degli studi sul Nim?».
«Fine, ora si tratta di giocare».
lunedì 5 agosto 2013
Nim — 13. Variazioni sulla regola della somma
«Ora vediamo di capire come mai ci sono colori diversi nella tabella della somma di nimeri».
«Oh, finalmente».
«Ho aspettato tanto perché così nel frattempo siamo diventati pratici nel calcolare somme di nimeri e Mex».
«Bene, ti ascolto».
«Allora, partiamo dal semplice: se avessimo a disposizione solo il nimero *0, cioè il gioco nullo, la tabella sarebbe molto facile da fare».
«Già, avrebbe una casellina sola, quella rossa».
«Infatti. Ora complichiamo un pochino, aggiungiamo *1. Ora abbiamo due nimeri, *0 e *1, che possiamo combinare in tre modi diversi: *0 + *0, *0 + *1 e *1 + *1. Di questa somma sappiamo già tutto, la regola del Mex ci dice che non usciamo dall'insieme {*0, *1}, e tutte le possibili somme si esauriscono qui».
«Abbiamo fatto la cornice blu».
«Sì. Ora le cose si complicano: se aggiungiamo un nuovo nimero, e cioè *2, ci accorgiamo che possono capitare casi in cui si deve calcolare il Mex di {*0, *1, *2}».
«Giusto, per esempio se dobbiamo calcolare *1 + *2».
«Ottimo. Vale la pena perdere un po' di tempo sui calcoli, per capire cosa c'è sotto: quando calcoliamo il risultato di *1 + *2, stiamo analizzando tutto quello che potrebbe succedere quando un giocatore muove o nel primo gioco o nel secondo».
«Vero».
«Quindi, dato che *1 = {*0} e *2 = {*0, *1}, le possibili mosse sono queste:».
*0 + *2 (muovo nel primo gioco, togliendo l'unica pedina)
*1 + *1 (muovo nel secondo gioco, togliendo una pedina)
*1 + *0 (muovo nel secondo gioco, togliendo due pedine)
«Sì, i possibili risultati sono stati calcolati in precedenza, sono *2, *0 e *1».
«E quindi il Mex vale *3».
«E infatti abbiamo detto che se aggiungiamo *2, abbiamo bisogno anche di *3 per completare la tabella, che sarebbe la nuova cornice colorata di giallo».
«Sì. Ora la domanda: perché dobbiamo aggiungere un nuovo nimero?».
«Ma l'abbiamo appena detto!».
«Aspetta: perché proprio uno solo, e non due o tre o chissà quanti?».
«Ah… uhm».
«Ragioniamo: la regola del Mex è tale per cui ogni riga e ogni colonna sono composte tutte da nimeri diversi».
«Eh, sì, questo lo capisco: il Mex è il più piccolo intero non negativo non presente a sinistra e sopra la casella che vogliamo riempire, quindi non ne posso mai scrivere due uguali».
«Benissimo. Ora osserva la griglia che contiene solo *0 e *1».
«Quella blu».
«Quella: è composta da due righe e due colonne; se voglio allargarla succederà prima o poi che i due nimeri che la compongono, *0 e *1, si devono trovare al di fuori della zona blu».
«Senza dubbio: *0 e *1 sono i due nimeri più piccoli, nella regola del Mex saltano fuori in fretta».
«E allora quando mi capiterà di avere *0 e *1 fuori dalla zona blu, nella zona blu dovranno esserci altri due nuovi nimeri».
«Ah! Ecco perché devo aumentare di due caselle! E dopo avrò a disposizione quattro nimeri, e se vorrò allargare la zona gialla ce ne vorranno altri quattro, poi otto, sedici, trentadue…».
«Perfetto, hai capito. Non ti spaventerà dunque questa regola:».
1. Se a e b sono minori di 2k, allora lo sarà anche *a + *b.
«Non mi spaventa, è quello che abbiamo detto finora. La regola dei colori, insomma».
«Benissimo. Un'ultima considerazione: osserva la prima riga (o la prima colonna) di ogni nuova cornice».
«Cioè quando cambiano colore?».
«Sì, esatto».
«Boh, la prima riga blu è *1, *0».
«Poi?».
«La prima riga gialla è *2, *3, *0, *1».
«Poi la prima riga viola è *4, *5 , *6, *7, *0, *1, *2, *3».
«E la prima riga fucsia è *8, *9, *10, *11, *12, *13, *14, *15, *0, *1, *2, *3, *4, *5, *6, *7, quindi?».
«Quindi succedono varie cose. Prima di tutto, ogni riga di un colore nuovo parte da una potenza di 2».
«Ok, un altro modo di dire quello che abbiamo visto prima».
«Già. Poi, grazie alla regola del Mex, le righe di un nuovo colore proseguono in ordine crescente fino a metà lunghezza».
«Vero anche questo, prima ci sono i nuovi nimeri, poi quelli vecchi».
«Quindi, riassumendo, se prendiamo come esempio la prima riga viola, quella che comincia con *4, *5, *6, *7, e ci ricordiamo che quei nimeri sono il risultato di una somma, possiamo dire questo:».
*4 + *0 = *4
*4 + *1 = *5
*4 + *2 = *6
*4 + *3 = *7
«E poi ci fermiamo, perché *4 + *4 non fa *8 ma *0».
«Bene. Generalizzando, cosa possiamo dire?».
«Uhm, forse possiamo dire che se prendiamo una potenza di 2 e sommiamo dei nimeri, è come se facessimo una somma normale?».
«Quasi. La regola vale solo fino a metà riga, nel nostro esempio fino a *4 + *4 escluso».
«Ok, allora ho capito, provo a formulare la regola: se sommo una potenza di 2 con un nimero minore di essa, è come se stessi facendo una somma tra normali numeri».
«Bene, in formule è così:».
2. Se a < 2k, allora *a + *2k = *(a + 2k).
«Capito».
«Da cui deduciamo subito queste regole pratiche:».
3. La somma-nim di due diverse potenze di 2 è uguale alla loro somma ordinaria, e la somma-nim di due numeri uguali è 0.
«Perché dici somma-nim?».
«Per non mettere tutti gli asterischi, e per non dover specificare ogni volta che le potenze di 2 che consideriamo sono dei nimeri».
«Ah, ok. E come mai le hai chiamate regole pratiche?».
«Perché ci permettono di fare molto in fretta i calcoli. Ti faccio qualche esempio: vogliamo calcolare il risultato di questa operazione:».
5 ⊕ 3
«Cos'è quello strano simbolo?».
«Significa che stiamo addizionando nimeri, è come se avessi scritto *5 + *3. Dato che dobbiamo fare un po' di calcoli, mi pare che sia più comodo. Tieni presente che quando scrivo ⊕ intendo l'addizione tra nimeri, mentre quando scrivo + intendo la normale addizione tra numeri».
«Ah, va bene. Allora, dobbiamo calcolare 5 ⊕ 3».
«Sì, utilizzando solo la regola pratica, cioè quella che abbiamo indicato col numero 3».
«Ma è una regola che parla di potenze di 2, o di numeri uguali».
«Vorrà dire che dobbiamo trasformare quei numeri in potenze di 2».
«Come se stessimo facendo un cambiamento di base?».
«Esattamente, ottimo! 5 in base 2 è uguale a 101, cioè 4 + 1».
«Mentre 3 è uguale a 11, cioè 2 + 1».
«E quindi il nostro calcolo diventa questo:».
5 ⊕ 3 = (4 + 1) ⊕ (2 + 1)
«E adesso come facciamo? Abbiamo due diversi simboli di somma».
«La somma-nim di due diverse potenze di 2 è uguale alla loro somma ordinaria, quindi scrivere 4 + 1 è come scrivere 4 ⊕ 1».
«Ah, allora possiamo togliere le parentesi e usare solo il simbolo della somma-nim:».
5 ⊕ 3 = 4 ⊕ 1 ⊕ 2 ⊕ 1
«Ora ricordati che la somma-nim di due numeri uguali è uguale a 0».
«E quindi posso scrivere questo:».
5 ⊕ 3 = 4 ⊕ 1 ⊕ 2 ⊕ 1 = 4 ⊕ 2
«Ora hai due potenze di 2 da sommare, quindi…».
Quindi posso calcolare il risultato: 4 ⊕ 2 = 4 + 2 = 6
«Benissimo. Se vogliamo utilizzare la notazione a cui siamo abituati, abbiamo calcolato che *5 + *3 = *6».
«Concorda con la tabella».
«Col vantaggio che non abbiamo avuto bisogno di consultarla per poter calcolare il Mex».
«Bello, si dovrebbe riuscire a fare i calcoli più in fretta».
«È così. Prova per esempio a calcolare questo:».
11 ⊕ 22 ⊕ 33
«Uh, questi sono numeri fuori dalla tabella. Allora, prima scompongo in potenze di 2 i vari numeri».
11 = 8 + 2 + 1
22 = 16 + 4 + 2
33 = 32 + 1
«E fin qua ci siamo».
«Poi addiziono tutto».
«Sì, ma ti conviene già scartare le coppie di numeri uguali».
«Ah, giusto: si annullano. Allora mi rimane questo:».
8 ⊕ 16 ⊕ 4 ⊕ 32 = 60
«Molto bene. Ora che hai capito, puoi anche abbreviare i calcoli e, se vuoi, usare l'altra notazione. Per esempio:».
*9 + *25 + *49 = (*8 + *1) + (*16 + *8 + *1) + (*32 + *16 + *1) = *32 + *1 = *33
«Ah, hai colorato le potenze che si semplificano».
«Sì, come vedi è molto comodo. Ora, una domanda: se noi facessimo la somma normale, otterremmo un numero certamente più grande o più piccolo di quello che otterremmo facendo la somma-nim?».
«Mh, a volte viene uguale, mentre altre volte più grande, dato che nella somma-nim ci sono delle possibili semplificazioni».
«Molto bene, quindi potremmo dire che a ⊕ b ≤ a + b».
«Direi proprio di sì».
«Un'ultima domanda: quando le due somme sono diverse, per cosa differiscono?».
«Per le potenze di 2 che ho semplificato».
«Bene, e posso dire che ogni volta che faccio una semplificazione tolgo due copie dello stesso numero?».
«Certo».
«E quindi tolgo un numero pari ogni volta».
«Ho capito: le due somme differiscono per un numero pari (o per 0, quando non ci sono semplificazioni, ma tanto anche 0 è pari)».
«Perfetto. Ecco l'ultima regola di oggi:».
4. La somma-nim è minore o uguale della somma usuale, ed esse differiscono per un numero pari.
«E quindi?».
«E quindi ora possiamo parlare di una strategia vincente per il Nim».
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 1| 0| 3| 2| 5| 4| 7| 6| 9| 8|11|10|13|12|15|14| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 2| 3| 0| 1| 6| 7| 4| 5|10|11| 8| 9|14|15|12|13| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 3| 2| 1| 0| 7| 6| 5| 4|11|10| 9| 8|15|14|13|12| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 4| 5| 6| 7| 0| 1| 2| 3|12|13|14|15| 8| 9|10|11| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 5| 4| 7| 6| 1| 0| 3| 2|13|12|15|14| 9| 8|11|10| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 6| 7| 4| 5| 2| 3| 0| 1|14|15|12|13|10|11| 8| 9| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 7| 6| 5| 4| 3| 2| 1| 0|15|14|13|12|11|10| 9| 8| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 8| 9|10|11|12|13|14|15| 0| 1| 2| 3| 4| 5| 6| 7| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 9| 8|11|10|13|12|15|14| 1| 0| 3| 2| 5| 4| 7| 6| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |10|11| 8| 9|14|15|12|13| 2| 3| 0| 1| 6| 7| 4| 5| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |11|10| 9| 8|15|14|13|12| 3| 2| 1| 0| 7| 6| 5| 4| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |12|13|14|15| 8| 9|10|11| 4| 5| 6| 7| 0| 1| 2| 3| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |13|12|15|14| 9| 8|11|10| 5| 4| 7| 6| 1| 0| 3| 2| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |14|15|12|13|10|11| 8| 9| 6| 7| 4| 5| 2| 3| 0| 1| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |15|14|13|12|11|10| 9| 8| 7| 6| 5| 4| 3| 2| 1| 0| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
«Oh, finalmente».
«Ho aspettato tanto perché così nel frattempo siamo diventati pratici nel calcolare somme di nimeri e Mex».
«Bene, ti ascolto».
«Allora, partiamo dal semplice: se avessimo a disposizione solo il nimero *0, cioè il gioco nullo, la tabella sarebbe molto facile da fare».
«Già, avrebbe una casellina sola, quella rossa».
«Infatti. Ora complichiamo un pochino, aggiungiamo *1. Ora abbiamo due nimeri, *0 e *1, che possiamo combinare in tre modi diversi: *0 + *0, *0 + *1 e *1 + *1. Di questa somma sappiamo già tutto, la regola del Mex ci dice che non usciamo dall'insieme {*0, *1}, e tutte le possibili somme si esauriscono qui».
«Abbiamo fatto la cornice blu».
«Sì. Ora le cose si complicano: se aggiungiamo un nuovo nimero, e cioè *2, ci accorgiamo che possono capitare casi in cui si deve calcolare il Mex di {*0, *1, *2}».
«Giusto, per esempio se dobbiamo calcolare *1 + *2».
«Ottimo. Vale la pena perdere un po' di tempo sui calcoli, per capire cosa c'è sotto: quando calcoliamo il risultato di *1 + *2, stiamo analizzando tutto quello che potrebbe succedere quando un giocatore muove o nel primo gioco o nel secondo».
«Vero».
«Quindi, dato che *1 = {*0} e *2 = {*0, *1}, le possibili mosse sono queste:».
*0 + *2 (muovo nel primo gioco, togliendo l'unica pedina)
*1 + *1 (muovo nel secondo gioco, togliendo una pedina)
*1 + *0 (muovo nel secondo gioco, togliendo due pedine)
«Sì, i possibili risultati sono stati calcolati in precedenza, sono *2, *0 e *1».
«E quindi il Mex vale *3».
«E infatti abbiamo detto che se aggiungiamo *2, abbiamo bisogno anche di *3 per completare la tabella, che sarebbe la nuova cornice colorata di giallo».
«Sì. Ora la domanda: perché dobbiamo aggiungere un nuovo nimero?».
«Ma l'abbiamo appena detto!».
«Aspetta: perché proprio uno solo, e non due o tre o chissà quanti?».
«Ah… uhm».
«Ragioniamo: la regola del Mex è tale per cui ogni riga e ogni colonna sono composte tutte da nimeri diversi».
«Eh, sì, questo lo capisco: il Mex è il più piccolo intero non negativo non presente a sinistra e sopra la casella che vogliamo riempire, quindi non ne posso mai scrivere due uguali».
«Benissimo. Ora osserva la griglia che contiene solo *0 e *1».
«Quella blu».
«Quella: è composta da due righe e due colonne; se voglio allargarla succederà prima o poi che i due nimeri che la compongono, *0 e *1, si devono trovare al di fuori della zona blu».
«Senza dubbio: *0 e *1 sono i due nimeri più piccoli, nella regola del Mex saltano fuori in fretta».
«E allora quando mi capiterà di avere *0 e *1 fuori dalla zona blu, nella zona blu dovranno esserci altri due nuovi nimeri».
«Ah! Ecco perché devo aumentare di due caselle! E dopo avrò a disposizione quattro nimeri, e se vorrò allargare la zona gialla ce ne vorranno altri quattro, poi otto, sedici, trentadue…».
«Perfetto, hai capito. Non ti spaventerà dunque questa regola:».
1. Se a e b sono minori di 2k, allora lo sarà anche *a + *b.
«Non mi spaventa, è quello che abbiamo detto finora. La regola dei colori, insomma».
«Benissimo. Un'ultima considerazione: osserva la prima riga (o la prima colonna) di ogni nuova cornice».
«Cioè quando cambiano colore?».
«Sì, esatto».
«Boh, la prima riga blu è *1, *0».
«Poi?».
«La prima riga gialla è *2, *3, *0, *1».
«Poi la prima riga viola è *4, *5 , *6, *7, *0, *1, *2, *3».
«E la prima riga fucsia è *8, *9, *10, *11, *12, *13, *14, *15, *0, *1, *2, *3, *4, *5, *6, *7, quindi?».
«Quindi succedono varie cose. Prima di tutto, ogni riga di un colore nuovo parte da una potenza di 2».
«Ok, un altro modo di dire quello che abbiamo visto prima».
«Già. Poi, grazie alla regola del Mex, le righe di un nuovo colore proseguono in ordine crescente fino a metà lunghezza».
«Vero anche questo, prima ci sono i nuovi nimeri, poi quelli vecchi».
«Quindi, riassumendo, se prendiamo come esempio la prima riga viola, quella che comincia con *4, *5, *6, *7, e ci ricordiamo che quei nimeri sono il risultato di una somma, possiamo dire questo:».
*4 + *0 = *4
*4 + *1 = *5
*4 + *2 = *6
*4 + *3 = *7
«E poi ci fermiamo, perché *4 + *4 non fa *8 ma *0».
«Bene. Generalizzando, cosa possiamo dire?».
«Uhm, forse possiamo dire che se prendiamo una potenza di 2 e sommiamo dei nimeri, è come se facessimo una somma normale?».
«Quasi. La regola vale solo fino a metà riga, nel nostro esempio fino a *4 + *4 escluso».
«Ok, allora ho capito, provo a formulare la regola: se sommo una potenza di 2 con un nimero minore di essa, è come se stessi facendo una somma tra normali numeri».
«Bene, in formule è così:».
2. Se a < 2k, allora *a + *2k = *(a + 2k).
«Capito».
«Da cui deduciamo subito queste regole pratiche:».
3. La somma-nim di due diverse potenze di 2 è uguale alla loro somma ordinaria, e la somma-nim di due numeri uguali è 0.
«Perché dici somma-nim?».
«Per non mettere tutti gli asterischi, e per non dover specificare ogni volta che le potenze di 2 che consideriamo sono dei nimeri».
«Ah, ok. E come mai le hai chiamate regole pratiche?».
«Perché ci permettono di fare molto in fretta i calcoli. Ti faccio qualche esempio: vogliamo calcolare il risultato di questa operazione:».
5 ⊕ 3
«Cos'è quello strano simbolo?».
«Significa che stiamo addizionando nimeri, è come se avessi scritto *5 + *3. Dato che dobbiamo fare un po' di calcoli, mi pare che sia più comodo. Tieni presente che quando scrivo ⊕ intendo l'addizione tra nimeri, mentre quando scrivo + intendo la normale addizione tra numeri».
«Ah, va bene. Allora, dobbiamo calcolare 5 ⊕ 3».
«Sì, utilizzando solo la regola pratica, cioè quella che abbiamo indicato col numero 3».
«Ma è una regola che parla di potenze di 2, o di numeri uguali».
«Vorrà dire che dobbiamo trasformare quei numeri in potenze di 2».
«Come se stessimo facendo un cambiamento di base?».
«Esattamente, ottimo! 5 in base 2 è uguale a 101, cioè 4 + 1».
«Mentre 3 è uguale a 11, cioè 2 + 1».
«E quindi il nostro calcolo diventa questo:».
5 ⊕ 3 = (4 + 1) ⊕ (2 + 1)
«E adesso come facciamo? Abbiamo due diversi simboli di somma».
«La somma-nim di due diverse potenze di 2 è uguale alla loro somma ordinaria, quindi scrivere 4 + 1 è come scrivere 4 ⊕ 1».
«Ah, allora possiamo togliere le parentesi e usare solo il simbolo della somma-nim:».
5 ⊕ 3 = 4 ⊕ 1 ⊕ 2 ⊕ 1
«Ora ricordati che la somma-nim di due numeri uguali è uguale a 0».
«E quindi posso scrivere questo:».
5 ⊕ 3 = 4 ⊕ 1 ⊕ 2 ⊕ 1 = 4 ⊕ 2
«Ora hai due potenze di 2 da sommare, quindi…».
Quindi posso calcolare il risultato: 4 ⊕ 2 = 4 + 2 = 6
«Benissimo. Se vogliamo utilizzare la notazione a cui siamo abituati, abbiamo calcolato che *5 + *3 = *6».
«Concorda con la tabella».
«Col vantaggio che non abbiamo avuto bisogno di consultarla per poter calcolare il Mex».
«Bello, si dovrebbe riuscire a fare i calcoli più in fretta».
«È così. Prova per esempio a calcolare questo:».
11 ⊕ 22 ⊕ 33
«Uh, questi sono numeri fuori dalla tabella. Allora, prima scompongo in potenze di 2 i vari numeri».
11 = 8 + 2 + 1
22 = 16 + 4 + 2
33 = 32 + 1
«E fin qua ci siamo».
«Poi addiziono tutto».
«Sì, ma ti conviene già scartare le coppie di numeri uguali».
«Ah, giusto: si annullano. Allora mi rimane questo:».
8 ⊕ 16 ⊕ 4 ⊕ 32 = 60
«Molto bene. Ora che hai capito, puoi anche abbreviare i calcoli e, se vuoi, usare l'altra notazione. Per esempio:».
*9 + *25 + *49 = (*8 + *1) + (*16 + *8 + *1) + (*32 + *16 + *1) = *32 + *1 = *33
«Ah, hai colorato le potenze che si semplificano».
«Sì, come vedi è molto comodo. Ora, una domanda: se noi facessimo la somma normale, otterremmo un numero certamente più grande o più piccolo di quello che otterremmo facendo la somma-nim?».
«Mh, a volte viene uguale, mentre altre volte più grande, dato che nella somma-nim ci sono delle possibili semplificazioni».
«Molto bene, quindi potremmo dire che a ⊕ b ≤ a + b».
«Direi proprio di sì».
«Un'ultima domanda: quando le due somme sono diverse, per cosa differiscono?».
«Per le potenze di 2 che ho semplificato».
«Bene, e posso dire che ogni volta che faccio una semplificazione tolgo due copie dello stesso numero?».
«Certo».
«E quindi tolgo un numero pari ogni volta».
«Ho capito: le due somme differiscono per un numero pari (o per 0, quando non ci sono semplificazioni, ma tanto anche 0 è pari)».
«Perfetto. Ecco l'ultima regola di oggi:».
4. La somma-nim è minore o uguale della somma usuale, ed esse differiscono per un numero pari.
«E quindi?».
«E quindi ora possiamo parlare di una strategia vincente per il Nim».
Iscriviti a:
Post (Atom)