PAPERINO E I PONTI DI QUACKENBERGLA TEORIA DEI GRAFI A FUMETTI

ALBERTO SARACCO

Sommario. In queste note voglio proporre alcuni possibili percorsi didattici di geome-tria, sulla teoria dei grafi, basati sul fumetto Paperino e i ponti di Quackenberg [1] a cuiho avuto l’onore di collaborare.

Il soggetto della storia e frutto di una collaborazione fra me e lo sceneggiatore DisneyFrancesco Artibani, che ne ha anche curato con grande attenzione la sceneggiatura. Idisegni sono opera di Marco Mazzarello.

La storia tratta di un famoso problema che ha dato i natali alla teoria dei grafi, ilproblema dei ponti di Konigsberg.

I percorsi didattici sono adatti a varie classi, indicativamente dalla seconda classe dellaprimaria alla seconda classe della secondaria di secondo grado.

Figura 1. La vignetta iniziale della storia. © Disney

Date: 11 febbraio 2018.

1

2 A. SARACCO

1. Introduzione

Insegnare matematica in modo divertente e una missione obbligata.

Divertendosi si impara meglio.

Il fumetto e il medium ideale per divulgare la geometria anche ad alti livelli.

Sicuramente da queste mie considerazioni [4], oltre che dalla mia passione per il fumettoDisney, per la matematica e per la divulgazione, e nata l’idea di trasformare un problemaclassico di geometria, i ponti di Koenigsberg, in un’avventura di paperi.

Non e certo una novita che nelle storie Disney si tratti di scienza o di matematica, finquasi dalla sua nascita. La scienza su Topolino e stata anche oggetto di tesi di laurea (adesempio [2]).

Nel 2016 e poi stato ufficializzato il progetto Topolino Comic&Science, che porta suTopolino storie a tema scientifico seguite direttamente da scienziati esperti nel settore,corredate da approfondimenti. Il progetto e affidato ai due storici sceneggiatori FrancescoArtibani e Fausto Vitaliano.

Il progetto ha forti punti di contatto con Comics&Science di Roberto Natalini e AndreaPlazzi, che dal 2013 si occupa di divulgazione scientifica attraverso il fumetto.

La vera novita ne i ponti di Quackenberg e la presenza di una dimostrazione all’internodei fumetti: ben 2 tavole e mezza (tavole 25-26 e meta della 27)1 sono dedicate alladimostrazione di un’affermazione di Eulero de’ Paperis (a tavola 24). La dimostrazionepresente nella storia e frutto quasi interamente della penna di Francesco Artibani, che sie preparato sul problema sotto la mia guida prima di dedicarsi alla sceneggiatura. Le miecorrezioni alla sua dimostrazione sono state minime.

A seguito dell’esperienza di scrittura del fumetto, ho presentato la storia nelle scuole, indue contesti profondamente diversi tra loro: una classe di seconda primaria e un gruppodi classi di prima e seconda secondaria di primo grado.

Mi sono convinto che la storia Paperino e i ponti di Quackenberg possa essere bensfruttata per vari laboratori nelle scuole, a piu livelli, dalla scuola primaria alla scuolasecondaria di secondo grado.

Questa nota vuole fornire agli insegnanti delle idee per tali laboratori.

Dopo una breve introduzione sul problema dei ponti di Koenigsberg e un riassunto dellastoria, parlero dei possibili laboratori, divisi per classi.

Se non avete ancora letto Paperino e i ponti di Quackenberg e non volete rovinarvi lastoria, fatelo ora. Da qui in avanti saranno presenti numerosi spoiler.

2. La storia e il problema

In questa sezione delineiamo gli avvenimenti principali della storia, intrammezzati incolore differente da leggende e aneddoti sul problema originale dei ponti di Koenigsberge sulla risoluzione di Eulero del problema.

1In questa nota indico sempre le tavole, per non vincolarmi alle pagine della prima apparizione dellastoria su Topolino. La pagina corrispondente alla tavola n in Topolino 3232 e la pagina 104 + n.

Per trovare l’elenco di tutte le pubblicazioni della storia, vedi la pagina inducks di Paperino e i pontidi Quackenberg : https://inducks.org/s.php?c=I+TL+3232-3

PONTI DI QUACKENBERG 3

