Skip to content

Girotondo di cerchi 3 – Semplificare

20 gennaio 2012

Lorella si asciuga le mani sullo strofinaccio della cucina. Ha finito di lavare il frullino per montare il latte da mettere sul caffè.

“Stavo pensando al problema dei percorsi chiusi in quella figura con i tre cerchi“, mi dice.

“Uhm?”, l’incoraggio eloquentemente a continuare.

“Tu hai contato quanti sono? A mano si può fare, ma è abbastanza lungo”, fa lei.

“Sì, ci ho messo un po’”, confesso, “e non ho trovato un modo per automatizzare il calcolo.”

“Ecco, è proprio questo il punto. Stavo pensando che basterebbe togliere il cerchio esterno per semplificare di molto i conti.

Per iniziare, così facendo, si vede che un girotondo di tre cerchi può essere deformato in un triangolo inscritto in un cerchio; quattro cerchi si deformano in un quadrato inscritto in un cerchio e così via. Questo però non è essenziale.

Mi sembra che così sia facile calcolare il numero totale di percorsi diversi che partono dai vari nodi, anche aumentando il numero di cerchi o, che è lo stesso, il numero di vertici del poligono inscritto.

Ad un certo punto, il numero dei percorsi si scompone per la prima volta usando quattro fattori primi diversi. E si tratterebbe allora di vedere quando succede. Che te ne pare?”

“Semplicissimo!”, canzono. Però sotto sotto sono d’accordo.

Girotondo di cerchi 3 – Semplificare


Un grafo è composto da n nodi, con due archi tra ogni coppia (i, i+1), i = 1, \ldots, n-1 e due archi tra (n, 1). Qual è il minimo n per il quale il numero di circuiti euleriani si scompone in almeno 4 fattori primi distinti?

Annunci
No comments yet

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: