Ciao a tutti, devo dimostrare che in un gruppo di 6 persone ce ne sono sempre almeno 3 che si conoscono o non si conoscono. vorrei sapere se la mia dimostrazione é corretta.
il mio lavoro: se le persone sono 4, si puó verify facilmente che almeno 2 si conoscono o non si conoscono.
dimostro per induzione: quindi so che per 2n persone, almeno n si conoscono o non si conoscono. devo dimostrarlo per 2n+2 persone. sapendo che sono presenti 2n + 2 persone, allora so che almeno n persone si conoscono o non si conoscono.
devo dimostrare che valga anche per n+1 persone, quindi, aggiungendo 2 persone, esse conoscono qualcuno o non conoscono nessuno. se una delle due non conosce nessuno allora ho dimostrato la prima parte della disgiunzione, ora devo passare la prossima. se quelle due conoscono qualcuno, allora il numero di persone che conoscono é compreso tra 1 ≤ x, y ≤ 2n + 1.
se x = 2n + 1 o y = 2n+1 allora la disgiunzione é dimostrata. se x, y < 2n + 1, allora c'é la possibilità che n+1 persone non si conoscano(o si conoscono) se x,y < 2n+1, per ipotesi induttiva allora si conoscono o non si conoscono perché dall'ipotesi induttiva posso dire che ogni persona conosce un numero compreso di persone da 0 a 2n - 1, in questo intervallo si verify il fatto che si conoscono o non si conoscono
Ok, posso dire che 2n = (2n-1) + 1
Quindi è valida anche 2n
