[HOME - BASE Cinque - Appunti di Matematica ricreativa]
Cari amici, in questo appunto vi propongo alcuni classici puzzles che chiedono di tracciare un disegno con un unico tratto di penna e senza ripassare su una linea già tracciata.
Un teorema di Eulero, facile da capire, ci aiuta a rispondere a queste domande e a risolvere questi puzzles.
Sapreste disegnare la figura qui sotto senza mai staccare la penna dal foglio e percorrendo ogni segmento una sola volta?
E' possibile tracciare la figura qui sotto con un solo tratto di penna percorrendo tutti i segmenti, ma ciascuno una sola volta?
Una figura di questo tipo, formata da punti (A, B, C, D, E, F) e da linee che li congiungono, si chiama grafo.
Per esempio l'ordine del nodo E è 4 mentre l'ordine del nodo D è 3.
Quando si dice "nodo pari" o "nodo dispari" si intende rispettivamente "nodo di ordine pari" o "nodo di ordine dispari".
---
Un cammino Euleriano è un percorso su un grafo che attraversa tutti gli archi esattamente una volta.
---
Tracciare un disegno con un solo tratto di penna equivale a fare un cammino Euleriano in un grafo.
Leonard Euler e Carl Hierholzer hanno dimostrato che è possibile trovare un cammino Euleriano in un grafo alle seguenti condizioni:
1) I grafi che hanno tutti i nodi pari si possono tracciare con un tratto continuo partendo da un nodo qualunque e tornando al nodo di partenza (ciclo Euleriano).
2) I grafi che hanno esattamente 2 nodi dispari (e tutti gli altri pari) si può tracciare con un tratto continuo partendo da uno di essi e arrivando all'altro (cammino Euleriano).
3) I grafi che hanno più di 2 nodi dispari non hanno un cammino Euleriano.
La figura a forma di casetta si può disegnare partendo dal punto C oppure dal punto D.
Ci sono molte soluzioni possibili (quante?), qui ne riporto due.
E' permesso incrociare le linee ma la soluzione in rosso è un esempio senza incroci.
Attenzione. Ho sdoppiato alcuni punti per facilitare la lettura della costruzione. I punti di partenza/arrivo sono segnati con un bollino.
Il rettangolo con le diagonali, invece ha 4 nodi dispari perciò non si può tracciare con un unico tratto di penna senza ripassare su una linea già tracciata.
Provate a disegnare le seguenti figure senza mai staccare la penna dal foglio e senza ripassare su una linea gi tracciata. E' possibile passare più volte sugli incroci.
Si vogliono colorare gli spigoli di un ottaedro con un pennarello rosso senza mai staccare la punta e senza ripassare sul colore già dato.
E' possibile scrivere il numero 100 su un foglio come si vede qui sotto senza mai staccare la punta della penna dal foglio?
Ecco alcuni altri esercizi. Quali sono possibili e quali impossibili?
Siamo
a Konisberg, nel 1759.
Il fiume che attraversa la città si divide
in due rami formando un'isola in corrispondenza della biforcazione.
Il territorio è diviso in 4 aree come si vede nella figura qui sotto:
l'isola A, le due sponde B, C e la parte interna alla biforcazione D.
Le 4 aree sono collegate da 7 ponti:
A-C sono collegate dai ponti
c, d;
A-B sono collegate dai ponti a, b;
D-A sono
collegate dal ponte e;
D-C sono collegate dal ponte g;
D-F
sono collegate dal ponte f;
|
|
E' possibile fare una passeggiata attraversando esattamente una sola volta tutti i ponti?
Ringrazio
Alberto Graziani per aver proposto questo esercizio.
Non
so se conoscete questa figura e il quesito che la accompagna, cioè quello
di unire tutti i segmenti con un'unica linea senza mai staccare la penna
dal foglio e passando una volta sola da ogni segmento.
1. Uno facile: la casetta
Altre soluzioni.
Ringrazio Jacopo Penazzi per le seguenti
osservazioni e per la soluzione più rigorosa.
Il
problema, a mio avviso, sta nel fatto che il quesito richiede di non
percorrere uno stesso segmento più volte, il che, sempre a mio avviso,
equivale a richiedere inoltre, che nessun segmento si intersechi con altri
segmenti.
Mi scuso per la pignoleria, dovuta probabilmente ad una differente
interpretazione del testo, ma io proporrei la seguente soluzione,
ugualmente valida e priva di tale difetto (sempre riferita alla figura
sopra riportata):
- partenza dal vertice C
- passo1: C-B
- passo2: B-F
- passo3: F-C
- passo4: C-D
-
passo5: D-F
- passo6: F-E
- passo7: E-B
- passo8:
B-A
- passo9: A-E
- passo10: E-D
In questo modo
sono rispettati i due vincoli posti dal testo e inoltre non esiste alcun
segmento che ne intersechi altri.
2. Uno impossibile: il rettangolo
Come dice il titolo stesso, il problema non si può risolvere.
3. Variazioni sul tema
La prima ha tutti i nodi pari, ciascuno dei quali può essere il punto di partenza di un ciclo Euleriano.
La seconda figura ha due nodi dispari perciò si possono trovare diversi cammini euleriani.
La terza ha 4 nodi dispari, quindi non ha soluzioni.
4. Uno a tre dimensioni: dipingere gli spigoli di un ottaedro
(inviato al Forum da Peppe)
Possiamo immaginare l'ottaedro come un grafo nello spazio: i vertici sono i nodi, gli spigoli sono gli archi.
Ecco quindi una possibile soluzione.
Tuttavia è più interessante riportare la rete di collegamenti sul piano con un grafo equivalente.
Ciascun nodo ha ordine pari, perciò esiste un percorso chiuso che passa per tutti gli archi.
Nell'ordine il percorso passa per questi vertici: A, C, B, A, E, F, D, E, C, F, B, D, A.
5. Uno col trucco: scrivere 100
Si piega il foglio e si scrive 100 come illustrato nella figura qui sotto.
Si rimette a posto la piegatura ed ecco il risultato.
6. Altri esercizi
I tre esercizi qui sopra sono equivalenti e impossibili poiché hanno 4 nodi dispari.
Le figure qui sopra sono equivalenti e, avendo solo nodi pari, possono essere tracciate partendo da uno qualunque dei nodi.
Questo esercizio è impossibile.
7. Un grande classico: i ponti di Konisberg
Il
problema dei ponti di Konisberg si può ricondurre alla seguente figura.
E' possibile tracciarla con un solo tratto di penna senza mai staccare la
penna dal foglio e percorrendo tutte le linee esattamente una volta?
Non è possibile!
Ringrazio Giorgio Scioldo per le seguenti
considerazioni.
A
proposito dei ponti di Konigsberg mi sono appena trovato a doverlo
spiegare a mio figlio di 9 anni, forse può essere interessante come
spiegazione "per bambini": ciascuno dei tre punti B, C ed E è collegato al
resto da tre ponti, per cui in ognuno di essi è possibile soltanto
uscire-entrare-uscire oppure entrare-uscire-entrare; quindi ognuno di essi
deve essere per forza un punto di inizio o di fine del percorso. Poiché
una linea può avere soltanto un punto di inizio ed un punto di fine, non
possono essercene tre, e quindi il problema non è risolvibile!
8. Uno enigmatico
La figura contiene 8 nodi dispari (di ordine 3), perciò non si può tracciare SUL PIANO con un unico tratto di penna.
Forse, se il disegno fosse la superficie di un nastro di Moebius o di un Toro...
---
Pace e bene a tutti.
GfBo
Data creazione: maggio 2001
Ultimo aggiornamento: luglio 2021
html5
Sito Web realizzato da Gianfranco Bo
