Convergenzea cura di

G. Anzellotti, L. Giacardi, B. Lazzari

Emanuele DelucchiGiovanni GaiffiLudovico Pernazza

Giochi e percorsimatematici

Emanuele DelucchiDipartimento di MatematicaUniversita di Brema

Giovanni GaiffiDipartimento di MatematicaUniversita di Pisa

Ludovico PernazzaDipartimento di MatematicaUniversita di Pavia

isbn 978-88-470-2615-5 isbn 978-88-470-2616-2doi 10.1007/978-88-470-2616-2

Springer Milan Dordrecht Heidelberg London New York

© Springer-Verlag Italia 2012

Questo libro e stampato su carta FSC amica delle foreste. Il logo FSCidentifica prodotti che contengono carta proveniente da foreste gestitesecondo i rigorosi standard ambientali, economici e sociali definiti dalForest Stewardship Council

Quest’opera e protetta dalla legge sul diritto d’autore e la sua riproduzione anche parziale e ammessa esclu-sivamente nei limiti della stessa. Tutti i diritti, in particolare i diritti di traduzione, ristampa, riutilizzodi illustrazioni, recitazione, trasmissione radiotelevisiva, riproduzione su microfilm o altri supporti, in-clusione in database o software, adattamento elettronico, o con altri mezzi oggi conosciuti o sviluppati infuturo,rimangono riservati. Sono esclusi brevi stralci utilizzati a fini didattici e materiale fornito ad usoesclusivo dell’acquirente dell’opera per utilizzazione su computer. I permessi di riproduzione devono esse-re autorizzati da Springer e possono essere richiesti attraverso RightsLink (Copyright Clearance Center).La violazione delle norme comporta le sanzioni previste dalla legge.Le fotocopie per uso personale possono essere effettuate nei limiti del 15% di ciascun volume dietro pa-gamento alla SIAE del compenso previsto dalla legge, mentre quelle per finalitffk di carattere professio-nale, economico o commerciale possono essere effettuate a seguito di specifica autorizzazione rilascia-ta da CLEARedi, Centro Licenze e Autorizzazioni per le Riproduzioni Editoriali, e-mail autorizzazio-ni@clearedi.org e sito web www.clearedi.org.L’utilizzo in questa pubblicazione di denominazioni generiche, nomi commerciali, marchi registrati ecc.,anche se non specificatamente identificati, non implica che tali denominazioni o marchi non siano protettidalle relative leggi e regolamenti. Le informazioni contenute nel libro sono da ritenersi veritiere ed esatteal momento della pubblicazione; tuttavia, gli autori, i curatori e l’editore declinano ogni responsabilitffklegale per qualsiasi involontario errore od omissione. L’editore non pu quindi fornire alcuna garanzia circai contenuti dell’opera.

Immagine di copertina: disegno di Chiara NociLayout copertina: Valentina Greco, MilanoProgetto grafico e impaginazione: CompoMat S.r.l., Configni (RI)Stampa: GECA Industrie Grafiche, Cesano Boscone (MI)

Springer-Verlag Italia S.r.l., Via Decembrio 28, I-20137 MilanoSpringer fa parte di Springer Science + Business Media (www.springer.com)

(eBook)

Prefazione

Questo volume e dedicato a tutti gli appassionati di matematica, e nasce daun’esperienza concreta. Da vari anni presso il Dipartimento di Matematica del-l’Universita di Pisa viene organizzata, a cura di Rosetta Zan e Pietro Di Marti-no, la ‘Settimana Matematica’. Si tratta di una iniziativa all’interno del ProgettoLauree Scientifiche, rivolta agli studenti degli ultimi anni delle scuole superiori.Uno degli ingredienti principali di questa iniziativa sono i ‘laboratori’, pensati permettere gli studenti a diretto contatto con l’attivita matematica, accompagnandolinello studio di problemi che chiamano in causa le loro conoscenze, ponendolepero sotto prospettive nuove.

Abbiamo organizzato piu volte il laboratorio dedicato ai giochi e quello dedi-cato alla topologia nell’ambito della Settimana Matematica. L’esperienza fatta aPisa ci ha poi incoraggiato a proporre i nostri laboratori anche in altre occasioni– in Italia, in Europa e negli Stati Uniti. In tutte queste situazioni abbiamo po-tuto osservare che i giochi costituiscono uno strumento didattico molto efficace.L’interesse degli studenti viene subito attirato dal meccanismo del gioco, e tutti sisentono coinvolti gia dalle prime ‘partitelle’ che servono per capire le regole. Poi,piano piano, l’esigenza agonistica di capire ‘come funziona’, ‘cosa fare per vincere’,interpella i ragazzi: e qui che inizia il percorso matematico.