Come preannuncia la didascalia della prima vignetta (figura 1), i fatti si svolgono aQuackenberg, perla del nord Europa (nella realta Koenigsberg, in Prussia), nel 1736(anno in cui Eulero si e effettivamente occupato del problema dei ponti di Koenigsberg,vedi [3], pagine 71–73).

La cittadina e attravesata dal fiume Pretzel (Pregel nella realta) che “ha regalato dueisole [...] alla citta” (vedi figura 2). Le isole e le sponde del fiume sono collegate tra loroda sette ponti (come schematizzato in figura 3).

Figura 2. Il fiume Pretzel e le isole di Quackenberg (tavola 4)© Disney

Figura 3. Schema delle isole e dei ponti di Quackenberg; a destra il grafocorrispondente

La vicenda inizia nella bottega di nonna Strudel (interpretata da nonna Papera), dovevengono sfornati vari dolcetti per gli abitanti della citta. Paperino e il garzone dellabottega e ha il compito di consegnare i prodotti del forno in giro per la citta. Il suolavoro e reso gravoso dalla tassa di attraversamento dei ponti imposta dal borgomastrodi Quackenberg, che altri non e che suo zio Paperone.

4 A. SARACCO

In seguito ad un ennesimo sopruso, Paperino ha un battibecco con un gabelliere. Ilborgomastro si accorge del fatto e —dopo un breve colloquio col nipote disutile— proponea Paperino una sfida (tavole 7-8):

Se sarai in grado di attraversare i sette ponti senza mai passare due volte per lo stesso,riservero una tariffa speciale a tutti i garzoni.

Paperino accetta la sfida e si prepara fiducioso a trovare la strada che passa attraversoi sette ponti. La saggia nonna Strudel e gli avveduti Qui, Quo e Qua sospettano che laprova sia piu ardua del previsto, ma questo non scoraggia Paperino.

L’impresa in effetti non e affatto semplice. La leggenda vuole che gli abitanti di Koe-nigsberg provassero ad attraversare i sette ponti senza mai passare due volte dallo stesso.Ogni tanto qualcuno, di ritorno dalla birreria, raccontava di essere riuscito a farlo, manessuno era in grado di ripetere il percorso da sobrio, alla luce del sole.

Dopo vari tentativi di trovare un percorso che passi su tutti i ponti una e una sola volta,Paperino si fa sempre piu scuro in volto e decide infine di rivolgersi alla “mente piu genialedi Quackenberg”, Eulero de’ Paperis (interpretato ovviamente da Pico de’ Paperis, tavola12).

Per quanto riguarda la vera Koenigsberg, e il sindaco della vicina Danzica che il 6 marzo1736 pone il problema a Eulero. Eulero rispondera con la soluzione il successivo 3 aprile(vedi [3], pagina 72).

Il matematico si mette al lavoro, mentre Paperino compie tentativi sempre piu comiciper riuscire nel suo intento e finisce col coinvolgere tutta la citta nell’avvincente sfida delborgomastro. La cittadina piomba nel caos, quando finalmente arriva Eulero de’ Paperiscon la sua soluzione del problema. Eulero annuncia che il problema non ammette soluzione(vedi figura 4).

Figura 4. Eulero de’ Paperis annuncia la sua conclusione (tavola 25)© Disney

Leggermente diverso e l’atteggiamento avuto verso il problema da parte di Eulero de’Paperis e Leonhard Euler. Il personaggio di fantasia dichiara che “la questione era in-gannevole, ma nascondeva un bel problema di geometria, la piu nobile delle branche della

PONTI DI QUACKENBERG 5

matematica” (vedi figura 5), mentre Leonhard Euler scrive che “la questione e molto ba-nale, ma mi sembra degna di considerazione, in quanto ne la geometria ne l’algebra eneppure l’arte di contare sono sufficienti a risolverla”2.

Figura 5. Eulero de’ Paperis parla del problema dei sette ponti (tavola25) © Disney

Entrambi, pero, concordano sulla necessita della nascita di una nuova area della mate-matica per affrontare il problema: Leonhard Euler afferma “dato tutto questo, mi sonochiesto se appartenesse a quella geometria di posizione [geometria situs ] che Leibniz untempo aveva tanto desiderato”3, mentre la sua controparte papera afferma con maggioreottimismo “la citta con i suoi ponti mi ha dato lo spunto per inaugurare una nuova disci-plina! La chiamero topologia [...] geometria situs o geometria di posizione” (vedi figura6). Il nome topologia in questo contesto storico e una licenza letteraria, dato che saraintrodotto oltre un secolo piu tardi, a meta Ottocento.

