Dati due naturali m ed n, trovare il minimo intero positivo k (funzione di m ed n) tale che scelte casualmente k persone:
-o ci sono almeno m coppie disgiunte (cioe' in totale 2m persone e una persona appartiene al massimo ad una coppia) tali che ciascun elemento della coppia conosce l'altro
-o ci sono almeno n coppie disgiunte (cioe' in totale 2n persone) tali che ciascun elemento della coppia non conosce l'altro.
Nota: se A conosce B allora automaticamente B conosce A.
Questo problema e' il piu' difficile tra quelli che ho postato oggi (gli altri sono in algebra e TdN ), quindi consiglio ai piu' esperti di cimentarsi soprattutto su questo e magari lasciare gli altri, almeno per qualche giorno, per chi ci vuole provare...
Ciao!
Maria
tra k persone alcune si conoscono, altre no...
Ma sì, una volta tanto mi spaccio per esperto...
Poniamo $ k=F(m,n) $
Visto che $ F(m,n)=F(n,m) $ possiamo porre $ m\geq n $
Notiamo subito che $ 2m+n-2<k $
Difatti potremmo porre che esista un insieme di $ 2m-1 $ persone che si conoscono tutte fra loro, mentre ciascuna delle rimanenti $ n-1 $ persone non conosce nessuno, e otterremmo che non esistono né $ m $ coppie disgiunte che si conoscono, né $ n $ coppie disgiunte che non si conoscono.
Resta da dimostrare che $ 2m+n-1=k $
Per induzione:
PASSO BASE: $ F(1,1)=2*1+1-1=2 $ è banalmente vero.
PASSO INDUTTIVO:
1) Se $ F(m,n)=2m+n-1 $ allora $ F(m,n+1)=2m+n $ dove $ m>n $
Dimostrazione:
-il caso in cui esistano $ m $ coppie che si conoscono è banale.
-ora il caso in cui esistano $ n $ coppie che non si conoscono ma non $ m $ coppie che si conoscono:
se tra le persone esterne alle $ n $ coppie disgiunte esiste una coppia di persone che non si conoscono, allora tesi è dimostrata. Dunque possiamo considerare che le persone esterne alle $ n $ si conoscano tutte tra loro. Inoltre se in una delle $ n $ coppie, entrambi i membri non conoscono una persona esterna alle $ n $ coppie, dove la persona non coincide per i due membri, allora la tesi è dimostrata. Quindi nei casi restanti per ogni coppia almeno un mebro conosce almeno $ 2m-n-1 $ persone esterne alle n coppie. Dunque, poiché $ m>n $, esistono $ m $ coppie disgiunte di persone che si conoscono.
2) Se $ F(m,n)=2m+n-1 $ allora $ F(m+1,n)=2m+n+1 $ dove $ m\geq n $
Dimostrazione:
Come la precedente, tranne per i casi affrontati alla fine, dove in ognuna delle $ m $ coppie, almeno un membro non conosce almeno $ n $ persone esterne alle $ m $ coppie. Dunque esistono $ n $ coppie disgiunte di persone che non si conoscono.
QED
Poniamo $ k=F(m,n) $
Visto che $ F(m,n)=F(n,m) $ possiamo porre $ m\geq n $
Notiamo subito che $ 2m+n-2<k $
Difatti potremmo porre che esista un insieme di $ 2m-1 $ persone che si conoscono tutte fra loro, mentre ciascuna delle rimanenti $ n-1 $ persone non conosce nessuno, e otterremmo che non esistono né $ m $ coppie disgiunte che si conoscono, né $ n $ coppie disgiunte che non si conoscono.
Resta da dimostrare che $ 2m+n-1=k $
Per induzione:
PASSO BASE: $ F(1,1)=2*1+1-1=2 $ è banalmente vero.
PASSO INDUTTIVO:
1) Se $ F(m,n)=2m+n-1 $ allora $ F(m,n+1)=2m+n $ dove $ m>n $
Dimostrazione:
-il caso in cui esistano $ m $ coppie che si conoscono è banale.
-ora il caso in cui esistano $ n $ coppie che non si conoscono ma non $ m $ coppie che si conoscono:
se tra le persone esterne alle $ n $ coppie disgiunte esiste una coppia di persone che non si conoscono, allora tesi è dimostrata. Dunque possiamo considerare che le persone esterne alle $ n $ si conoscano tutte tra loro. Inoltre se in una delle $ n $ coppie, entrambi i membri non conoscono una persona esterna alle $ n $ coppie, dove la persona non coincide per i due membri, allora la tesi è dimostrata. Quindi nei casi restanti per ogni coppia almeno un mebro conosce almeno $ 2m-n-1 $ persone esterne alle n coppie. Dunque, poiché $ m>n $, esistono $ m $ coppie disgiunte di persone che si conoscono.
2) Se $ F(m,n)=2m+n-1 $ allora $ F(m+1,n)=2m+n+1 $ dove $ m\geq n $
Dimostrazione:
Come la precedente, tranne per i casi affrontati alla fine, dove in ognuna delle $ m $ coppie, almeno un membro non conosce almeno $ n $ persone esterne alle $ m $ coppie. Dunque esistono $ n $ coppie disgiunte di persone che non si conoscono.
QED
"Sei la Barbara della situazione!" (Tap)
Vabeh, non pretendo di essere lucido a quest'ora...
- Trasformo le persone in un grafo, dove due persone sono collegate se e soltanto se si conoscono
- Indico con f(a,b)=k il minimo k tale che ogni grafico di cardinalità >= k ha (a coppie disgiunte di vertici collegati) o (b coppie disgiunte di vertici non collegati).
Lemma: f(a,b)=f(b,a).
Se un grafo di k vertici ha (a coppie disgiunte collegate), allora il suo complementare ha (a coppie disgiunte scollegate), lo stesso con b, quindi il lemma, se vale la pena chiamarlo tale, è dimostrato.
Grazie al lemma, d'ora in poi suporremo sempre $ ~ a \ge b $.
Claim: $ ~ f(a,b) = 2a + b - 1 $.
Stima dal basso, ovvero: Per ogni a,b, esiste un grafo di 2a + b - 2 vertici che non contiene nè (a coppie disgiunte collegate) nè (b coppie disgiunte scollegate).
Prendiamo un grafo formato in questo modo:
- 2a-1 vertici collegati tra loro in tutti i modi
- i restanti b-1 vertici scollegati tra loro e con tutti gli altri.
Allora:
- se vogliamo (a coppie disgiunte di vertici collegati), in tutto dovremo avere almeno 2a vertici con almeno un collegamento, ma ne abbiamo 2a-1.
- se vogliamo (b coppie disgiunte di vertici scollegati), ogni coppia dovrà avere almeno un vertice tra i (b-1) che sono scollegati, ma questi sono solo (b-1), mentre vogliamo b coppie.
Stima dall'alto, cioè ogni grafo con (2a + b - 1) coppie, ha quelle famose coppie disgiunte. La faccio per induzione.
Divido l'induzione in due passi:
Induzione 1: f(a,a) = 3a-1. Cioè copro i casi in cui a=b.
- f(1,1) = 2 = 3*1-1, ovviamente.
- Sappiamo che f(a,a) = 3a-1. Dimostriamo che f(a+1,a+1)=3a+2. Prendiamo un grafo di 3a+2 vertici, tirando fuori 3 vertici x,y,z, i vertici restanti formano un grafo di 3a-1 vertici, quindi hanno o (a coppie disgiunte collegate) o (a coppie disgiunte scollegate). Senza perdita di generalità, assumo che siano collegate. Dimostriamolo per assurdo, ovvero: è possibile che non si siano nè (a+1) collegate n+ (a+1) scollegate? Facciamo finta di no.Se una coppia tra xy,yz,zx è collegata, abbiamo (a+1) coppie disgiunte collegate, contro l'ipotesi.
Quindi xy,yz,zx sono scollegate.
Ora prendiamo un altro vertice t e facciamo lo stesso ragionamento con y,z,t. Tra le (3a-1) restanti ce ne sono (a) scollegate, aggiungendo yz ne abbiamo (a+1), impossibile. Allora tra le restanti ce ne sono (a) collegate. Quindi yz,zt,ty sono scollegate.
Andando avanti così, possiamo concludere che sono tutte scollegate, ma quindi, ovviamente, possiamo trovare (a+1) coppie disgiunte scollegate.
Induzione 2: voglio dimostrare che f(a+1,b) = f(a,b) + 2.
Prendiamo un grafo di f(a,b) + 2 vertici.
Togliamo i vertici x,y.
Se nel restante grafo di f(a,b) vertici ci sono (b coppie scollegate), allora anche tutto il grafo ha (b coppie scollegate), ok. Altrimenti ci sono (a coppie collegate). Se xy sono collegati, abbiamo (a+1) coppie collegate. Altrimenti xy sono scollegati.
Ma questo lo possiamo fare per tutte le coppie di vertici: se cerchiamo di un ottenere un grafo senza tutte quegli insiemi di coppie collegate o scollegate, troviamo che tutte le coppie di vertici sono scollegate.
Ma allora ne troviamo (a+1) scollegate.
Quindi, riassumento le induzioni:
- Trovo che f(a,a) = 3a-1
- Posso trovare anche f(a+1,a), f(a+2,a), f(a+3,a), e quindi questa induzione raggiunge tutte le coppie (a,b), dimostrando che f(a,b) con a>b è 2a + b -1, con a < b è 2b - a + 1.
Ah, non mi convince molto... quindi spero che si sia un errore così almeno resto convinto della sua falsità
EDIT: a essere così poco convinti e tanto particolareggiati, piever mi ha fregato l'esercizio
- Trasformo le persone in un grafo, dove due persone sono collegate se e soltanto se si conoscono
- Indico con f(a,b)=k il minimo k tale che ogni grafico di cardinalità >= k ha (a coppie disgiunte di vertici collegati) o (b coppie disgiunte di vertici non collegati).
Lemma: f(a,b)=f(b,a).
Se un grafo di k vertici ha (a coppie disgiunte collegate), allora il suo complementare ha (a coppie disgiunte scollegate), lo stesso con b, quindi il lemma, se vale la pena chiamarlo tale, è dimostrato.
Grazie al lemma, d'ora in poi suporremo sempre $ ~ a \ge b $.
Claim: $ ~ f(a,b) = 2a + b - 1 $.
Stima dal basso, ovvero: Per ogni a,b, esiste un grafo di 2a + b - 2 vertici che non contiene nè (a coppie disgiunte collegate) nè (b coppie disgiunte scollegate).
Prendiamo un grafo formato in questo modo:
- 2a-1 vertici collegati tra loro in tutti i modi
- i restanti b-1 vertici scollegati tra loro e con tutti gli altri.
Allora:
- se vogliamo (a coppie disgiunte di vertici collegati), in tutto dovremo avere almeno 2a vertici con almeno un collegamento, ma ne abbiamo 2a-1.
- se vogliamo (b coppie disgiunte di vertici scollegati), ogni coppia dovrà avere almeno un vertice tra i (b-1) che sono scollegati, ma questi sono solo (b-1), mentre vogliamo b coppie.
Stima dall'alto, cioè ogni grafo con (2a + b - 1) coppie, ha quelle famose coppie disgiunte. La faccio per induzione.
Divido l'induzione in due passi:
Induzione 1: f(a,a) = 3a-1. Cioè copro i casi in cui a=b.
- f(1,1) = 2 = 3*1-1, ovviamente.
- Sappiamo che f(a,a) = 3a-1. Dimostriamo che f(a+1,a+1)=3a+2. Prendiamo un grafo di 3a+2 vertici, tirando fuori 3 vertici x,y,z, i vertici restanti formano un grafo di 3a-1 vertici, quindi hanno o (a coppie disgiunte collegate) o (a coppie disgiunte scollegate). Senza perdita di generalità, assumo che siano collegate. Dimostriamolo per assurdo, ovvero: è possibile che non si siano nè (a+1) collegate n+ (a+1) scollegate? Facciamo finta di no.Se una coppia tra xy,yz,zx è collegata, abbiamo (a+1) coppie disgiunte collegate, contro l'ipotesi.
Quindi xy,yz,zx sono scollegate.
Ora prendiamo un altro vertice t e facciamo lo stesso ragionamento con y,z,t. Tra le (3a-1) restanti ce ne sono (a) scollegate, aggiungendo yz ne abbiamo (a+1), impossibile. Allora tra le restanti ce ne sono (a) collegate. Quindi yz,zt,ty sono scollegate.
Andando avanti così, possiamo concludere che sono tutte scollegate, ma quindi, ovviamente, possiamo trovare (a+1) coppie disgiunte scollegate.
Induzione 2: voglio dimostrare che f(a+1,b) = f(a,b) + 2.
Prendiamo un grafo di f(a,b) + 2 vertici.
Togliamo i vertici x,y.
Se nel restante grafo di f(a,b) vertici ci sono (b coppie scollegate), allora anche tutto il grafo ha (b coppie scollegate), ok. Altrimenti ci sono (a coppie collegate). Se xy sono collegati, abbiamo (a+1) coppie collegate. Altrimenti xy sono scollegati.
Ma questo lo possiamo fare per tutte le coppie di vertici: se cerchiamo di un ottenere un grafo senza tutte quegli insiemi di coppie collegate o scollegate, troviamo che tutte le coppie di vertici sono scollegate.
Ma allora ne troviamo (a+1) scollegate.
Quindi, riassumento le induzioni:
- Trovo che f(a,a) = 3a-1
- Posso trovare anche f(a+1,a), f(a+2,a), f(a+3,a), e quindi questa induzione raggiunge tutte le coppie (a,b), dimostrando che f(a,b) con a>b è 2a + b -1, con a < b è 2b - a + 1.
Ah, non mi convince molto... quindi spero che si sia un errore così almeno resto convinto della sua falsità
EDIT: a essere così poco convinti e tanto particolareggiati, piever mi ha fregato l'esercizio