L’insegnante si trova in una situazione favorevole per tre importanti motivi:l’interesse degli studenti e molto alto fin dall’inizio; l’approccio matematico allostudio dei giochi e convincente perche offre risultati concreti e... agonisticamenteutili; infine, gli argomentimatematici che ‘si nascondono’ nel meccanismo di certigiochi (che vanno opportunamente scelti) sono molto significativi. Pensiamo alprocesso di astrazione che porta alla definizione chiara di cosa vuol dire ‘possede-re una strategia vincente fin dall’inizio’ e alla scoperta che, nei giochi considerati,uno dei due giocatori effettivamente la possiede o alla costruzione di algoritmiche permettono di risolvere un rompicapo e contemporaneamente portano adapprofondire la conoscenza delle permutazioni e dei gruppi. Oppure alla osser-vazione che un gioco con scacchiera e pedine nasconde nel suo meccanismo unimportante teorema sulle funzioni continue; o ancora alla possibilita di giungerea svelare, attraverso una sfida in cui si collegano crocette nel piano con tratti dipenna, la formula di Eulero per i grafi planari e i poliedri.

Il presente volume offre agli insegnanti un supporto per intraprendere questopercorso didattico che parte dai giochi e si inoltra nella matematica, mettendo aloro disposizione strumenti per introdurre o approfondire con gli studenti que-stioni di base (le tecniche di dimostrazione, per esempio, come l’induzione o ladimostrazione per assurdo)ma anche per rompere di tanto in tanto gli schemi deiprogrammi scolastici e aprire prospettive nuove. I giochi, infatti, per loro natura,pongono spesso problemi ‘non standard’. Ci sara dunque occasione di incontrare icoefficienti binomiali, i grafi, le permutazioni, i gruppi, le funzioni di piu variabili

Giochi e percorsi matematiciVI

reali, il teorema di punto fisso di Brouwer, gli omeomorfismi, le curve nel piano,i lavori di Eulero e i primi concetti della topologia.

Ma questo volume non e rivolto solo agli insegnanti: confidiamo infatti cheanche gli studenti e tutti gli appassionati di matematica troveranno la lettura utilee piacevole. Abbiamo impostato la trattazione degli argomenti in modo che siapossibile seguire diversi piani di lettura, dedicando spazio alla descrizione degliesempi piu semplici oltre che alle dimostrazioni dei teoremi che entrano in scena.

Il libro e suddiviso in quattro parti, ognuna delle quali e legata ad un gioco oa una famiglia di giochi. Nella prima parte vengono descritti il Chomp, il Nim,il gioco dei divisori, il Chomp sui grafi e tutta una serie di giochi a due giocatoriin cui i concorrenti, al loro turno, ‘mangiano’ qualcosa. La seconda parte e dedi-cata al gioco del 15 e ad altri giochi con blocchetti mobili da far scorrere dentrouna scatola o lungo un grafo. Nella terza parte viene presentato l’Hex, un giococon pedine da posizionare su una scacchiera inventato da Piet Hein e John Nash.Nella quarta parte si discutono giochi con carta e penna (Germogli, Cavoletti diBruxelles, eccetera): in questi giochi due giocatori devono collegare con dei trattidi penna alcuni punti fissati, rispettando certi vincoli. Le quattro parti del librocondividono la stessa struttura, articolata in sei capitoli.

Il primo capitolo si apre con la descrizione delle regole del gioco principale,illustrate con qualche semplice esempio. In un secondo momento si studia ilgioco cercando di capire come funziona e come fare per vincere. A questopunto si osserva che le domande naturali (ossia se esista una strategia vincen-te disponibile gia dall’inizio per uno dei giocatori, quale sia il giocatore chepuo vincere, quale sia esattamente questa strategia) suscitano varie riflessionimatematiche. Si enunciano dunque con precisione queste domande.Nel secondo capitolo si danno risposte alle domande, coinvolgendo i concet-ti matematici che erano nascosti nel meccanismo del gioco. Si offrono di-mostrazioni rigorose mantenendo pero il linguaggio ad un livello facilmenteaccessibile, rimanendo nello spirito del ‘gioco’.Nel terzo capitolo, dal titolo ‘Variazioni sul tema’, si presentano alcuni giochiaffini a quello principale. Chi si avvicina a questo libro anche per giocare tro-vera interessanti varianti con cui cimentarsi, mentre chi e interessato al percor-so matematico notera che a volte basta cambiare piccoli dettagli nelle regole onella situazione iniziale per dare spunto a domande nuove.Il quarto e il quinto capitolo, il cui titolo comincia con ‘In primo piano: ...’ sonodedicati ad un approfondimento dei temi e contenuti matematici che sono alcuore dei ragionamenti utilizzati per rispondere alle domande nate dal gioco.Il linguaggio diviene piu formale, senza scollegarsi pero completamente dagliesempi dei giochi. L’insegnante potra utilizzare questi approfondimenti peraccompagnare gli studenti nel percorso che porta gradualmente dall’intuizioneall’esigenza di cercare conferme attraverso delle dimostrazioni, dallo studio diun problema particolare alla scoperta di teoremi e tecniche generali, dandouna ‘prima introduzione’ a concetti matematici di grande importanza.L’ultimo capitolo offre una lista di esercizi che insistono sugli argomenti pre-sentati nei ‘primi piani’. Gli esercizi si aggiungono a quelli che, intercalati nel te-

PrefazioneVII

sto dei capitoli precedenti, riproducono le domande poste agli studenti durantele lezioni. Talvolta abbiamo incluso dei suggerimenti per lo svolgimento.