Le due tavole e mezzo successive sono destinate alla dimostrazione di quanto enunciatoda Eulero de’ Paperis (per approfondire sulla dimostrazione, vedi la sezione 4 a pagina14).

Scoperta l’impossibilita della sfida del borgomastro, Paperone rischia il linciaggio dellafolla e si salva solo promettendo l’abolizione della tassa di attraversamento, salvo poiannunciare che “tolta una [tassa] se ne fa un’altra”, oltre alla sua intenzione di costruireun ottavo ponte (tavola 30).

3. Il laboratorio

Qualunque sia la vostra classe di insegnamento, vi consiglio comunque di leggere tuttele proposte di laboratorio seguenti. In primis perche non sono un esperto di didattica, masolo un appassionato di divulgazione, in secundis perche e sempre bene avere un quadropiu ampio rispetto a quanto si intende presentare in classe e infine perche non tutte leclassi sono uguali e la cosa migliore e presentare un laboratorio ritagliato sulla propriaclasse ispirato alle idee che vi provo a fornire.

2Lettera di Leonhard Euler a Giovanni Marinoni, 13 marzo 1736, citata in [5], traduzione italiana [3],pagina 73

3Sempre nella lettera citata sopra

6 A. SARACCO

Figura 6. La topologia o geometria di posizione (tavola 25)© Disney

3.1. 2°-3° anno scuola primaria. Questa che segue e l’effettiva descrizione di un la-boratorio che ho effettuato in prima persona nella classe di mia figlia Sofia, una secondaprimaria, a fine ottobre 2016, una settimana prima dell’uscita in edicola di Topolino 3232.I bambini hanno risposto con grandissimo entusiasmo e si sono applicati a tutti i compitipratici-laboratoriali che ho dato loro. Hanno seguito con grande interesse la storia, anchese riportare la calma dopo le singole attivita laboratoriali e stata dura. In cio sono statofortemente aiutato dalle maestre Loredana e Silvia, che hanno contribuito al laboratorio.

Avendolo effettuato a inizio anno scolastico un una seconda primaria, sono piu chesicuro che sia adatto all’eta. L’unico prerequisito e la conoscenza dei concetti di pari edispari.

Gran parte del laboratorio si basa sulla lettura della storia. L’ideale e proiettare la storiasulla LIM della classe. In assenza di LIM o di proiettore, si puo fare una lettura condivisadel fumetto, con ogni bambino che segue dalla propria copia, mentre qualcuno legge adalta voce. Penso pero che questa seconda opzione sia meno efficace. Soprattutto, per labuona riuscita del laboratorio sarebbe bene che i bambini non sbirciassero il proseguiodella storia.

Si puo presentare l’attivita come un laboratorio su un vero problema di matematica,trasposto poi nel mondo dei paperi Disney. Se siete dei conoscitori dei personaggi Disney,puo essere divertente intermezzare al racconto delle domande ai bimbi, del tipo: all’ultimavignetta di tavola 4, Chi guida la carrozza? [Battista, storico maggiordomo di Paperone]Chi ci sara dentro la carrozza? [il borgomastro Paperone]; a tavola 8, di solito le sfidetra zio Paperone e Paperino finiscono bene per il nipote? [No]...

Si inizia leggendo il fumetto. Arrivati alle vignette delle tavole 7-8 in cui il borgomastroPaperone propone la sfida e bene assicurarsi che i bambini abbiano capito bene la sfidaposta a Paperino: attraversare tutti i sette ponti passando su ognuno una e una solavolta.

Giunti alla fine di tavola 9 si interrompe la lettura e si propone la sfida ai bambini: voleteprovare ad affrontare la sfida proposta da zio Paperone? Voi sareste capaci di vincere lasfida? Consegnate ad ogni bambino una mappa schematizzata di Quackenberg, mentre laproiettate alla LIM e rispiegate bene il compito che devono affrontare. Puo andare bene

PONTI DI QUACKENBERG 7

lo schema in figura 3 a pagina 3, ma probabilmente i bambini apprezzerebbero di piu lafigura 7, tratta dalle tavole 26 e 27 della storia, con i dialoghi rimossi.

Figura 7. La sfida: riuscite a trovare un percorso che passi da ogni ponteuna e una sola volta? © Disney

