Sikinia
i) Ogni strada in Sikinia è a senso unico. E ogni coppia di città è collegata da esattamente una strada. Dimostrare che esiste una città che può essere raggiunta da tutte le altre direttamente o via al più un'altra città.
ii) Il Parlameno sikiniano consiste di una camera. Ogni parlamentare ha al più 3 nemici. Dimostrare che si può dividere la singola camera in due camere tali che ogni parlamentare ha al più un nemico nella propria camera.
ii) Il Parlameno sikiniano consiste di una camera. Ogni parlamentare ha al più 3 nemici. Dimostrare che si può dividere la singola camera in due camere tali che ogni parlamentare ha al più un nemico nella propria camera.
Risposte
per quanto riguarda il primo punto lo farei per induzione sul numero di città di Sikinia:
per n=2 ok.
suppongo vero per ogni m tale che $2<=ma} se da a esce almeno una strada a è collegata a C tramite una città e C è la città cercata, se da a non esce nessuna strada tutte le città sono collegate ad a direttamente.
giusto?
per n=2 ok.
suppongo vero per ogni m tale che $2<=m
giusto?
Mmh, non capisco perché C sarà direttamente collegata a D, dato che D appartiene ad A..
"TomSawyer":
Mmh, non capisco perché C sarà direttamente collegata a D, dato che D appartiene ad A..
E' utile uno schemino:
B-> C -> A
Le citta' di B sono direttamente collegate con C e siccome le citta' di A non sono direttamente collegate a C, allora C e' direttamente collegata alle citta' di A, e quindi a D.
"TomSawyer":
Mmh, non capisco perché C sarà direttamente collegata a D, dato che D appartiene ad A..
ad A appartengono le città non direttamente collegate a C questo significa che le strade vanno da C a le città di A, per ipotesi tutte le coppie sono collegate tra loro quindi per esempio se F e G sono due città o F è direttamente collegata a G o viceversa. Nel nostro caso le città di A non sono collegate a C e questo implica che C è collegata a tutte le città di A in particolare D
Sì sì, tutto giusto (mi ero dimenticato dei sensi unici 
). Anche la mia soluzione è simile. I due problemi hanno il comune il possibile ed elegante uso dell'extremal principle.
). Anche la mia soluzione è simile. I due problemi hanno il comune il possibile ed elegante uso dell'extremal principle.
Vabbè, sistemiamo il ii)
Sia $G=(V,E)$ il grafo non orientato in cui $V$ sono i parlamentari e $E$ la relazione di inimicizia.
Un taglio di $G$ è un coppia di insiemi del tipo $(S, V-S)$. Un arco $(u,v)$ attraversa il taglio se $u\in S$ e $v\in V-S$. La dimensione del taglio è il numero di archi che attraversano il taglio.
Sia allora $(S, V-S)$ il taglio di dimensione massima. Dimostriamo che esso costituisce la suddivisione della camera richiesta dal problema.
Supponiamo per assurdo WLOG che esistano $s,u,v\in S$ tale che gli archi $(s,u)$ e $(s,v)$ sono in $E$. Ma allora il taglio $(S-{s},V-Suu{s})$ ha dimensione strettamente maggiore della dimensione del taglio $(S,V-S)$. Infatti esiste in $V-S$ al piu' un vertice $w$ tale che $(s,w)\in E$, poiche' ogni parlamentare ha al piu' tre nemici. Dunque la dimensione del taglio aumenta di $2$ a causa degli archi $(s,u)$ e $(s,v)$ e dimuinisce di massimo $1$ a causa di $(s,w)$. Assurdo.
Sia $G=(V,E)$ il grafo non orientato in cui $V$ sono i parlamentari e $E$ la relazione di inimicizia.
Un taglio di $G$ è un coppia di insiemi del tipo $(S, V-S)$. Un arco $(u,v)$ attraversa il taglio se $u\in S$ e $v\in V-S$. La dimensione del taglio è il numero di archi che attraversano il taglio.
Sia allora $(S, V-S)$ il taglio di dimensione massima. Dimostriamo che esso costituisce la suddivisione della camera richiesta dal problema.
Supponiamo per assurdo WLOG che esistano $s,u,v\in S$ tale che gli archi $(s,u)$ e $(s,v)$ sono in $E$. Ma allora il taglio $(S-{s},V-Suu{s})$ ha dimensione strettamente maggiore della dimensione del taglio $(S,V-S)$. Infatti esiste in $V-S$ al piu' un vertice $w$ tale che $(s,w)\in E$, poiche' ogni parlamentare ha al piu' tre nemici. Dunque la dimensione del taglio aumenta di $2$ a causa degli archi $(s,u)$ e $(s,v)$ e dimuinisce di massimo $1$ a causa di $(s,w)$. Assurdo.
Molto carina con i grafi. Anche, col principio dell'invarianza: consideriamo una qualsiasi divisione in due camere. Sia $h$ la somma totale dei nemici che ogni parlamentare ha nella sua camera. Supponiamo che $A$ abbia almeno due nemici nella sua camera; allora ha al piu' un nemico nell'atlra camera. Quindi se cambia camera, $h$ diminuira'. Ma $h$ non puo' diminuire per sempre; ad un certo punto, $h$ raggiungera' il suo minimo assoluto, che e' anche la distribuzione che vogliamo.
"TomSawyer":
extremal principle
ovvero?
Praticamente e' quando si prende l'elemento massimale (o minimale) con una certa proprieta'.
@TomSawyer
from Problem solving strategies?
from Problem solving strategies?
Esatto .
.
"yurifrey":
@TomSawyer
from Problem solving strategies?
chiedo scusa (non so proprio una mazza) ma è un libro?
Sì, un bellissimo libro di Arthur Engel.
Concordo, gran bel libro pieno di esercizi interessantissimi e soluzioni chiare.
Io sono entrato quest'anno a contatto con l'ambiente delle olimpiadi della matematica e ne sono venuto a conoscenza da poco. Se poi si considera che ci sono 14 capitoli con una media di 70 esercizi a capitolo diciamo che mi ci vorrà un po' prima di finirlo...
Io sono entrato quest'anno a contatto con l'ambiente delle olimpiadi della matematica e ne sono venuto a conoscenza da poco. Se poi si considera che ci sono 14 capitoli con una media di 70 esercizi a capitolo diciamo che mi ci vorrà un po' prima di finirlo...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo