Staffetta combinatoria.

[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]

Sempre da qui la soluzione del problema.

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.

(Nel caso del grafo non bipartito, n.d.r.) 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?

Numero i vertici del grafo (del ciclo, n.d.r.) 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.

[sasha™]

Link.

Ci sono, disposte circolarmente intorno ad un lago, 12 ceste contenenti un pesce ciascuna. Si può spostare un pesce da una cesta ad un altra, purché si saltino esattamente due pesci (non due ceste) mentre lo si sposta (ciò vuol dire che si può saltare un numero qualsiasi di ceste vuote). È consentito spostare un solo pesce alla volta e muoversi solo in senso orario. Determinare il tragitto più breve tale che, al termine di questo, ci siano sei ceste con due pesci e sei ceste vuote, spostando solo sei pesci.

[sasha™]

Soluzione, nello stesso topic.

Numero le ceste dalla 1 alla 12 in senso antiorario (risolvo il problema in senso antiorario e lo stesso vale per il senso orario)
1) si può fare in 25 mosse: 1-4, 5-8, 9-12, 3-6, 7-10, 11-2. (1-4 intendo che prendo il pesce nella cesta 1 e lo lascio nella 4)
2) Suppongo (wlog) che il primo pesce sia preso nella cesta 1 e lasciato nella cesta 4. Dopo un giro devo prendere o lasciare un pesce nella cesta 2 (altrimenti ci dovrò passare al giro dopo e fare almeno 25 passi). Se prendo un pesce salto la cesta 3 e ci dovrò tornare al terzo giro (>25 passi), se lascio un pesce nella cesto 2 allora il pesce proveniva dalla cesto 10, ha saltato la 11 e la 12 con un pesce e la 1 con zero pesci. Al secondo giro devo sistemare i pesci delle ceste 11 e 12 quindi atterro con un pesce nella 11 e prendo quello della 12 che salterà la cesta 1 (con 0 pesci) e la 2 (con due pesci) facendo più di 25 passi.

Questo ragionamento si generalizza facilmente con $4n$ ceste.
Spero che sia stato chiaro, senza un disegno è difficile....

e se le ceste fossero $4n+2$?

[jordan]

Da qui il problema 18:

Dato un punto O Anna pensa a un punto P che dista meno di 5 m da esso. Barbara può segnare sul piano $n$ punti. Dopo chiede ad Anna per ogni coppia di punti quale dei due sia più vicino a P. Barbara deve circoscrivere una zona di meno di 10 m$^2$ nel quale è presente il punto P. Qual'è il minimo valore di $n$ per cui è possibile ciò?

Disposizione punti: tre sulla circonferenza a formare il triangolo equilatero inscritto, uno nel centro della corconferenza; l'area massima dei pezzi che si vengono a formare è $ \frac{8}{3}\pi-2\sqrt{3}<5 $

[jordan]

Da qui il problema 19:

Marco e Sara giocano a testa o croce. Partono tutti e due con un punto. Ad ogni T, Marco guadagna un punto, ad ogni C, Sara raddoppia i suoi punti (perchè Marco è galantuomo e vuole lasciar vincere la fanciulla);
-trovare un metodo per calcolare al n-esimo tentativo la probabilità di vittoria di Marco
-verificare il metodo per n=100.

Bon, rispondiamo...
allora, si ha che

$C+T = n$ e si deve avere che $2^{C} < T$. Ma essendo $T = n-C$ si ha semplicemente che si deve avere che $2^C +C < n$ che è vera in generale per $C=\lfloor \log_{2}{n} \rfloor $ e in particolare per $n=100$ si ha che $C=6$.

La probabilità che in generale dopo $n$ tiri sia in vantaggio il galantuomo è pari a

$\sum_{b=0}^{\lfloor \log_{2}{n} \rfloor}\frac{\binom{n}{b}}{2^n}$ in quanto $2^n$ sono i casi possibili e $ \sum_{b=0}^{\lfloor \log_{2}{n} \rfloor +1}\binom{n}{b}$ sono i casi favorevoli, equivalenti al numero di modi in cui si può scrivere una parola binaria di $n$ numeri contenente al massimo $\lfloor \log_{2}{n} \rfloor +1$ numeri $1$

Aspetto conferme per il prossimo problema

[jordan]

Da qui il problema 20:

ad un tavolo circolare ci sono 60 posti e vi si siedono 30 mogli con i rispettivi 30 mariti. Mostrare che esistono almeno due signore che siedono alla stessa distanza dai rispettivi mariti.