8 A. SARACCO

Accertatevi che tutti i bambini abbiano capito cosa devono fare e magari fate rispiegarele regole della sfida a qualcuno di loro. Date circa 10 minuti per affrontare la sfida erendersi conto che e davvero difficile. Puo essere una buona idea farli lavorare a gruppi.Nonostante il compito sia impossibile, quasi tutti riusciranno nell’impresa: tuffandosi nelfiume, uscendo dalla pagina per passare da una sponda all’altra, toccando l’inizio di unponte senza attraversarlo, dimenticandosi di un ponte, attraversandone uno piu volte...Vi chiameranno di continuo con le loro soluzioni. Armati della sicurezza che il compito eimpossibile, con pazienza seguite la loro soluzione e spiegate perche e sbagliata.

Quando si saranno resi conto della difficolta, provate a riportare la calma per riprenderea leggere la storia... “la sfida sembra davvero difficile, vogliamo vedere come se la cavaPaperino?”

Riprendendo la lettura dalla tavola 10, si seguono le peripezie di Paperino fino allarivelazione di Eulero de’ Paperis sull’impossibilita di trovare una soluzione (tavola 24).Qui e possibile osservare alcune reazioni da parte dei bambini, tra il perplesso, l’offeso eil tradito per il fatto che l’insegnante ha dato loro un compito che mai avrebbero potutorisolvere!

Dopo aver letto la tavola 25 (pagina 129 in [1]) puo essere utile guidare gli alunniattraverso la dimostrazione, magari proiettando nuovamente la mappa su cui si eranoesercitati a trovare una soluzione, ovvero la figura 3 o 7. Anziche procedere con la letturadel fumetto, ci si affida alla mappa di Quackenberg muta mentre l’insegnante interpretaEulero de’ Paperis cercando di guidare man mano gli alunni alla comprensione delladimostrazione, cosı come Paperino e guidato. Si sviluppera un bel dibattito, con glialunni che cercheranno di dire la loro. Per prepararsi al compito, consiglio all’insegnantedi leggere bene la sezione 4 a pagina 14 di questo articolo.

Dopo aver visto la dimostrazione, si puo riprendere la lettura dalla tavola 27, fino allaconclusione. Paperone nell’ultimissima vignetta della storia annuncia che costruira unottavo ponte per poi riprendere la sfida con Paperino.

Dopo la costruzione dell’ottavo ponte, si puo effettivamente trovare un percorso chepassi su tutti gli otto ponti una e una sola volta (anzi, ce ne sono molti diversi tra loro).Si puo quindi proporre la mappa in [4] (pagina 141), qui riprodotta in figura 8, chiedendodi trovare un percorso. Consiglio di far notare ai bambini che ora si puo fare4, dato cheora ci sono due zone con un numero pari di ponti (l’isola di sinistra e la sponda in basso,entrambe con 4 ponti) e solo due con un numero dispari di ponti (l’isola di destra, 5 ponti,e la sponda in alto, 3 ponti).

Per concludere l’attivita laboratoriale si puo far colorare qualche disegno stampato dallastoria o qualche disegno di paperi, per rilassarsi a fine attivita.

3.2. 4°-5° anno scuola primaria. Per gli ultimi due anni della scuola primaria, propor-rei un percorso essenzialmente simile a quello visto per le classi seconde e terze.

L’unica variazione che si puo provare e alla fine della lettura della storia. QuandoPaperone annuncia che costruira un ottavo ponte per rendere possibile la sfida, anzicheconsegnare ai bambini la mappa con otto ponti (figura 8), darei loro una nuova copia

4Per essere precisi nella storia abbiamo solo dimostrato che nel caso ci siano piu di due zone con unnumero dispari di ponti e impossibile trovare il percorso richiesto. Dimostrare che se ci sono esattamentedue o zero zone con un numero dispari di ponti il percorso c’e, e piu difficile (vedi sezione 4 a pagina 14).Inutile (anzi forse dannoso) avventurarsi in un discorso di questo tipo con bambini della primaria).

PONTI DI QUACKENBERG 9

Figura 8. Paperone ha costruito l’ottavo ponte© Disney

intonsa della mappa con sette ponti gia usata (figura 3 o 7) chiedendo loro dove costrui-rebbero l’ottavo ponte e perche, e quindi di trovare un percorso che passi su tutti gli ottoponti.

Ovunque decidano di costruire l’ottavo ponte ci saranno due zone con un numero disparidi ponti e due con un numero pari di ponti. Si puo quindi trovare un percorso che passiper tutti gli otto ponti una e una sola volta5. I bimbi dovrebbero riuscire a trovare variesoluzioni diverse. A partire dalle loro soluzioni si puo cercare di far loro osservare che nonimporta dove si costruisce il ponte, il percorso si trova sempre.

3.3. Scuola secondaria di primo grado. Anche in questo caso ho avuto un’esperienzadiretta.

Per le scuole secondarie di secondo grado sono possibili due conclusioni diverse dellaboratorio. Nel laboratorio da me effettuato ho scelto la prima delle due proposte, datoche avevo di fronte a me 5 classi, per un totale di circa 100-120 studenti. La secondaproposta ritengo sia piu adatta nel caso di un laboratorio per una singola classe.

La prima possibilita e, dopo aver letto la storia e lavorato sulla mappa con gli ottoponti, in una delle due versioni precedentemente proposte, quella di esaminare due diversipossibili approcci al problema dei sette ponti.

5Vale nuovamente il discorso della nota 4.

10 A. SARACCO

Il primo approccio e quello per enumerazione, accennato da Eulero de’ Paperis nellavignetta finale di tavola 12 (vedi figura 9): ovvero elencare tutti i casi possibili e poi

Figura 9. Strategia n.1: esaminare tutti i percorsi possibili (tavola 12)© Disney

vedere quali di questi sodddisfano le richieste del problema.

Una prima possibile enumerazione e quella della successione di ponti percorsi: dopo averassegnato ad ogni ponte una lettera (a, b, c, d, e, f, g) come in figura 10 si consideranotutte le sequenze costituite da quelle sette lettere e si vede se sono percorsi ammissibili ono. Ad esempio:

1 Il percorso abcdefg non e possibile, perche dopo aver percorso i primi sei ponti citroviamo sulla sponda in basso, da cui non parte il ponte g;

2 il percorso abcdegf non e possibile, perche dopo aver percorso i primi sei ponti citroviamo sulla sponda in alto, da cui non parte il ponte f;

3 ...

Il problema e che le sequenze da esaminare sono ben 5040 e la faccenda rischia di farsilunga6.

Una seconda possibile enumerazione e quella delle zone in cui si passa durante il per-corso: dopo aver assegnato ad ogni zona una lettera (A, B, C, D) sempre come in figura10 (e come fa Eulero de’ Paperis, ad esempio in figura 7) si considerano tutte le sequenzecostituite da otto di quelle lettere (senza due lettere consecutive uguali)7 e si vede se sonopercorsi ammissibili o no. Ad esempio:

1 Il percorso ABABABAB non e possibile, perche non passa mai dalle zone C e De quindi non passa per tutti i ponti;

2 il percorso ABCDABCD non e possibile, perche nessun ponte collega le sponde Be C;

3 il percorso ABACADBA non e possibile, perche non ci sono 3 ponti che colleganoA e B;

6Nella prossima sezione, destinata agli studenti piu grandi, vedremo anche perche sono in questonumero.

7Otto, ovvero la zona iniziale e poi una zona di arrivo per ogni ponte da percorrere.

PONTI DI QUACKENBERG 11

Figura 10. Assegnamo ad ogni ponte una lettera minuscola e ad ogni zonauna lettera maiuscola

4 ...

Il problema e che le sequenze da esaminare sono ben 8748 e la faccenda rischia di farsilunga8.

Il problema piu grande nelle tecniche per enumerazione e che aumentano rapidamentedi complessita. Inoltre non ci forniscono un motivo per cui qualcosa si puo o non si puofare: non impariamo nulla dai casi precedenti e ogni volta dobbiamo fare il lavoro da zero.Una dimostrazione matematica invece ci fornisce le vere motivazioni dietro un fatto, cipermette di capire meglio il problema e si generalizza ad altri casi. Come osserva Eulerode’ Paperis “dobbiamo [...] trovare un metodo che funzioni sempre... e poco importache i ponti siano sette o settecento!” (tavola 13, vedi figura 11). Occorre generalizzareil problema particolare, ovvero inserirlo in una classe piu ampia di problemi dello stessotipo e poi fare una dimostrazione che funzioni in generale.

Figura 11. La generalizzazione e fondamentale per affrontare un problemamatematico (tavola 13)© Disney

