Dalle USAMO '79

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
pepperoma
Messaggi: 82
Iscritto il: 03 giu 2010, 14:26
Località: Bari
Contatta:

Dalle USAMO '79

Messaggio da pepperoma »

Date 9 persone, ognuna delle quali conosce al più 3 lingue, sapendo che in ogni gruppo di 3 persone ce ne sono almeno 2 che parlano la stessa lingua, dimostrare che esistono 3 persone in grado di dialogare in una lingua comune.
Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Re: Dalle USAMO '79

Messaggio da enomis_costa88 »

E' un po' che non guardo la policy del forum, spero che noi vecchi possiamo ancora rispondere ai post dei ragazzi :-)

Sia la tesi falsa e wlog (a meno di trascurare le lingue parlate da una sola persona) ogni lingua parlata da esattamente 2 persone.
Possiamo quindi un grafo nel quale i vertici rappresentano le persone e gli archi le lingue:
Sia $ G $ un grafo di 9 vertici tale che:
1) i vertici siano di grado al massimo 3
2) comunque scelti 3 vertici c'è un arco tra essi.
Dalla $ [1] $ si ottiene che esistono due vertici non connessi tra di loro.
Siano $ V_1, V_2 $ due vertici non connessi, per la $ [2] $ ogni altro vertice sarà quindi connesso ad almeno uno di essi e la somma dei loro gradi è almeno $ 9-2=7>6 $ ma ciò contraddice la $ [1] $.
"Tu che lo vendi cosa ti compri di migliore?"

Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Rispondi