Due problemini carini sui grafi

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
mitchan88
Messaggi: 469
Iscritto il: 01 gen 1970, 01:00
Contatta:

Due problemini carini sui grafi

Messaggio da mitchan88 » 10 ago 2007, 19:30

Uno dal test della sns 2001/2002 (già risolto da enomis in questi lidi ma lo ripropongo perchè è caruccio :P )
Un sistema di lampadine, connesse fra di loro e dotate ciascuna di un interruttore, ha la proprietà che premendo un interruttore si cambia lo stato della lampadina associata e di ogni lampadina ad essa direttamente collegata. Si dimostri che che se l'unico modo di avere tutte le lampadine spente è quello di lasciare tutti gli interruttori nella posizione iniziale, allora è possibile ottenere qualsiasi configurazione di lampadine accese.
E uno dall'engel
Ad una festa ci sono n>4 invitati, e si sa che comunque presi 4 di essi ve ne è almeno uno che conosce tutti gli altri 3. Dimostrare che esiste una persona che conosce tutte le altre. (ovviamente se a conosce b allora b conosce a)
Enjoy :wink:
[url:197k8v9e]http://antrodimitch.wordpress.com[/url:197k8v9e]

Membro del fan club di Ippo_

Avatar utente
ummagumma
Messaggi: 94
Iscritto il: 22 lug 2007, 11:14

Messaggio da ummagumma » 10 ago 2007, 20:26

perchè usare i grafi (a me ignoti :( ) quando nn ce n'è bisogno:
per il 2: considero una quadrupla A B C D, in cui A conosce gli altri, mentre B e C nn si conoscono. B e C non si conoscono WLOG perchè se si conoscessero la th sarebbe immediata.
posso allora considerare le quadruple composte da A B C Xi, dove Xi è uno degli altri (n-4) invitati
In queste A sarà amico di almeno n-4 da cui A è amico di n-4+3= n-1 amici
A è amico di tutti gli altri.
Probabilmente il grafo connesso è solo una visualizzazione del mio ragionamento

Avatar utente
mitchan88
Messaggi: 469
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da mitchan88 » 12 ago 2007, 12:45

ummagumma ha scritto:perchè usare i grafi (a me ignoti :( ) quando nn ce n'è bisogno:
Si in effetti nessuno dei due problemi richiede l'utilizzo di teoremoni sui grafi :p La mia soluzione è un pò più intricata:
Prendiamo la persona P che conosce più persone, e dividiamo le rimanenti nell'insieme Y di quelle che non conosce e X di quelle che conosce. supponiamo per asurdo che Y non sia vuoto. Allora possiamo creare delle quaterne con P, y€Y e x_i e x_j €X: viste l'ipotesi allora o x_i o x_j conoscono tutti. In particolare, abbiamo che tutte le persone di X si conoscono. Ma allora lmeno una persona conosce più persone di P, assurdo.
[url:197k8v9e]http://antrodimitch.wordpress.com[/url:197k8v9e]

Membro del fan club di Ippo_

Rispondi