C'è gente che parla 3 lingue qui.

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

C'è gente che parla 3 lingue qui.

Messaggioda Giovanni98 » 14/08/2015, 11:18

Ad una festa partecipano 9 ragazzi, ognuno dei quali parla al più 3 lingue. Si sa che comunque si prendano due ragazzi, questi riescono a comunicare (parlano quindi al meno una stessa lingua). Dimostrare che esiste una lingua parlata da 5 ragazzi.
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30

Re: C'è gente che parla 3 lingue qui.

Messaggioda Morets » 19/08/2015, 10:19

Se c'è almeno una persona che parla una lingua, la tesi è banalmente verificata (infatti tutti devono parlare quella stessa lingua).
Se c'è almeno una persona che parla esattamente due lingue la tesi è verificata, infatti dovendo aver una lingua comune con gli altri allora almeno una delle due lingue è parlata da almeno 5 persone.
Rimane da verificare il caso in cui tutte le persone parlino tre lingue. Considero la prima persona che parlerà tre lingue ABC allora almeno una di queste tre lingue, senza perdita di generalità A, è parlata da almeno altre 3 persone (complessivamente da almeno 4 quindi). Ora, volendo provare a costruire un controesempio, voglio che le 5 persone che non parlano A possano comunicare con le altre 4 senza che una lingua sia parlata da più di 4 persone. Questo implica che per ogni persona successiva devo poter scegliere una lingua diversa da A da ognuna delle 4 persone che parlano A. Quindi almeno due persone che parlano A hanno un'altra lingua in comune. Arrivo così alla sesta persona. Ora questa seconda lingua, senza perdita di generalità B, è parlata da 4 persone. Deve esistere un'altra lingua diversa parlata da due persone che parlino A. Arrivo alla nona persona e analogamente a prima deve esistere un'altra lingua parlata da due persone che parlano A. Riconsidero ora le prime 4 persone tra queste ve ne devono essere almeno due che parlano A e due lingue che sono parlate da una coppia di persone che parlano A. Senza perdita di generalità supponiamo che ABC sia una di queste, grazie ad A parla ad altre 3 persone, grazie a B parla ad altre 3 persone (una comune, quindi totale 5), grazie a C parla ad altre tre persone (se C è la lingua parlata dalla settima e dall'ottava) o ad altre due persone (se C è la lingua parlata dalla nona) (in ogni caso una delle persone parla anche A quindi il totale è 7 o 6). Nel primo caso ABC parla 3 lingue che sono già parlate da 4 persone (incluso lui stesso), ma parla solo con altre 7 persone, nell'altro caso una lingua è parlata da solo tre persone, ma ABC parla con sei persone quindi può arrivare al massimo a 7. Ne segue che o A o B o C è parlata da almeno 5 persone.
Morets
 
Messaggi: 61
Iscritto il: 27/11/2013, 17:24


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti