szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna
 Tytuł: liczba zbiorów
PostNapisane: 18 kwi 2014, o 18:48 
Użytkownik

Posty: 185
Jaka jest największa liczba zbiorów, które można utworzyć z n zbiorów za pomocą operacji \cup , \setminus?
n jest całkowite i dodatnie

Proszę o samą prawidłową odpowiedź na to pytanie.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna
 Tytuł: liczba zbiorów
PostNapisane: 18 kwi 2014, o 19:49 
Użytkownik

Posty: 1017
Jeśli dobrze pamiętam to 2^{2^n}. Ale zamiast znać wynik wypada zrozumieć to, skąd mamy taki wynik.
Góra
Mężczyzna
 Tytuł: liczba zbiorów
PostNapisane: 18 kwi 2014, o 19:57 
Użytkownik

Posty: 185
To nie jest prawda - z jednego zbioru mogę co najwyżej 2 zbiory utworzyć, a nie 4.
Góra
Mężczyzna
 Tytuł: liczba zbiorów
PostNapisane: 18 kwi 2014, o 20:12 
Użytkownik

Posty: 1017
Po pierwsze rozpatrujemy dwa działania: sumę i różnicę tak? Dla n=1 wzór jest prawdziwy, mamy takich obszarów jest 4.Jak narysujesz sobie sytuację dla n=2 to co masz? No niby jak narysujesz sobie jak się przecinają zbiory to po ponumerowaniu masz ich 4, ale możesz je przecież dodawać i odejmować od siebie.

Ilustracja dla n=2
Obrazek

No i jakie tam masz obszary?

1 , 2 , 3 , 4 ,\\
4 \cup 1 , 4 \cup 2 , 4 \cup, 3\\
1 \cup 2 , 1\cup 3, 2 \cup 3 , \\
1 \cup 2 \cup  3 \cup 4, \\
2 \cup 1 \cup 4, 3 \cup 2 \cup 4, 1 \cup 2 \cup 3, 2\cup 3 \cup 1 \\
\emptyset

Mamy ich 16, czyli tyle, ile mówiłem: 2^{2^2}=2^4=16

Ten rysunek i to rozpisanie chyba dobrze to ilustruje?
Góra
Mężczyzna
 Tytuł: liczba zbiorów
PostNapisane: 18 kwi 2014, o 22:24 
Użytkownik

Posty: 39
Jako, że autor tematu nie wspomniał, aby dane zbiory były elementami jakiejś struktury zbiorów z jedynką, nie będę istnienia takiej jedynki(obszar 4 na obrazku) zakładał.
Mając n zbiorów, ich sumę możemy podzielić(wykorzystując sumy i różnice, a w zasadzie przecięcia, które można przez nie wyrazić) maksymalnie(w sytuacji, w której wszystkie przecinają się nietrywialnie i pomiędzy żadnymi z nich nie zachodzi zawieranie) na 2^{n} - 1 rozłącznych zbiorów(wyłączając zbiór pusty). Podział ten jest jednoznaczny. Wszystkie możliwe do uzyskania zbiory będą sumami tych zbiorów. Stąd mamy 2^{2^n - 1}.
Jeżeli założyć, że istnieje jakaś przestrzeń, jedynka(taki zbiór, że suma rozważanych zbiorów zawiera się właściwie w nim), to wynik jezarka jest, jak najbardziej poprawny(również dla n=1, wtedy rzeczywiście wychodzi 4).
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 liczba zbiorów - zadanie 2  wielkireturner  4
 zawieranie zbiorow - zadanie 5  byleniesebus  1
 równoliczność zbiorów - zadanie 53  method8  1
 Równoliczność zbiorów problem  bm1209  2
 Przystawanie zbiorów, ideał  petro  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl