Problema sugli insiemi

[UmbertoM1]

Consideriamo un insieme A di 8 elementi. Si trovi il numero massimo di sottoinsiemi di A, ciascuno
formato da 3 elementi, che `e possibile scegliere in modo che l’intersezione tra due qualsiasi di essi
non sia mai un insieme di 2 elementi.

[sradesca]

sono 9

[FreddyKruger]

Come lo hai dimostrato?

[spluk1]

Dato un insieme di 8 elementi il numero di coppie distinte è $ ( ( 8 ),( 2 ) )=28 $ . Prendo in considerazione un sottoinsieme generico di 3 elementi distinti ABC; in questo sottoinsieme ci sono 3 coppie distinte: AB, BC e CA. Poiché il numero di coppie distinte è 28 e ogni sottoinsieme di 3 elementi contiene 3 coppie distinte, allora il massimo numero di sottoinsiemi di 3 elementi che non hanno coppie di elementi in comune( ovvero che non hanno 2 elementi in comune) è $ 28 -: 3=9,bar (3) $ . Infine, poiché il numero di sottoinsiemi deve essere intero, si ha che è 9 ( il più grande intero minore di $ 9,bar (3) $ ).

[marco99991]

Ma puoi dire che 9 è un limite, non che sia una soluzione. Ad esempio io ne ho trovato 7 (a tentativi):
145
246
356
123
167
257
347
Non ho usato il numero 8, forse provando se ne trova una in più, comunque sono almeno 7

[marco99991]

ora ne ho trovati 8

123
345
567
781
146
258
368
247

non riesco a trovare 9 sottoinsiemi

[marmi1]

Ritengo $8$ sia anche il massimo,
Infatti ogni elemento può trovarsi al massimo in $ 3 $ sottoinsiemi.
Ciao,
Andrea

[marco99991]

Giusto marmi!

[spluk1]

E' vero, avete ragione! Ogni elemento può essere contenuto solo in 3 sottoinsiemi; infatti se fosse contenuto in 4 sottoinsiemi significherebbe che esistono 8 coppie distinte che contengono quell'elemento; ma esistono solo 7 coppie distinte che contengono un determinato elemento ( 12, 13, 14, 15, 16, 17, 18). Visto che ogni elemento compare solo in 3 sottoinsiemi, allora, al massimo, ci saranno in totale 24 elementi, vale a dire 8 sottoinsiemi di 3 elementi.