Attraversamento semplice

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Attraversamento semplice

Messaggio da Gerald Lambeau »

Determinare tutti gli interi positivi $n$ tali che è possibile attraversare un grafo completo di $n$ vertici passando per ogni arco una e una sola volta e "senza staccare la penna dal foglio" (cioè per andare da un vertice a un altro bisogna passare per un percorso di archi non già attraversati che li connettono, altrimenti sarebbe banale).
"If only I could be so grossly incandescent!"
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Attraversamento semplice

Messaggio da Talete »

Testo nascosto:
$n$ dispari oppure tale che $76n=152$.
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
Ilgatto
Messaggi: 38
Iscritto il: 24 ott 2017, 16:36

Re: Attraversamento semplice

Messaggio da Ilgatto »

Inizio notando che il caso $n=2$ è banale e che il caso $n=1$ è alquanto assurdo.
Dimostro che se $n$ è pari e maggiore di $2$, allora non è possibile fare un "attraversamento" come richiesto:
Ogni vertice è collegato a ogni altro perchè il grafo è completo, quindi ogni vertice è collegato a $n-1$ altri vertici. Nel caso in cui $n$ sia pari, $n-1$ è dispari, quindi ogni vertice è collegato a un numero dispari di altri vertici. Però se collego tutti i vertici nel modo richiesto, dovrò entrare ed uscire ogni volta da $n-2$ vertici. Mi spiego meglio, inizio da un vertice, vado in un altro e poi passo a un altro ancora, così facendo ogni volta che passo da un vertice ripasso $2$ archi collegati a quel vertice, tranne quando l'attraversamento inizia o termina nel punto considerato. Questo significa che solo $2$ vertici possono essere collegati a un numero dispari di vertici (sommando sempre $2$ non posso ottenere un numero dispari), quindi il caso $n=2$ è valido, mentre non lo sono tutti i casi con $n$ pari e maggiore di $2$.
Iniziamo a dimostrare che per ogni altro $n$ l'attraversamento è possibile considerando $n$ primo:
parto da un vertice chiamato $A$ e devo finire sempre in quello, perchè il numero di archi collegati ad $A$ è pari e, per quanto detto prima, l'inizio sarebbe collegato a un numero dispari di vertici se non fosse anche la fine. Da $A$, passo a un vertice chiamato $B$, poi a $C$ ecc. fino a tornare ad $A$ dopo essere passato da tutti i vertici. Poi da $A$ andiamo a $C$ e così via saltandone sempre $1$ e sempre nella stessa direzione. Poi vado avanti saltandone $2$, poi $3$ ecc. fino a quanto arrivo al punto $A$ e dovrei saltare $\frac{n-1}{2}$ vertici. Dimostro che così passo da ogni arco una e una sola volta:
Mi trovo in $A$ e devo saltare $k$ vertici un po' di volte per poi tornare in $A$, questo è possibile in quanto $k+1$ ed $n$ sono coprimi (eccetto il caso in cui $k=0$, che è banale) infatti se non lo fossero, dopo $\frac{n}{(k+1,n)}$ salti sarei tornato al punto $A$ senza essere passato da tutti i vertici. Essendo coprimi invece non basta compiere un giro, perchè il vertice $A$ viene saltato $k$ volte prima di essere raggiunto, infatti bisogna compiere $k$ giri per tornare al vertice iniziale perchè in questo modo si rende il prodotto tra il numero di giri fatti e il numero di vertici del grafo divisibile per $k+1$. È una cosa contorta, quindi la spiego meglio se assegno a ogni vertice un numero invece di una lettera (quindi il vertice $A$ diventa $0$, il vertice $B$ è $1$ ecc.) guardando modulo $n$ si può considerare ogni salto come un passaggio dal vertice $x$ a quello $x+k+1$; quindi essendo $k+1$ e $n$ coprimi, tornerò ad avere $0$ $\mod n$ solo dopo aver compiuto $n$ salti, cioè dopo essere passati una volta da ogni vertice e avendolo saltato $k$ volte (passo da ogni vertice perchè per pidgeonhole se non passassi da un vertice dovrei farlo due volte da un altro, ma ciò significherebbe che potrei tornare a un vertice compiendo meno di $n$ salti che è assurdo). Inoltre se saltassi più di $\frac{n-1}{2}$ ripasserei sopra degli archi che avevo già passato; questo perchè partendo da $A$ saltando $k$ vertici per poi tornare ad $A$ è equivalente a farlo saltando $n-k$ vertici in senso opposto. Come faccio ad essere sicuro che ho ripassato tutti gli archi? Se ce ne fosse uno non ripassato, esso collegherebbe comunque due vertici che hanno tra loro $k\le \frac{n-1}{2}$ vertici in uno dei due sensi, ma io ho già ripassato tutti gli archi che collegano due vertici che distano quel numero $k$ di vertici, dunque ho ripassato ogni arco.
Se $n$ non è primo, modifico leggermente la strategia:
Come prima parto da $A$ per poi ritornarci dopo essere passato da tutti i vertici ordinati con le lettere dell'alfabeto; mentre faccio questo giro, ne faccio anche altri. Nel senso che prima di passare da $A$ a $B$, faccio un giro saltando ogni volta $k$ vertici essendo $k$ tale che $k+1$ e $n$ non sono coprimi. Quindi ad esempio se $n=9$ parto da $A$, vado a $D$, poi a $G$ e torno ad "A" (in questo caso l'unico divisore di $n$ diverso da $1$ e $n$ è $3$ (anche $6$ non è coprimo, ma per quanto detto all'inizio è equivalente al caso $3$), quindi compio un giro con $k=2$). Dopo aver compiuto un giro come appena descritto, passo a $B$ e ripeto l'operazione (con il caso $n=9$ faccio un altro giro saltando $2$ vertici, andrò quindi in $E$ poi in $H$ e torno a $B$), poi a $C$ ecc. fino a tornare ad $A$.Non potrò ripetere da tutti i vertici tutti i giri, perchè avrò già ripassato diversi archi, ma è come se quei giri li avessi già fatti poichè li ho ripassati partendo però da un altro inizio (nel caso $n=9$ non posso fare un giro partendo da $C$ saltando $2$ vertici, perchè l'ho già fatto partendo da $A$).
Ora mi restano da fare gli archi che saltano un numero $k \le \frac{n-1}{2}$ di vertici in uno dei due sensi tale che $k+1$ è coprimo con $n$; questi si fanno tranquillamente come mostrato prima con $n$ primo, essendo sufficiente che $k+1$ e $n$ siano coprimi.
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Attraversamento semplice

Messaggio da Gerald Lambeau »

Ok, buona!
"If only I could be so grossly incandescent!"
savian
Messaggi: 27
Iscritto il: 20 nov 2017, 14:16

Re: Attraversamento semplice

Messaggio da savian »

Da dove mi consigliate di studiare per dare una dimostrazione come quella de ''il gatto''?
Ilgatto
Messaggi: 38
Iscritto il: 24 ott 2017, 16:36

Re: Attraversamento semplice

Messaggio da Ilgatto »

A dir la verità non è che ho studiato qualcosa, ho fatto l'esercizio come avevo già visto fare sul forum. In particolare ho messo i vertici in modo comodo, cioè su un poligono regolare. Ora inizio con i casi base, cioè con $n=1,2,3$. Vedo che per questi funziona. Escludo $n$ pari perchè quello che ho usato è una cosa nota e molto utile quando ci sono dei grafi. Poi per il resto vai un po' a occhio, io ho pensato a quella tecnica di attraversamento perchè mi sembrava facile da spiegare.
Insomma ti conviene guardare un po' di problemi sul forum, cercare di capire cosa ti chiedono di trovare e magari cercare teoremi anche su Wikipedia che è facile da usare e veloce. In questo caso la teoria si riduce a capire cosa chiede il problema e quella cosa per escludere gli $n$ pari che troverai usata spesso in questo tipo di esercizi. Quando hai fatto abbastanza esercizi da capire cosa fare per risolverli senza aver bisogno di aiuto, il problema si riduce a scrivere una soluzione completa e precisa.
Rispondi