Il fiore di Eulero – lo avete risolto?
Nell’ultimo post vi avevo sottoposto alcune sfide. Pubblichiamo qui le risposte.
1. Un fiore a tre petali
Provate a disegnare questo fiore, partendo dal punto A, con un solo tratto di penna, senza mai sollevarla dal foglio e senza ripassare su una linea già tracciata.
Domande
- OK, ma come si fa per calcolare tutte le possibilità?
- In quanti modi diversi si può rispondere alla domanda 1?
Ci sono esattamente 384 modi diversi per farlo.
Dipende dall’ordine in cui tracciate le foglie e i petali e se scegliete il senso orario o quello antiorario.
Procedimento 1, ingenuo
Questa è la mia soluzione elementare, diciamo naif, ingenua.
—
Enumerare le possibilità.
Parti da A e arriva all’incrocio B delle foglie.
1
Disegna una delle 2 foglie in uno dei 2 versi (orario-antiorario):
2×2
Disegna la foglia rimanente, in uno dei due versi:
1×2
Prosegui arrivando alla base C del fiore.
1
Disegna uno dei 3 petali in uno dei 2 versi:
3×2
Disegna uno dei 2 petali rimanenti in uno dei 2 versi:
2×2
Disegna l’ultimo petalo in in uno dei 2 versi:
1×2
Totale delle possibilità: 1×((2×2)×(1×2))×1×((3×2)×(2×2)×(1×2)) = 384
Procedimento 2, calcolo combinatorio di base
Questa è una soluzione combinatoria più matura.
- Modi di ordinare le foglie (permutazioni): 2!
- Modi di ordinare i petali (permutazioni): 3!
- Scelta del senso (orario-antiorario) per 5 volte: 25.
- Totale: 2!⋅3!⋅25 = 2⋅3⋅2⋅32 = 384
Procedimento 3, avanzato
Non consideriamo i petali e le foglie ma le strade che escono da ciascun nodo.
Ci mettiamo cioè in un atteggiamento locale piuttosto che globale. Immaginiamo di essere una formica che arriva in un nodo, vede solo le uscite disponibili e decide cosa fare.
Partiamo da A e arriviamo al primo incrocio, B.
Ci sono 5 uscite possibili ma non possiamo proseguire dritti finché non abbiamo percorso le due foglie, quindi abbiamo solo 4 strade da scegliere.
4
Conclusa la prima foglia (loop), ci ritroviamo al punto B e possiamo scegliere fra altre 2 strade.
2
Proseguiamo fino al secondo incrocio C. Qui abbiamo 6 strade tra cui scegliere.
6
Percorso il primo petalo (loop) ci rimane una scelta tra 4 strade
4
Percorso il secondo loop ci rimane una scelta tra 2 strade.
2
Totale: (4⋅2)⋅(6⋅4⋅2) = 4!!⋅6!! = 384
—
Semifattoriale.
Le scritture del tipo n!! (con n numero naturale), indicano il semifattoriale di un numero.
—
Il semifattoriale di un numero naturale n è il prodotto di tutti i numeri naturali fino a n che hanno la stessa parità di n.
Si scrive così: n!!
Esempi.
- 7!! = 7⋅5⋅3⋅1 = 105
- 8!! = 8⋅6⋅4⋅2 = 384
2. Cammino versus ciclo euleriano
Provate a disegnare la figura 1, partendo dal punto A, con un solo tratto di penna, senza mai sollevarla dal foglio e senza ripassare su una linea già tracciata.
Stesso esercizio per la figura 2, partendo dal punto B e ritornando a B.
Domanda
1. In quanti modi diversi si può tracciare ciascuno dei due disegni?
Per risolvere (velocemente) i problemi, ricaviamo una formula generale dal procedimento 3 dell’esercizio precedente.
—
Se abbiamo uno stelo con f fiori di p petali ciascuno, possiamo tracciarlo in n modi possibili, con:
n = ((2p)!!)f
—
Figura 1.
f = 3; p = 4;
n = (8!!)3 = 3843 = 56.623.104
Figura 2.
Nella figura 2 si parte da B e si ritorna al punto di partenza. Questo si chiama circuito euleriano.
Il numero di modi di disegnarlo è il doppio della figura 1 perché quando partiamo B abbiamo 2 scelte di direzione.
n = 2⋅(8!!)3 = 3843 = 113.246.208
Ringraziamento. Ringrazio il professore Riccardo Moschetti per avermi suggerito la soluzione col fattoriale doppio, in una bella narrazione!!
—
Pace e bene a tutti.
GfBo
Foto cover: Prokuronov Andrey / Shutterstock
Ilustrazioni: Gianfranco Bo
L’articolo è pubblicato anche su BASE Cinque.
Commenti