OliForum Matematico

Uno dal test della sns 2001/2002 (già risolto da enomis in questi lidi ma lo ripropongo perchè è caruccio )

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

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

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.