Siano dati tre insiemi $ A $, $ B $, e $ C $ con $ |A|=|B|=100 $, sia $ n(S) $ il numero dei sottoinsiemi dell'insieme $ S $, compreso l'insieme vuoto ed $ S $ stesso, trovare il minimo di $ |A\cap B \cap C| $ sapendo che:
$ n(A)+n(B)+n(C)=n(A \cup B \cup C) $
Insiemi e sottoinsiemi
Insiemi e sottoinsiemi
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »
-
Albertobucci95
- Messaggi: 45
- Iscritto il: 12 gen 2013, 15:00
Re: Insiemi e sottoinsiemi
Allora $ n(M)=2^M $ quindi abbiamo che i due insiemi $ n(A) $ e $ n(B) $ hanno entrambi
$ 2^100 $ sottoinsiemi.
Adesso per far si che $ n(A)+n(B)+n(c) $ sia una potenza di due (visto che deve essere uguale a $ n(A \cup B \cup C) $) bisogna che $ n(C)=2^101 $ deve quindi avere $ 101 $ elementi.
A questo punto sappiamo che $ |C|=101 $ e che $ |A \cup B \cup C|=102 $.
Quindi il $ min(A \cap B \cap C)= $
$ 2^100 $ sottoinsiemi.
Adesso per far si che $ n(A)+n(B)+n(c) $ sia una potenza di due (visto che deve essere uguale a $ n(A \cup B \cup C) $) bisogna che $ n(C)=2^101 $ deve quindi avere $ 101 $ elementi.
A questo punto sappiamo che $ |C|=101 $ e che $ |A \cup B \cup C|=102 $.
Quindi il $ min(A \cap B \cap C)= $
Re: Insiemi e sottoinsiemi
Non leggo il risultato, qual è il minimo?
Questo è il punto in cui mi blocco.
Questo è il punto in cui mi blocco.
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »
Re: Insiemi e sottoinsiemi
Direi che non c'è scritto... 
Io seguirei questa strada:
Io seguirei questa strada:
Testo nascosto:
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
-
Albertobucci95
- Messaggi: 45
- Iscritto il: 12 gen 2013, 15:00
Re: Insiemi e sottoinsiemi
Si scusate all'inizio volevo scrivere la soluzione ma poi per la fretta ho messo solo metà, anche perchè così qualcuno che non aveva le giuste basi teoriche poteva comunque affrontare la seconda parte, comunque proseguiamo sfruttando l'aiuto di Drago:
Se gli insiemi $ A $ e $ B $ hanno meno di $ 98 $ elementi in comune vi sarebbero almeno $ 104 $ elementi nell'unione dei $ 3 $ insiemi, contrariamente a quanto già dimostrato.
Quindi $ A \cap B $ ha cardinalità compresa tra $ 98 $ e $ 100 $.
I casi $ A \cap C $ e $ B \cap C $ sono simmetrici e per lo stesso ragionamento di prima devono avere cardinalità compresa tra $ 99 $ e $ 100 $.
Adesso bisogna vedere i vari casi e capire per quali si ha $ A \cap B \cap C $ minimo:
$ 1) $ se $ |A \cap C|=100 $ allora l'insieme $ B $ deve avere per forza un elemento diverso sia da $ A $ che da $ C $ e gli altri o tutti uguali ad $ A $ o tutti uguali ad $ A $ tranne uno, per questi casi quello con $ |A \cap B \cap C| $ minimo è il secondo che vale $ 98 $
$ 2) $ se $ |A \cap C|=99 $ allora l'insieme $ B $ deve avere per forza tutti gli elementi appartenenti anche ad $ A $ o $ C $ e qui si aprono tre sottocasi a secoda di quanto vale $ |A \cap B| $ se vale $ 100 $ è $ 99 $, se vale $ 99 $ è $ 98 $ ed infine se vale $ 98 $ è $ 97 $.
Si ha quindi che il $ min(|A \cap B \cap C|)=97 $
Se gli insiemi $ A $ e $ B $ hanno meno di $ 98 $ elementi in comune vi sarebbero almeno $ 104 $ elementi nell'unione dei $ 3 $ insiemi, contrariamente a quanto già dimostrato.
Quindi $ A \cap B $ ha cardinalità compresa tra $ 98 $ e $ 100 $.
I casi $ A \cap C $ e $ B \cap C $ sono simmetrici e per lo stesso ragionamento di prima devono avere cardinalità compresa tra $ 99 $ e $ 100 $.
Adesso bisogna vedere i vari casi e capire per quali si ha $ A \cap B \cap C $ minimo:
$ 1) $ se $ |A \cap C|=100 $ allora l'insieme $ B $ deve avere per forza un elemento diverso sia da $ A $ che da $ C $ e gli altri o tutti uguali ad $ A $ o tutti uguali ad $ A $ tranne uno, per questi casi quello con $ |A \cap B \cap C| $ minimo è il secondo che vale $ 98 $
$ 2) $ se $ |A \cap C|=99 $ allora l'insieme $ B $ deve avere per forza tutti gli elementi appartenenti anche ad $ A $ o $ C $ e qui si aprono tre sottocasi a secoda di quanto vale $ |A \cap B| $ se vale $ 100 $ è $ 99 $, se vale $ 99 $ è $ 98 $ ed infine se vale $ 98 $ è $ 97 $.
Si ha quindi che il $ min(|A \cap B \cap C|)=97 $