Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie

Jeden element wspólny

STUDIA

  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
1 odpowiedź w tym temacie

#1 ostrich

ostrich

    Ułamek

  • Użytkownik
  • 5 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 19.08.2013 - 22:38

Dla zbiorów 4 elementowych, wyznaczyłem że minimalna liczba różnych elementów wynosi 10. Nie jestem pewnien tego rozwiązania, może da się to zrobić mniejszą ilością:

{1,2,3,4} , {1,5,6,7} , {2,5,8,9} , {3,6,8,10}

 

Mając przykładowo zbiory 5 elementowe, jak wyznaczyć minimalną liczbę różnych elementów, tak aby:

- w każdym zbiorze było dokładnie 5 elementów

- każdy zbiór miał dokładnie JEDEN element wspólny z innym zbiorem

- liczba zbiorów wynosiła conajmniej 5

 

Jak wyznaczyć tę liczbę dla np. 8, 10 elementów w zbiorze?

 

 


  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 hmm

hmm

    Operator całkujący

  • VIP
  • 478 postów
312
Instruktor I
  • Płeć:Mężczyzna

Napisano 24.08.2013 - 23:12

Pierwsza obserwacja: jeżeli zbiory n-elementowe oznaczymy przez A_i1\leq i\leq NN\geq n, to szukaną minimalną ilość elementów można zapisać jako minimum z |A_1\cup A_2\cup\ldots\cup A_N|.

 

Jest teraz jasne, że moglibyśmy zażądać, żeby liczba zbiorów była równa dokładnie n, bo jeśli zbiory A_1,A_2,\ldots,A_N spełniają warunki zadania, to zbiory A_1,A_2,\ldots, A_n także spełniają te warunki, a przy tym |A_1\cup\ldots\cup A_n|\leq |A_1\cup\ldots\cup A_N|.

 

Teraz wystarczy skorzystać z zasady włączeń i wyłączeń: |A_1\cup A_2\cup \ldots \cup A_n|=\sum_{i=1}^n |A_i| - \sum_{i>j} |A_i\cap A_j| +\sum_{i>j>k} |A_i\cap A_j\cap A_k| -\ldots. Pierwszy składnik na mocy założenia pierwszego jest równy n^2. Drugi składnik na mocy założenia drugiego jest równy n\choose 2. Całą resztę można zinterpretować jako ilość elementów, które występują przynajmniej w trzech zbiorach. Jest to więc liczba nieujemna. Co więcej jeśli dla dowolnych i,j,k będziemy mieli A_i\cap A_j\cap A_k=\emptyset, to reszta będzie równa zero.

 

Zbiory o powyższej dodatkowej własności (przekrój dowolnych trzech zbiorów jest pusty) zawsze można skonstruować, w podobny sposób jak zrobiłeś to dla n=4. A więc minimalna ilość to n^2 - {n\choose 2}=\frac{n(n+1)}{2}. Np. dla n=5 będzie to minimalnie 15 elementów.


  • 0