Le possibili distanze sono {1,2,...,30}. Se per assurdo ogni coppia si fosse seduta a una distanza diversa allora ogni possibile distanza {1,2,...,30} risulterebbe esattamente una volta. Numerando i posti da 1 a 60 nello stesso verso, abbiamo 15 coppie con distanza dispari, e 15 coppie con distanza pari. Questo significa che il totale di posti pari occupati è pari a 15+2k, dove k è il numero di coppie con distanza pari che occupano entrambi i posti con numero pari. E' evidente che 15+2k=30 non ha soluzione negli interi. []

[jordan]

Da qui il testo del problema 21:

Siano A un insieme ordinato di $ n>1 $ elementi e $ B_1,\ldots, B_k \subseteq A $, con $ k<n $. Dimostrare che è sempre possibile dare una colorazione con due colori degli elementi di A tale che

• 1) ogni elemento di A o è colorato con uno dei due colori oppure è lasciato incolore.
  2) almeno un elemento di A è colorato.
  3) se esiste un elemento di un $ B_i $ colorato allora esiste almeno un altro elemento di $ B_i $ colorato con l'altro colore. Ossia o $ B_i $ è tutto incolorato oppure sono presenti entrambi i colori.

[Anér]

Sempre da qui

Pongo $ A=\{a_1,\cdots, a_n\} $. Ora ogni elemento appartiene ad alcuni dei $ B_i $ e ad altri no. Allora per ogni elemento definisco il vettore $ v_i=(c_{i,1},\cdots, c_{i,k}) $, ove $ c_{i,j} $ vale 1 se $ a_i\in B_j $ e 0 altrimenti. Questi $ v_i $ sono $ n $ vettori appartenenti a $ \mathbb{R}^k $, e dato che $ k<n $ questi vettori non possono essere linearmente indipendenti, ovvero esistono coefficienti reali $ \lambda _1, \cdots, \lambda _n $ tali che $ \lambda _1v_1+\cdots+\lambda_nv_n=0 $, e non tutti i $ \lambda_i $ sono nulli. A questo punto coloro di nero gli elementi $ a_i $ per cui $ \lambda _i $ è positivo, di bianco quelli per cui $ \lambda _i $ è negativo, mentre non coloro quelli che hanno coefficiente nullo.
Poiché c'è almeno un coefficiente diverso da 0 ho colorato almeno un elemento. Inoltre se $ B_j $ avesse elementi neri ma nessun elemento bianco non potrebbe essere $ \lambda _1v_1+\cdots+\lambda_nv_n=0 $ perché la somma delle $ j $-esime componenti dei vettori sarebbe strettamente positiva (sarebbe la somma di alcuni $ \lambda _i $ positivi).

Il problema 22 invece è qui

Abbiamo un grafo $ G $ connesso su $ n\geq 2 $ vertici, e sappiamo che in questo grafo due cicli non hanno mai un arco in comune. Siano $ l_1,\cdots,l_k $ le lunghezze dei $ k\geq 0 $ cicli del grafo.
Un commesso viaggiatore parte da un vertice $ P $ di $ G $ e deve camminare sugli archi del grafo in modo da visitare tutti i vertici e tornare alla fine in $ P $. Determinare il più piccolo intero $ M $ tale che con $ M $ passi il commesso viaggiatore può riuscire nell'impresa.

[Carlein]

Soluzione del 22)

Veramente carino questo problema. Visto che altrettanto vegliardi hanno partecipato alle staffette impunemente,e visto che sono passati un paio di giorni e poichè mi è piaciuto molto, provo a buttare giù quello che ho pensato Spero di non aver cannato
1) E' chiaro che i lati che non giacciono su cicli, li devo usare almeno 2 volte, perchè sono l'unico collegamento tra 2 componenti altrimenti sconnesse,è anche abbastanza chiaro che nei percorsi minimali lo userò 2 volte. Altrettanto chiaro che in un percrso minimale i lati che stanno sui cicli li uso tutti una volta sola. Quindi il totale cercato è 2T+S, dove $ S=\sum_{i=1}^{k}l_i $ e T è il numero di lati che non giacciono su cicli. D'altronde vale T+S=L, con L il numero di lati.
2)Il nostro obeittivo è trovare T. Qui entra in gioco l'osservazione che il grafo è un quasi albero. Difatti supponiamo di rimuovere da ogni ciclo un lato a caso, allora è chiaro che abbiamo un albero e dunque abbiamo che il numero di lati è n-1, d'altronde per l'ipotesi fatta sui cicli che non condividono lati abbiamo perso esattamente k lati, dunque si ha $ n-1=T+S-k $ da cui $ T=n-1-S+k $.
3) Unendo 1) e 2) si ha che $ M=2(n-1+k)-S $.

Una spiegazione accurata di 1) data in seguito