Nella storia, per ovvi motivi di semplicita, la dimostrazione delle tavole 25-26-27 e fattaper il caso particolare di Quackenberg, ma funziona in generale. La dimostrazione puo

8Come nell’altro caso, nella prossima sezione, destinata agli studenti piu grandi, vedremo anche perchesono in questo numero.

12 A. SARACCO

essere leggermente riadattata per dimostrare (vedi la sezione 4 a pagina 14) il seguenteenunciato:

Teorema 1. Se una citta e divisa in zone collegate da ponti e ci sono piu di due zoneda cui partono un numero dispari di ponti, allora non esiste nessun percorso che passi suogni ponte una e una sola volta.

Puo essere bello far riflettere gli studenti sulla profonda differenza che vi e tra uncaso singolo e un teorema generale... riescono a vedere la dimostrazione dell’enunciatogenerale?

La seconda possibilita e quella di farli lavorare in maniera laboratoriale a coppie oa piccoli gruppi su vari problemi di costruzione di ponti. Molto carini sono ad esempioi seguenti problemi, tratti cosı come sono da Wikipedia [7] (a meno di un’ambientazionepiu paperosa).

Sulla riva meridionale della citta sorge il castello del borgomastro Paperone e sulla rivasettentrionale sorge quello del ricco Rockerduck, acerrimo nemico di Paperone; sull’isolaorientale abita Eulero de’ Paperis; infine nell’isola centrale si trova una la pasticceria dinonna Strudel. In figura 12 il grafo colorato corrispondente a questa situazione.

Figura 12. Il grafo colorato: in blu la sponda di Paperone, in rosso quelladi Rockerduck, in bianco l’isola di Eulero de’ Paperis e in giallo quella dinonna Strudel

L’ottavo ponte del borgomastro Paperone Il borgomastro, dopo aver ascoltatola spiegazione di Eulero de’ Paperis (tavole 24-28 in [1]), si convince dell’impossibilita dipassare i ponti. Decide allora di costruire un ottavo ponte che gli permetta la sera dipassare i ponti partendo dal suo castello e finendo alla pasticceria di nonna Strudel dovepotersi vantare della sua riuscita col nipote Paperino.

Dove costruisce l’ottavo ponte il borgomastro?Il nono ponte di Rockerduck Il ricco Rockerduck, decide di costruire di nascosto

un altro ponte che consenta a lui di traversare i ponti in modo da raggiungere dal suocastello la pasticceria, rendendo nel contempo impossibile al borgomastro fare lo stesso.

PONTI DI QUACKENBERG 13

Dove costruisce il nono ponte Rockerduck?Il decimo ponte di Eulero de’ Paperis Eulero de’ Paperis decide di costruire un

decimo ponte che consenta a tutti i cittadini di passare tutti i ponti e fare ritorno allapropria casa tra i tranquilli affetti familiari, per porre fine alla faida.

Dove costruisce il decimo ponte Eulero de’ Paperis?

3.4. Scuola secondaria di secondo grado. Per gli studenti dei primi anni delle su-periori, la lettura della storia puo essere uno stimolo per indagare alcuni aspetti dellamatematica.

Teoria dei grafi. Dovrebbero essere infatti gia avvezzi al concetto di dimostrazionematematica, grazie alla geometria euclidea. Si puo pertanto chiedere loro di rielaborare ladimostrazione di Eulero de’ Paperis, svolta nel caso particolare delle isole di Quackenbergper dimostrare il piu generale teorema 1.

Per porre la questione in maniera piu generale, possiamo introdurre le seguenti defini-zioni.

Definizione 1. Un grafo Γ e un insieme finito di punti (detti nodi) e di archi ognuno deiquali connette due nodi.

L’indice di un nodo e il numero di archi uscenti da un nodo.Un cammino in Γ e una successione di archi di Γ tali che il nodo finale di un arco

coincida con il nodo iniziale dell’arco successivo.Un cammino euleriano in Γ e un cammino in Γ in cui ogni arco compare una e una

sola volta.Un ciclo euleriano in Γ e un cammino euleriano in Γ in cui il nodo finale del cammino

coincide col nodo iniziale.

Si puo quindi riformulare il teorema 1 nel seguente modo e chiedere agli studenti didimostrarlo.

Teorema 2. Sia Γ un grafo con piu di due nodi con indice dispari. Allora non esistenessun cammino euleriano in Γ.

