Pagina 1 di 1

Amicizie esagerate

Inviato: 20 ago 2011, 13:21
da LukasEta
Comunque si scelgano quattro studenti della Scuola Sant'anna , ce n'è almeno uno dei quattro che è amico degli altri tre. Dimostrare che esiste almeno uno studente della Scuola che è amico di tutti gli altri.


Ecco la mia soluzione,ma non mi convince come ho usato l'induzione..


Con 4 studenti,la tesi è banalmente verificata
Per ipotesi induttiva, considero che la tesi sia valida se nella scuola ci sono $n$ studenti.
Allora uno studente di nome A è amico di tutti gli altri $n-1$ studenti.
Arriva un nuovo studente, B, e ho due casi:
Caso 1: egli è amico di A,ma allora A è amico di tutti gli altri studenti,dunque la tesi è verificata anche con n+1 studenti.

Caso 2:non è amico di A.
Consideriamo tutte le quaterne di studenti che comprendono anche A e B: dal momento che non c'è amicizia tra A e B, uno tra gli altri due studenti in ogni quaterna deve essere amico degli altri tre. Quindi,sicuramente c'è amicizia tra i due studenti diversi da A e B, in ogni quaterna che comprende anche A e B. Quindi, se prendiamo uno studente diverso da A e B , egli sarà sicuramente amico di tutti gli altri studenti diversi da A e B,ma per ipotesi induttiva è anche sicuramente amico di A (l'amicizia è reciproca). Tuttavia,per ogni coppia di studenti diversi da A e B,almeno uno è amico anche di B (avevamo detto che se non c'è amicizia tra A e B,allora necessariamente uno dei due elementi diversi da A e B in ogni quaterna è amico degli altri 3,quindi anche di B). Questo studente che è amico anche di B è dunque amico di tutti quanti,dunque la tesi è dimostrata.

Re: Amicizie esagerate

Inviato: 20 ago 2011, 14:35
da dario2994
Tutto giusto :wink:

Re: Amicizie esagerate

Inviato: 20 ago 2011, 15:50
da LukasEta
Uh,meno male :D grazie!