16. Passeggiate elettriche (staffetta)

[Anér]

Abbiamo un grafo connesso su $ n $ vertici come al solito. Su ogni vertice è posizionata una lampadina che si può accendere in $ k\geq 2 $ colori diversi ed è provvista di un interruttore: premendo l'interruttore si cambia ciclicamente il colore della lampadina. Un elettricista si trova in un vertice $ P $ del grafo e deve camminare lungo gli archi per cambiare lo stato delle lampadine secondo le richieste del proprietario del grafo (cosa tocca fare oggi per sbarcare il lunario!), e ogni volta che arriva in un vertice deve premere una e una sola volta l'interruttore. La situazione iniziale delle lampadine è quella lasciata dal figlio pestifero del proprietario del grafo che ha potuto scegliere a piacere lo stato di ogni lampadina. Trovarsi in $ P $ al'inizio non significa premere all'inizio l'interruttore in $ P $ (ma questi sono dettagli). Alla fine del lavoro l'elettricista deve tornare in $ P $, ovvero l'ultimo interruttore premuto deve essere quello in $ P $. Determinare per quali grafi è possibile portare sempre a termine il lavoro.

[Anér]

Visto che nessuno ha ancora risposto piazzo una spiegazione del testo e un aiutino nascosto.
Dato $ k\geq 2 $ bisogna determinare tutti i grafi G connessi con questa proprietà: "Se poniamo in ogni vertice di G una lampadina con $ k $ colori, comunque si scelgano un vertice $ P $, una colorazione iniziale del grafo e una finale, esiste un percorso che parte da $ P $ e finisce in $ P $, passando eventualmente più volte per lo stesso vertice, e tale da trasformare la colorazione iniziale in quella finale, con la regola che ogni volta che si arriva in un vertice la lampadina cambia colore con il colore successivo".
Per comodità le lampadine sono fatte tutte allo stesso modo, ovvero assumono ciclicamente i colori $ c_1,\cdots ,c_k $.
Ecco l'aiutino

Testo nascosto:

Mostrare che i grafi richiesti sono tutti e soli quelli connessi non bipartibili, cioè quelli per cui non è possibile dividere i vertici in 2 insiemi in modo che gli archi abbiano sempre un estremo in ognuno dei due insiemi, o in altri termini (grazie a un noto teorema sui grafi bipartibili) quelli connessi con almeno un ciclo dispari.

Suvvia, ravviviamo questa staffetta di combinatoria!

[sasha™]

Scrivo un po' di ovvietà per ravvivare il topic.

Che con i bipartiti non si possa, purché k sia pari, è piuttosto banale. Sia $q_i$ il numero di volte che va premuta la lampadina nel vertice $P_i$ per farla arrivare nella corretta colorazione. Se il cammino dell'elettricista deve tornare in $P$, in un grafo bipartito ha necessariamente lunghezza pari. Pertanto, modificherà il valore di $\sum q_i$ di un numero pari. Se $\sum q_i$ è dispari, e $k$ è pari (la somma va comunque considerata modulo k: premere una lampadina $q_i$ volte o $q_i + k$ volte è la stessa cosa), banalmente non esistono percorsi possibili.

Altra ovvietà: le "foglie" si possono eliminare facilmente. Basta andare avanti-indietro fra il penultimo e l'ultimo vertice finché questo non è del colore "giusto". L'altro sarà cambiato, ma si passa da colorazione qualsiasi a colorazione qualsiasi, quindi cambia poco. Nel caso in cui $P$ sia estremo di una foglia, basta portarlo nel colore immediatamente precedente quello giusto, così come il resto del "ramo", in modo che, ripercorrendolo (per chiudere il percorso), tutte le lampadine assumano il colore giusto. Un discorso simile si può fare con i cicli "semplici", possono essere eliminati allo stesso modo, credo.

Mah, probabilmente non ho detto nulla di utile, ma almeno tiro su il topic.

[Anér]

Oh, finalmente qualcuno che risponde! L'idea della somma dei numeri di cambiamenti di ogni vertice può essere molto migliorata, magari spezzando tale somma in due somme, nel caso in cui il grafo sia bipartito. L'idea di andare avanti e indietro per aggiustare una foglia può essere generalizzata, ed è utile a descrivere una strategia per i grafi non bipartiti (in fondo avanti e indietro si può fare su ogni arco). Dai, non è così difficile questo problema!

[sasha™]

L'idea di andare avanti è indietro l'ho sviluppata pensando a quello, poi mi sono accorto che non ne traevo quasi nulla e l'ho riformulata così...