Due possibili dimostrazioni sono presentate nell’ultima sezione di questa nota.I ragazzi riescono a dimostrare il teorema 2 in tutta generalita, staccandosi dall’inter-

pretazione particolare dei ponti? Sarebbe bello farli riflettere che un tale teorema si puoapplicare anche a problemi apparentemente molto diversi. Ad esempio:

Posso disegnare la busta in figura 13 senza staccare la matita dal foglio e senza ripassaredue volte uno stesso lato?

Il problema e dello stesso tipo del problema dei ponti. La risposta e no: ci sono ben 6nodi di indice dispari.

Combinatoria. Un’altra sfida interessante da proporre agli studenti e quella di con-tare quanti cammini vanno esaminati nei procedimenti per enumerazione (vedi figura 9).La combinatoria e una parte della matematica molto utilizzata nei giochi matematici epermette di esplorare vari metodi di ragionamento interessanti. Per una teoria e variproblemi di combinatoria, si puo vedere ad esempio l’esauriente [6].

La domanda del quanti ne vadano considerati dipende in realta da come intendonoscrivere un cammino. Esamino qui alcune possibilita, ma la cosa migliore e far riflettere iragazzi a piccoli gruppi, ponendoli davanti al problema e facendoli ragionare e discutere.

14 A. SARACCO

Figura 13. Posso disegnare la busta senza staccare la matita dal foglio esenza ripassare due volte uno stesso lato?

Con la prima enumerazione di pagina 10 bisogna permutare in tutti i modi possibili i7 ponti. Questo si puo fare in 7! = 5040 modi (ho 7 scelte per il primo ponte, fissato ilprimo ne ho 6 per il secondo, e cosı via).

Con la seconda enumerazione di pagina 10 devo elencare 8 zone scelte in modo che nonce ne siano due consecutive uguali (4 scelte per la prima zona, 3 per ogni successiva),quindi 4 · 37 = 8748.

Sono possibili ulteriori modi di enumerare i cammini? In che modo li elencherebberotutti? E quanti sono? Il problema quanto cresce di complessita all’aumentare dei ponti odelle zone?

Queste sono tutte domande che possono portare a una discussione interessante in classe.

4. La dimostrazione di Eulero de’ Paperis e quella di Eulero

La dimostrazione svolta nel fumetto del teorema 1 e leggermente diversa rispetto aquella originale di Eulero.

Entrambe le dimostrazioni sono per assurdo, ovvero partono dal presupposto che esistaun percorso con le caratteristiche richieste, per poi ricavarne una contraddizione.

4.1. La dimostrazione di Eulero de’ Paperis.

Dimostrazione. Immaginiamo di avere un percorso che passa su ogni ponte una [e unasola] volta. [...]Ogni volta che il percorso passa in una zona devo usare due ponti, uno per entrare e unoper uscire. [...] Dunque [...] per compiere il percorso [...] abbiamo sempre bisogno di unnumero pari di ponti [per ogni zona attraversata dal percorso.]

Eulero de’ Paperis - [1] tavole 25-27

Pertanto una zona con un numero dispari di ponti puo essere solo la zona di partenzao di arrivo del percorso e quindi se tali zone sono piu di due tale percorso non esiste. �

PONTI DI QUACKENBERG 15

4.2. La dimostrazione di Eulero. Scrivo qui la dimostrazione di Eulero adattata alcaso particolare dei ponti di Koenigsberg/Quackenberg, lasciando nelle note la dimostra-zione generale9. Questa dimostrazione, seppur diversa, si basa sempre sul principio usatonella dimostrazione dell’alter ego papero di Eulero.

Dimostrazione. Supponiamo per assurdo di avere un percorso che passa su ogni ponte unae una sola volta. Assegnando ad ogni zona una lettera come in figura 10, un percorso euna parola di 8 caratteri scritta con queste lettere (come osservato a pagina 10, quandosi parla della seconda possibile enumerazione).

D’altra parte, ogni lettera di una parola identifica uno e due ponti che partono daquella zona (uno solo se e la lettera iniziale o finale della parola) e quindi se dalla zona Xescono k ponti la lettera X deve comparire almeno k/2 volte nella parola che rappresentail percorso passante per tutti i ponti. In particolare la lettera A compare almeno 3 voltenella parola che identifica il percorso, poiche 5 ponti partono da essa, mentre B,C,Dcompaiono ognuna almeno 2 volte.