Completano il libro un’appendice che contiene informazioni sulle esperienze di-dattiche e sui laboratori che abbiamo organizzato (e rimanda alla pagina webhttp://www.maestran.ch/giochi/index.html in cui si possono trovare maggio-ri dettagli e dati aggiornati) e una seconda appendice con le soluzioni di alcuniesercizi proposti nel testo.

Il legame fra i giochi e i principali argomentimatematici discussi nel libro vienerappresentato nello schema riassuntivo che conclude questa prefazione. Le lineecontinue collegano gli argomenti trattati nei ‘primi piani’ ai rispettivi giochi. Lelinee tratteggiate indicano quali legami fra i vari argomenti vengonomessi in lucenel nostro ‘racconto’.

Desideriamo ringraziare gli organizzatori della SettimanaMatematica, RosettaZan e Pietro Di Martino, per averci incoraggiato con il loro entusiasmo e forni-to preziose indicazioni rileggendo le versioni preliminari del lavoro, e FabrizioBroglia che ci ha dato l’idea di questo percorso didattico sui giochi. Ringraziamoanche anche Alberto Abbondandolo, Francesca Acquistapace, Alessandro Berar-ducci, Mauro Di Nasso e PietroMajer, per i consigli sulle lezioni e le conversazio-ni sui giochi, Maurice Froidcoeur per l’attenta lettura della versione preliminaredi alcuni capitoli. Un ringraziamento speciale va infine a Marco Golla e GiulioTiozzo, che hanno condiviso con noi questa esperienza nei primi laboratori.

Pisa, gennaio 2012 Emanuele DelucchiGiovanni Gaiffi

Ludovico Pernazza

Giochi e percorsi matematiciVIII

Chomp

Gioco del 15 Hex

Cavoletti diBruxelles

Costruzione del grafo del gioco.

Esistenza di una strategia vincente.

Ricerca di strategie concrete.

Induzione

T������������TT

PermutazioniGruppi

CombinatoriaInvarianti

Continuità

�������� essioni diTopologia

Poliedri eFormula di Eulero

Teorema di������sso

Indice

Parte I Chomp

1. Il Chomp: presentazione e prime domande 3

2. Risposte: giochi combinatori finiti e la ‘mossa rubata’ 7

2.1 I giochi combinatori finiti 7

2.2 La teoria della mossa rubata 9

2.3 Cenni sulla tattica 10

3. Variazioni sul tema 13

3.1 Il gioco dei divisori, ossia... l’iperChomp 13

3.2 Buffet di biscotti: il gioco del Nim 14

3.3 Il Chomp sui grafi 16

4. In primo piano: il principio di induzione 19

4.1 Un passo dopo l’altro... 19

4.2 Un’applicazione: le configurazioni del Chomp 22

4.3 I coefficienti binomiali 24

5. In primo piano: la teoria dei grafi 27

5.1 Definizioni 27

5.2 Il Primo Teorema sui grafi 31

5.3 I ponti di Konigsberg 32

5.4 Il Chomp sui grafi 36

6. Altri esercizi 39

6.1 Strategie per vincere o... non perdere 39

6.2 Un po’ di pratica con l’induzione e i coefficienti binomiali 39

6.3 Esercizi sui grafi 45

Giochi e percorsi matematiciX

Parte II Quindici

7. Il Quindici: presentazione e prime domande 49

8. Risposte: invarianti e algoritmi 538.1 Una curiosa somma invariante 538.2 L’invariante... alla prova di una mossa 558.3 Un algoritmo e un trucco utile 568.4 Alcune curiosita 58

9. Variazioni sul tema 599.1 Foto di famiglia: il gioco del 15 e i grafi con etichette 59

10. In primo piano: gruppi e permutazioni 6310.1 Permutazioni 6310.2 Gruppi e permutazioni 6610.3 Pari o dispari? 6710.4 Di nuovo il gioco del 15 6910.5 L’invariante del gioco del 15 ‘svelato’ 7010.6 Il vantaggio di essere saliti piu in alto 71

11. In primo piano: invarianti 7311.1 Verso una prima definizione 7311.2 Azione! 75

12.Altri esercizi 7712.1 Gruppi e permutazioni 7712.2 Il gioco del 15 7812.3 Invarianti per griglie e scacchiere 8012.4 Azione sui sistemi di equazioni 81

Parte III Hex

13. L’Hex: presentazione e prime domande 89

14.Risposte: percorsi e curve, sulla scacchiera e nel piano 9514.1 Il teorema dell’Hex 95

IndiceXI

14.2 La mossa rubata per l’Hex 10014.3 Il teorema di Jordan per le curve poligonali 101

15.Variazioni sul tema 10715.1 Curiosita e scacchiere asimmetriche 10715.2 La variante della ‘doppia mossa’ 10815.3 Hex ‘alla rovescia’ 10915.4 Il Gale 109

16. In primo piano: continuita di funzioni 11116.1 Saltando, oscillando, verso la definizione di continuita 11116.2 Il punto d’arrivo 11716.3 Funzioni continue e proprieta fondamentali dei numeri reali 12016.4 L’importanza di essere uniformi 12316.5 L’appetito vien generalizzando. Cercare di arrivare al piano dalla

retta, finendo per scoprire la topologia 124

17. In primo piano: il teorema di Brouwer e primi assaggi di

topologia 12917.1 Il teorema della curva di Jordan 12917.2 Il teorema di Brouwer (attraverso l’Hex) 131

18.Altri esercizi 13718.1 Ancora giochi 13718.2 Funzioni continue 13818.3 Uniforme continuita e omeomorfismi 14018.4 Il teorema della curva di Jordan 14118.5 Il teorema del punto fisso di Brouwer 142

Parte IV Cavoletti di Bruxelles

19. I Cavoletti di Bruxelles: presentazione e prime domande 147

20.Risposte: finitezza, strategia, . . . topologia! 15120.1 Finito... o no? 15120.2 Strategia... o no? 15420.3 Gioco combinatorio finito... o no? 15520.4 Oltre le verdure, fino alla formula di Eulero 156

Giochi e percorsi matematiciXII

21.Variazioni sul tema 15921.1 Germogli 15921.2 Stelline 162

22. In primo piano: grafi planari 16322.1 Grafi planari 16322.2 La formula di Eulero 165

23. In primo piano: poligoni, poliedri, perplessita e topologia 16923.1 Cosa e un poliedro? 16923.2 Verso la geometria delle forme: la topologia 172

24.Altri esercizi 17724.1 Germogli e dintorni 17724.2 Grafi planari e formula di Eulero 178

Parte V Appendici

A. I giochi come concreta esperienza didattica 183

B. Soluzioni e suggerimenti per alcuni degli esercizi proposti 185B.1 Esercizio sul gioco del Nim e sulla Nim-sommaB.2 Esercizio sul teorema di Jordan per i poligoniB.3 Esercizio sui solidi platoniciB.4 Esercizi sulle pavimentazioni della sfera

185186188189

Bibliografia

Indice analitico

191

195