Spezzare la somma nei grafi bipartiti? Giusto, le due somme devono essere necessariamente congrue modulo $k$ (no?), altrimenti, dato che il numero di cambiamenti che si fanno è lo stesso, tale percorso non esiste. E questo ci dà il "se". Per il "solo se" ora ci penso...

Ok, forse ci sono. Elimino tutti i "rami" con quel giochino (se un ramo contiene $P$, ho già spiegato come fare), e faccio la stessa cosa sui sottocicli (in modo assolutamente identico, avanti-indietro sui vari archi in modo da aggiustare tutti i vertici tranne uno; se un sottociclo contiene $P$, stessa cosa). Così mi posso ricondurre ad avere un unico ciclo dispari, perché quando devo eliminare un ciclo dispari, che c'è per ipotesi, se ha in comune con il ciclo "finale" uno o più archi, posso scegliere se lasciare il cammino pari o quello dispari (e quindi decidere se il ciclo "finale" sarà pari o dispari), se invece ha in comune un vertice, posso tenere quello e cancellare il resto. Resta da chiudere questo caso, che ad occhio è semplice. Ci penso ancora un po'.

[Anér]

Cerca di scrivere tutto più formalmente: ad esempio non è chiaro nella prima parte cosa è congruo a cosa, e nella seconda non capisco cosa sia un sottociclo, né ho capito in che ordine sistemi le lampade di un ciclo , se le sistemi tutte (quelle di un ramo dalla foglia in giù o nell'altro modo se contiene P).

[sasha™]

Definito sempre $q_i$ come il numero di shift da fare (modulo $k$), se il grafo è bipartito, divido i vertici in due sottoinsiemi nel modo "ovvio" (cioè in modo che partendo da un vertice di A si arrivi sempre ad un vertice di B e viceversa). Il percorso è chiuso, quindi il numero di volte che vado da A a B è uguale al numero di volte che vado da B ad A. Quindi il numero di shift fatti nei due sottoinsiemi è lo stesso. Per cui, se la somma degli shift da fare su tutti i vertici di A, e quella su tutti i vertici di B, sono distinte (modulo $k$), non potranno mai arrivare entrambe a zero contemporaneamente. In questo caso, dunque, non sempre è possibile completare il lavoro.

I rami vanno sistemati tutti partendo dall'ultima foglia a scendere, incluso quello che contiene $P$, solo che da $P$ in poi non vanno messi sul colore giusto, ma su quello precedente, in modo che, tornando su $P$, diventino del colore giusto. Continuo domattina, ora chiudo...

[sasha™]

Allora. Fisso un ciclo di lunghezza dispari che parte da $P$ (tale che non si passi mai per lo stesso arco e/o vertice due volte), o, se $P$ è su un ramo, dal vertice più vicino a $P$ sul quale posso farlo. Dimostro che posso farlo, e che è possibile eliminare tutto il resto.

Posso farlo perché il grafo è connesso è c'è almeno un ciclo dispari: se $P$ ne fa parte, elimino tutto il resto, altrimenti, lascio quello insieme al percorso più breve (ma non necessariamente, basta un percorso a caso) fra $P$ e il ciclo.

Posso eliminare tutto il resto. Per i rami faccio quello che ho scritto prima. Per i cicli, se sono connessi al ciclo fissato solo tramite un vertice, parto da quello, e facendo avanti-indietro fra il successivo e quello dopo ancora, porto il primo dei due sul colore giusto. Itero il procedimento fino a tornare nel vertice che appartiene al ciclo fissato. Se sono connessi tramite due vertici (in pratica, se ho due cammini distinti fra $A$ e $B$, entrambi appartenenti al ciclo fissato) faccio la stessa cosa partendo da $A$ e finendo in $B$. Se una qualsiasi componente che voglio eliminare contiene $P$, semplicemente sul cammino che collega $P$ al ciclo fissato, anziché portarli sul colore giusto li porto sul precedente (tornando indietro su P si aggiusteranno da soli).

In questo modo mi riduco ad avere un unico ciclo dispari. Da qui è problematico, perché posso portare tutte le lampadine sul colore giusto tranne una (solito metodo per eliminare i cicli), e quella non saprei correggerla.

[Anér]

Nella parte con le somme rileggi bene l'ipotesi e definisci bene l'invariante.
Nella parte con la strategia non ho capito bene cosa fai se hai cicli che si innestano su altri cicli che sono collegati con un ramo al ciclo dispari, i quali rami poi toccano, ma solo in un vertice, altri cicli collegati a quello dispari e a un vertice del percorso che va da P al ciclo dispari... insomma il grafo potrebbe essere molto intricato, e ti conviene cercare un modo di semplificarlo, magari con un paio di forbici.

[sasha™]

Niente forbici, basta fissare un qualsiasi cammino da $P$ a $P$ che passi per tutti i vertici, eventualmente più volte, e ogni volta che vado da $P_i$ a $P_{i+1}$, faccio avanti-indietro tante volte quante ne servono per portare $P_i$ sul colore giusto. In questo modo posso sistemare tutti i vertici tranne $P$. Adesso sono in $P$, fisso un cammino, che passi al più una volta per ogni vertice, da $P$ a un ciclo dispari, e porto tutti i vertici di questo cammino sul colore precedente quello giusto, a scapito di un vertice del ciclo dispari che ho scelto, con il solito giochino avanti-indietro. A questo punto sistemo il ciclo (non so ancora come, in realtà), torno indietro e ho vinto... In ogni caso dovrebbe bastare per ricondursi sempre ad un caso "semplice ciclo dispari", indipendentemente da quanto è intricato il grafo, no?

Sulla parte sulle somme cosa c'è che non è chiaro?

[Anér]

No, scusa, non avevo capito bene io la parte delle somme; sì, ti manca solo il caso del ciclo dispari, e prova a sfruttare l'invariante del caso pari e stavolta davvero un paio di forbici.

[Veluca]

Dopo (poche) fatiche son riuscito a trovare una soluzione con l'algebra lineare per il caso del ciclo dispari, per la gioia di fph XD

Numero i vertici del grafo partendo da P. (o quantomeno da quello a cui devo arrivare)
Siano $(q_1,q_2,\dots,q_n)$ le mosse che devo fare rispettivamente al primo (cioè P), al secondo, ... all'ennesimo vertice per arrivare alla configurazione "di vittoria".
Riesco facilmente a fare queste mosse (n in tutto), che mi riportano in P:
$(1,1,1,\dots,1,1)$
$(1,2,2,\dots,2,1)$
$(1,2,2,\dots,1,0)$
$\dots$
$(1,1,0,\dots,0,0)$
Siano ora $(a_1,a_2,\dots,a_n)$ il numero di volte che eseguo ciascuna delle n mosse.
Se ho che

$\left\{\begin{array}{cccccccccccc}
a_1&+&a_2&+&a_3&+&\dots&+&a_{n-1}&+&a_n&=&b_1\\
a_1&+&2a_2&+&2a_3&+&\dots&+&2a_{n-1}&+&a_n&=&b_2\\
a_1&+&2a_2&+&2a_3&+&\dots&+&a_{n-1}&&&=&b_3\\
\vdots&&\vdots&&\vdots&&\vdots&&\vdots&&\vdots&&\vdots\\
a_1&+&a_2&&&&&&&&&=&b_n
\end{array}\right.$

per $(a_1,a_2,\dots,a_n)$ interi relativi, allora esiste una serie di mosse che mi permette di sistemare ogni lampadina e tornare in P. (se a_i<0 non mi importa, eseguo quella mossa k-a_i volte, dove k è il numero di colori)
Se la matrice dei coefficienti ha il determinante di valore assoluto 1, allora per (il teorema di Cramer?) tutte le soluzioni sono intere, perchè si ottengono dal determinante di una matrice a coefficienti interi fratto $\pm1$.

$\underbrace{\left|\left|\begin{array}{cccccc}
1&1&1&\dots&1&1\\
1&2&2&\dots&2&1\\
1&2&2&\dots&1&0\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\
1&1&0&\dots&0&0
\end{array}\right|\right|}_{n}=\underbrace{\left|\left|\begin{array}{cccccc}
1&1&1&\dots&1&1\\
0&1&1&\dots&1&0\\
0&1&1&\dots&0&-1\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\
0&0&-1&\dots&-1&-1
\end{array}\right|\right|}_{n}=\underbrace{\left|\left|\begin{array}{cccccc}
1&1&1&\dots&1&0\\
1&1&1&\dots&0&-1\\
1&1&1&\dots&-1&-1\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\
0&-1&-1&\dots&-1&-1
\end{array}\right|\right|}_{n-1}$

dove ho usato prima l'eliminazione di Gauss, e poi la formula ricorsiva per il calcolo del determinante.
Ora uso di nuovo l'eliminazione di Gauss, sostituendo $r_{n-i}$ con $r_{n-i-1}-r_{n-i}$, per $i=1,2,\dots,n-2$, e in seguito sostituisco la prima riga con $r_1-\displaystyle\sum_{i=1}^{\frac{n-1}2}r_{2i}$ (qui uso l'ipotesi che n sia dispari).

$\left|\left|\begin{array}{cccccc}
1&1&1&\dots&1&0\\
1&1&1&\dots&0&-1\\
1&1&1&\dots&-1&-1\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\
0&-1&-1&\dots&-1&-1
\end{array}\right|\right|=\left|\left|\begin{array}{cccccc}
1&1&1&\dots&1&0\\
0&0&0&\dots&1&1\\
0&0&0&\dots&1&0\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\
1&1&0&\dots&0&0
\end{array}\right|\right|=\left|\left|\begin{array}{cccccc}
0&0&0&\dots&0&-1\\
0&0&0&\dots&1&1\\
0&0&0&\dots&1&0\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\
1&1&0&\dots&0&0
\end{array}\right|\right|$

Ma questa è una matrice triangolare, quindi il suo determinante è uguale in valore assoluto al prodotto di tutti i numeri sulla diagonale, quindi è 1 in valore assoluto.

[Anér]

Mi pare che funzioni tutto. Alternativamente si poteva fare così: chiamo Q il vertice del ciclo dispari da cui devo partire e in cui devo tornare. Il ciclo dispari non è bipartibile, ma se chiamo R uno dei vertici adiacenti a Q e taglio l'arco QR ho che il ciclo diventa una spezzata di estremi Q e R, ossia un grafo bipartibile in cui Q e R appartengono alla stessa fazione (perché il ciclo era dispari), e chiamo questa fazione A, mentre B sarà l'altra. Se però ripristino l'arco QR posso saltare quante volte voglio avanti e indietro da Q a R in modo da diminuire di 1 modulo k il numero di cambiamenti necessari per la fazione A, mentre la B resta invariata; posso quindi fare in modo che le due somme di cambiamenti necessari delle due fazioni siano uguali modulo k. Alla fine mi ritrovo in uno dei vertici Q e R (non so quale, ma non importa, l'importante è che alla fine mi trovo in A e devo completare l'opera arrivando in Q che si trova sempre in A) con le somme aggiustate, e posso sopprimere l'arco QR e aggiustare tutti i vertici a partire da R e finendo in Q, che per conservare l'invariante si aggiusterà da solo.
Visto che avete risolto insieme il problema scegliete voi chi proporrà il prossimo, mettendovi d'accordo tra di voi.

[sasha™]

Ci eravamo già messi d'accordo, e tocca a me... Ora ci penso, poi lo posto. Sono tentato di proporre quello delle mele del WC11... Ma è troppo noto.

[fph]

Dopo (poche) fatiche son riuscito a trovare una soluzione con l'algebra lineare per il caso del ciclo dispari, per la gioia di fph XD

Gioia. Solo un paio di consigli/osservazioni/commenti:

1) devi anche dimostrare che la soluzione ha come elementi interi non negativi, perché non si può fare una mossa "-1 volte". In alternativa, puoi anche trovare una sequenza di mosse che equivale a fare una certa mossa base "-1 volte" (questo è più facile, ed è un'idea che si ricicla in molti problemi di questo tipo). Nota che se non fai questo, non usi mai l'ipotesi che i colori delle lampadine si ripetono ogni $k$. EDIT: ok, l'hai fatto, mi era sfuggito, sorry.
2) trucco del mestiere: quando una matrice è "quasi triangolare", sfrutta questo fatto e cerca di trasformarla al triangolo più simile, così fai meno fatica. In questo caso, il triangolo più simile è la metà in alto a sx della matrice; ti basta ammazzare gli elementi $A_{2,n}, A_{3,n-1},A_{4,n-2},... A_{n,2}$. Questo lo fai ricorsivamente: partendo dalla seconda riga, ammazzi $A_{2,n}$ con $r_2\leftarrow r_2-r_1$, poi $A_{3,n-1}$ con $r_3\leftarrow r_3-r_2$... Questo sembra più semplice di quello che fai tu, che "riempie" le righe e poi le risvuota, e usa in modo molto naturale l'ipotesi $n$ dispari.
3) di solito i determinanti si indicano con barre singole.
4) le matrici che hai scritto si fanno con meno fatica con

Codice: Seleziona tutto

\begin{Vmatrix}a & b\\ c & d\end{Vmatrix}

. Rimpiazza Vmatrix con vmatrix, pmatrix, bmatrix, matrix per avere come delimitatori rispettivamente barre singole, parentesi tonde, quadre, e nulla.
5) tu hai saggiamente evitato questo errore, ma lo dico a beneficio degli altri (pochi) lettori di questo post: potrebbe venirvi in mente di tentare l'algebra lineare negli interi modulo $k$ per fare i conti. Occhio però: solo per $k$ primo funzionano tanti bei teoremi tipo "un sistema lineare ha soluzione unica sse il determinante è nonzero".