Pertanto

8 ≥ 3 + 2 + 2 + 2 = 9 ,

assurdo. Non esiste il percorso cercato. �

4.3. Il viceversa del teorema. In realta il teorema di Eulero dice di piu. Precisamentevale anche il viceversa, ovvero dato un grafo connesso (ovvero tale che qualsiasi due nodidel grafo —zone della citta— sono collegate da archi —da ponti—) con al piu due nodi diindice dispari (al piu due zone con un numero dispari di ponti) esiste un percorso eulerianoche passa da ogni arco (ponte) una e una sola volta. Precisamente:

Teorema 3. Se una citta e divisa in zone collegate da ponti e c’e modo di andare da unaqualsiasi zona a una qualsiasi altra usando i ponti, allora:

• esiste un percorso chiuso (cioe con zona finale e iniziale uguali) che passi su tuttii ponti una e una sola volta se e solo nessuna zona ha un numero dispari di ponti;

9Dimostrazione generale.

Dimostrazione. Supponiamo di avere un percorso che passa su ogni ponte una e una sola volta. Asse-gnando ad ogni zona una lettera Xi, un percorso e una parola scritta con queste lettere. Se i ponti sonon, le parole che passano da n ponti sono composte da n + 1 caratteri.

D’altra parte ogni lettera di una parola identifica uno e due ponti che partono da quella zona (unosolo se e la lettera iniziale o finale della parola) e quindi se dalla zona Xi escono k(Xi) ponti la lettera Xdeve comparire almeno k(Xi)/2 volte nella parola che rappresenta il percorso passante per tutti i ponti.

Poiche il numero di volte n(Xi) in cui compare una lettera e un numero naturale, si ha n(Xi) ≥[k(Xi)+1

2

], dove [·] indica la parte intera. Inoltre il numero totale di ponti uscenti dalle singole zone e 2n

(ogni ponte esce da due zone).Pertanto si ha

2n =∑i

k(Xi)

n + 1 =∑i

n(Xi) ≥∑i

[k(Xi) + 1

2

]e al massimo 2 dei k(Xi) possono essere dispari. �

16 A. SARACCO

• esiste un percorso aperto (cioe con zona finale e iniziale diverse) che passi su tuttii ponti una e una sola volta se e solo se esattamente due zone hanno un numerodispari di ponti.

5. Fonti delle figure

Le figure 1, 2, 4, 5, 6, 9 e 11 sono tratte da [1].La figura 7 e tratta da [1], con i dialoghi rimossi.La figura 8 e il disegno in bianco e nero realizzato da Marco Mazzarello e comparso in [4], pag. 141.Tutte le figure sopra citate sono© Disney, e qui riprodotte per gentile concessione della Redazione di

Topolino.La figura 12 e tratta da [7]: commons.wikimedia.org/w/index.php?curid=520396, CC BY-SA 3.0.

Riferimenti bibliografici

[1] Francesco Artibani, Marco Mazzarello, Alberto Saracco, Paperino e i ponti di Quackenberg, Topolino3232 (2017), 105–134.

[2] Fabio Bettani, La scienza su “Topolino” nel decennio 2001–2010, tesi di master in comunicazione del-la scienza, SISSA, 2012. https://mcs.sissa.it/sites/default/files/allegati/bettani.pdf

[3] Sandro Camparrini (a cura di), Stefano Pisani (biografia), Eulero. Dai logaritmi alla meccanicarazionale, Grandangolo Scienza 24, Corriere della Sera (2017), 168 pp.

[4] Barbara Garufi (interviste a Francesco Artibani e Alberto Saracco), Gettiamo un ponte... sullatopologia, Topolino 3232 (2017), 136–141.

[5] B. Hopkins e R. Wilson, The truth about Konigsberg, in Leonhard Euler: Life, Work and Legacy, acura di R. Bradley e E. Sandifer, Elsevier, Amsterdam (2007).

[6] M. Trombetta, Calcolo combinatorio. Teoria e problemi, U Math 1, scienza express (2018), 158 pp.[7] Wikipedia, Problema dei ponti di Konigsberg.

Alberto Saracco, Dipartimento di Scienze Matematiche, Fisiche e Informatiche, Uni-versita di Parma, Parco Area delle Scienze 53/A, I-43124 Parma, Italy

E-mail address: alberto.saracco@unipr.it