Hai ragione, ho trascurato di chiarire un bel pò di cosette, e devo dire che a chiarirle sono usciti un sacco di passaggi in più di quanto mi aspettavo al primo attacco intuitivo(o meglio barbaro).
Vado
0)Questa proprietà vale per tutti i grafi.Se un lato l non giace su un ciclo e lo rimuovo, allora il grafo restante è sconnesso in due componenti. Difatti se chiamo A e B gli estremi, allora se nel grafo senza l A e B restano connessi da un cammino, restano senza dubbio connessi da un cammino senza ripetizioni di vertici(che ottengo rimuovendo opportunamente pezzi inutili del cammino di prima), questo cammino con l dà un ciclo su cui giace l, assurdo. D'altronde è chiaro che ogni vertice deve conoscere in G-l uno tra A e B, difatti in G conosceva entrambi,prendo il cammino in G con cui conosceva per dire A,se il primo che conosco tra A e B in questo cammino è B, allora non ho ancora usato l (altrimenti conoscevo A prima), viceversa se è B.
1) Costruisco induttivamente il percorso con 2T+S passi. Per n=2, è ovvio. Suppongo che tutti i grafi ad al più n nodi con la proprietà data, abbiano un tale cammino. Prendo un grafo G a n+1 nodi con la data proprietà.Distinguo due casi:
a)C'è un lato l che non giace su nessun ciclo. Allora,tenendo presente 0), se parto da un vertice A di questo lato, la componente connessa di G-l in cui sta A, rispetta l'ipotesi induttiva, faccio lì il mio percorso, vado in B, di nuovo stesso discorso per lui, ritornato in B rifaccio l e sono in A con 2T+S passi.
b)Non c'è tale lato l.Distinguo due casi
b.1)Tutti i vertici hanno grado 2: in tal caso G è un ciclo, e la costruzione è ovvia
b.2)C'è un nodo N di grado più di 2. Allora G-N è sconnesso: difatti vi sono almeno due cicli C e D su cui sta N, i percorsi che connettono un vertice di C e uno di D passano sempre per N, altrimenti similmente a 0) riusciamo a costruire un ciclo che ha lati in comune con C e con D. Siano dunque $ H_1,...,H_j $ le componenti connesse di G-N. Consideriamo i vari grafi $ F_1=H_1+N,F_2=H_2+N...,F_j=H_j+N $ questi sono tutti grafi che rientrano nell'ipotesi induttiva, io dunque parto da N e attuo la strategia ottenuta al passo induttivo per $ F_1 $, ritornato ad N continuo con $ F_2 $ fino a fare $ F_j $ e questo è il percorso che ci va bene.
2)Dimostro che $ M\geq 2T+S $.
2.1)Per la proprietà 0) io ho che un lato l ,contato da T, se tolto sconnette il grafo in 2 componenti W e X. Allora è del tutto chiaro che ogni percorso che partendo da un vertice N che sta diciamo in W, conosce tutti e ritorna in W, dovrà prima passare da W a X e poi il contrario, in tutti e due i casi deve per forza usare l, quindi l è stato usato due volte, e abbiamo già così 2T passi.
2.2)In pratica ora usiamo un miscuglio di quello che abbiamo imparato in 2.1) e in 2) del mio post di sopra.
Dato un percorso generico metto i cicli in due categorie
c.1)Quelli i cui lati vengono usati tutti almeno una volta
c.2) gli altri
Questo corrisponde a fare un percorso sul grafo che otteniamo rimuovendo da ciascun $ z_1,...,z_h $ cicli classificati in c.2), un lato(di più non posso togliere perchè una volta tolto un lato quelli restanti sono lati che non giacciono più su cicli e quindi ho 0), in effetti togliere u lato a un pò di cicli qui come in 2) del mio post precedente comporta un'alberizzazione del grafo che in entrambi i casi mi fa contare bene le cose,qui per 2.1), a 2) del post di prima per il fatto che un'albero ha n-1 lati, in generale perchè l'albero è un caso estremo facile da gestire che dice molto al problema). Ma allora è chiaro che in totale ho almeno quelli contati da c.1 che sono $ \sum_{i=h+1}^{k}l_i $ e poi per quanto appreso in 2.1) $ \sum_{i=1}^{h}2(l_i-1) $ da c.2). Quindi in totale ho $ 2T+\sum_{i=h+1}^{k}l_i+\sum_{i=1}^{h}2(l_i-1)\geq 2T+S $ dal momento che la disuguaglianza vale addendo per addendo( dal momento che $ 2(n-1) > n $ per n>2)

Il problema 23: viewtopic.php?f=16&t=15673