A causa di improvvisi eventi catastrofici che hanno recentemente sconvolto le popolazioni di Sud America e Medio Oriente, si sono resi necessari provvedimenti straordinari per assicurare il regolare svolgimento delle competizioni internazionali: pertanto, è stato decretato che nell'anno corrente (2017) le IMO e le IOI si terranno in contemporanea nella città di Alfredd$0$!!!1!!1!
Filippo, risultato vincitore assoluto di entrambe le competizioni nell'anno addietro, si è ora dato alla carriera politica ed, eletto sindaco di Alfredd$0$, è incaricato di organizzare al meglio il grande evento. Il momento topico risiede nella tradizionale visita turistica alle attrazioni della città. Poiché ad Alfredd$0$ fa sempre molto fredd$0$, Filippo ha pensato bene di commissionare la realizzazione di un certo numero di imponenti sculture di ghiaccio aventi per tema le due gare internazionali, le quali verranno collocate nelle $n \ge 4$ piazze del centro urbano. Il giro turistico consterà di un percorso circolare che attraverserà $m$ piazze e altrettante sculture, senza passare mai più di una volta per una stessa piazza (fatta eccezione per quella di partenza/arrivo, che verrà visitata esattamente due volte).
Filippo, da bravo sindaco ed ex-olimpionico, non vuole dare risalto a una particolare gara piuttosto che a un'altra (è affezionato in egual misura ad ambedue le IMO e le IOI), dunque vuole fare in modo che le sculture a tema IMO siano nello stesso numero di quelle a tema IOI, e che quindi il numero di piazze/sculture visitate sia pari. Tuttavia, egli non dispone di una planimetria aggiornata della città di Alfredd$0$. Sa solo che: (i) le piazze sono collegate da alcune strade bidirezionali; (ii) ogni strada collega esattamente due piazze (distinte); (iii) ogni coppia di piazze è collegata da al più una strada; (iv) da ogni piazza partono almeno $3$ strade.
Aiutate Filippo dimostrando che esiste un intero $k \ge 2$ per il quale si può avere $m = 2k$.
Bello
Re: Bello
Sì sì, però senza le sculture di ghiaccio perde tutto il suo fascino... 
Comunque il protagonista della storia in persona mi ha messo al corrente dell'esistenza di una soluzione decisamente più immediata di quella che avevo pensato, quindi in realtà il problema non è interessante quanto pensassi.
Comunque il protagonista della storia in persona mi ha messo al corrente dell'esistenza di una soluzione decisamente più immediata di quella che avevo pensato, quindi in realtà il problema non è interessante quanto pensassi.
-
bern-1-16-4-13
- Messaggi: 78
- Iscritto il: 23 mag 2015, 18:27
Re: Bello
Se non sbaglio nel momento in cui uno vede che due cicli dispari non possono avere più di 1 vertice in comune, e che non si può avere un "ciclo" di cicli dispari (se rappresentiamo con un punto ogni ciclo dispari e con un arco tra due vertici il fatto che i rispettivi cicli abbiano un vertice in comune, supponendo l'assurdo otterremmo un grafo ad albero), diventa un semplice lavoro di stime anche abbastanza larghe
-
bern-1-16-4-13
- Messaggi: 78
- Iscritto il: 23 mag 2015, 18:27
Re: Bello
Ora mi viene il dubbio: la tua domanda è rivolta a cip vero?
Re: Bello
Boh, penso a me, e in ogni caso nel dubbio: è chiaro che esiste un ciclo qualsiasi (parto da un vertice a caso e cammino sugli archi senza mai tornare sul vertice appena visitato, prima o poi passo due volte su uno stesso vertice e ho trovato il ciclo). Ora, supponiamo che sia di lunghezza dispari, altrimenti abbiamo finito; se c'è un arco che collega due vertici del ciclo non consecutivi, o se c'è un vertice esterno al ciclo collegato ad almeno due vertici del ciclo, abbiamo vinto, quindi diciamo che questo non succede. Sotto queste ipotesi, ogni nodo del ciclo, avendo grado $\ge 3$, è collegato ad almeno un vertice esterno. Se collassiamo il ciclo in un solo vertice, il nuovo grafo conserva l'ipotesi sul grado, quindi induttivamente possiamo dire che contiene un ciclo pari (per $n = 4$ è palese). Ma allora anche il grafo iniziale ha un ciclo pari (se non passava per il "ciclo collassato" è ovvio, altrimenti è sempre possibile completare il ciclo con un numero dispari di vertici).
Comunque, con un'idea iniziale molto simile (cioè camminare sul grafo, ma stavolta in modo un po' più intelligente) si può concludere praticamente subito.
Comunque, con un'idea iniziale molto simile (cioè camminare sul grafo, ma stavolta in modo un po' più intelligente) si può concludere praticamente subito.