szukanie zaawansowane
 [ Posty: 17 ]  Przejdź na stronę 1, 2  Następna strona
Autor Wiadomość
Mężczyzna
PostNapisane: 16 maja 2011, o 18:46 
Użytkownik

Posty: 106
Lokalizacja: Kraków
Zamieszczam zadania elementarne z SSDNM (Środowiskowe Studia Doktoranckie z Nauk Matematycznych). Jest to pierwsza część egzaminu, pozostałe zadania (tzw. matematyczne) przyślę później. Egzamin odbył się dzisiaj (16.05.2011), należało oddać 5 zadań, w tym maksymalnie 2 zadania elementarne.

1. Niech m(A_1,...,A_7) oznacza liczbę zbiorów możliwych do wykonstruowania ze zbiorów A_1,...,A_7 \subseteq R za pomocą operacji: \, \cap , \cup . Ile wynosi maksimum funkcji m ? Podać przykład układu realizującego maksimum.

2. Relację równoważności nazwijmy sprawiedliwą, gdy jej wszystkie klasy abstrakcji są równoliczne. Wyznaczyć moc zbioru wszystkich sprawiedliwych relacji równoważności w zbiorze liczb naturalnych.

3. Na ile sposobów można rozmieścić 8 wież na szachownicy 8 \times 8 tak, aby żadne dwie nie biły się nawzajem oraz żadna nie stała na głównej przekątnej szachownicy ?

-- 17 maja 2011, o 23:19 --

Co do pierwszego zadania , to obserwacje są takie, że \cap jest zbędny, bo przecięcie da się przedstawić za pomocą operacji sumy i różnicy. Druga obserwacja to fakt, że jeżeli jakiś zbiór skonstruowaliśmy za pomocą sum i różnic , to możemy go skonstruować za pomocą sum i tylko jednej różnicy. Myślę, że to dobry fundament do rozważań

Co do zadania 3, to zrobiłem go na egzaminie tak, że zaczynam od pierwszej kolumny i mam 7 możliwości ustawienia pierwszej wieży. Załóżmy, że ustawiam ją w i-tym wierszu (0<i \le 8). Pomysł polega na tym , żeby nie przechodzić do drugiej kolumny teraz tylko do i-tej, ustawiamy w j-tym wierszu i przechodzimy do j-tej kolumny .... itd. To ułatwia znacznie sprawę. Otrzymałem wynik 7 \cdot 7!
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna
PostNapisane: 3 wrz 2011, o 20:50 
Użytkownik

Posty: 105
Do zadania 3 może przydać się znajomość tzw. wieżomianów.
Góra
Mężczyzna
PostNapisane: 12 maja 2012, o 14:58 
Użytkownik

Posty: 1272
Lokalizacja: Warszawa
nie rozumiem podejścia do zadania 3, ale wydaje mi się że jest ono błędne..

zadanie jest proste jeśli zastosuje się wieżomiany.. mamy planszę B wymiarów 8\times 8 bez przekątnej i 8 wież do dyspozycji, aby zgodnie z zasadami rozstawić je na niej.. niech r(B) to wieżomian dla planszy B, a r_n(B) to współczynnik przy x^n w wieżomianie czyli to co nas interesuje - liczba sposobów rozstawienia n wież na danej planszy zgodnie z zasadami.. liczenie wieżomianu dla B jest oczywiście straszne, ale trywialne jest policzenie wieżomianu dla dopełnienia czyli B', bowiem r(B')=(1+x)^8, gdyż jest to sama przekątna i wszystkie jej pola są w jednym skojarzeniu.. mając to stosujemy wzór:

r_n(B)=\sum_{i=0}^{n}(-1)^i(n-i)!r_i(B') dla n=8 i mamy od razu wynik..

problemem jest oczywiście znajomość tego wzoru, który jest i tak szczególnym przypadkiem liczenia n-tego współczynnika wieżomianu dla planszy mając wieżomian dopełniania planszy - dla planszy kwadratowej o boku n i liczby wież też równej n.. ale może dla piszącego taki egzamin jego wyprowadzenie nie byłoby jakoś bardzo trudne, może da się to jakoś sprytnie kombinatorycznie uzasadnić, tego niestety nie wiem.. mnie tu pachnie zasadą włączania-wyłączania, ale słaby z niej zawsze byłem..

jeśli kogoś to interesuje to w ogólności ten wzór wygląda tak: r_k(B)=\frac{1}{(m-k)!}\sum_{i=0}^{k}(-1)^i {n-i \choose k-i}(m-i)!r_i(B') dla planszy n\times m i k wież



w zadaniu drugim tych relacji będzie continuum? mógłby ktoś to pokazać?
Góra
Mężczyzna
PostNapisane: 25 lis 2014, o 18:31 
Użytkownik
Avatar użytkownika

Posty: 3692
Lokalizacja: blisko
Co do zadania 1 uważam, że powinno się podzielić zbiory:

A może inaczej załóżmy że mamy dwa zbiory:

A_{1},A_{2}

wtedy je dzielimy na:

B_{1}= A_{1} \setminus A_{2}, B_{2}=A_{2} \setminus A_{1},  B_{3}=A_{1} \cap A_{2}

zbiory B są parami rozłączne i wystarczy wykonywać na nich sumowanie tylko co da siedem możliwości
podobnie można robić dla większych ilości A.
Góra
Mężczyzna
PostNapisane: 23 gru 2014, o 13:43 
Korepetytor
Avatar użytkownika

Posty: 3960
Lokalizacja: Praga, Dąbrowa Górnicza, Kraków
Zadanie 2. Relacja równoważności na \mathbb{N} to w szczególności element \wp(\mathbb N\times \mathbb N) czyli mamy co najwyżej continuum relacji równoważności na liczbach naturalnych. Wystarczy zatem pokazać, że istnieje co najmniej continuum relacji równoważności, które spełniają wymogi zadania.

Przypomnijmy, że rodzina wszystkich skończonych podzbiorów zbioru liczb naturalnych jest przeliczalna, a zatem rodzina [\mathbb{N}]^\omega wszystkich nieskończonych podzbiorów \mathbb{N} ma moc continuum. Relacja równoważności, to nic innego jak partycja zbioru, a więc wystarczy pokazać, że mamy continuum różnych partycji \mathbb{N} złożonych z dwóch zbiorów. To jednak jest łatwe.

Ustalmy A\in [\mathbb{N}]^\omega i rozważmy relację

n\sim_A m \iff n,m\in A\text{ lub }n,m\in \mathbb{N}\setminus A.

Mamy \sim_A = \sim_B wtedy i tylko wtedy, gdy A = \mathbb{N}\setminus B lub A=B, a więc rodzina relacji

\{\sim_A\colon A\in [\mathbb{N}]^\omega\}

ma istotnie moc continuum.
Góra
Mężczyzna
PostNapisane: 23 gru 2014, o 20:21 
Użytkownik

Posty: 5803
Lokalizacja: Kraków
Cytuj:
3. Na ile sposobów można rozmieścić wież na szachownicy tak, aby żadne dwie nie biły się nawzajem oraz żadna nie stała na głównej przekątnej szachownicy ?

tu chyba chodzi o D_8 ilość permutacji bez punktów stałych, spełnia te sama rekurencję co P_n=n! z D_1=0 \ D_2=1, tj.
D_{n+1} = n(D_{n-1}+D_n)
Góra
Mężczyzna
PostNapisane: 24 gru 2014, o 00:41 
Gość Specjalny
Avatar użytkownika

Posty: 4977
Lokalizacja: Kraków
arek1357 napisał(a):
Co do zadania 1 uważam, że powinno się podzielić zbiory:

A może inaczej załóżmy że mamy dwa zbiory:

A_{1},A_{2}

wtedy je dzielimy na:

B_{1}= A_{1} \setminus A_{2}, B_{2}=A_{2} \setminus A_{1},  B_{3}=A_{1} \cap A_{2}

zbiory B są parami rozłączne i wystarczy wykonywać na nich sumowanie tylko co da siedem możliwości
podobnie można robić dla większych ilości A.

Sek w tym, że różnica nie jest pośród dozwolonych operacji.
Wynik w tym zadaniu to 2^n i można to dość elegancko, bez machania rękami udowodnić.
Góra
Mężczyzna
PostNapisane: 2 lut 2019, o 04:06 
Użytkownik

Posty: 531
Lokalizacja: Rzeszów
Spektralny napisał(a):
Zadanie 2. Wystarczy zatem pokazać, że istnieje co najmniej continuum relacji równoważności, które spełniają wymogi zadania.

Przypomnijmy, że rodzina wszystkich skończonych podzbiorów zbioru liczb naturalnych jest przeliczalna, a zatem rodzina [\mathbb{N}]^\omega wszystkich nieskończonych podzbiorów \mathbb{N} ma moc continuum. Relacja równoważności, to nic innego jak partycja zbioru, a więc wystarczy pokazać, że mamy continuum różnych partycji \mathbb{N} złożonych z dwóch zbiorów. To jednak jest łatwe.

Ustalmy A\in [\mathbb{N}]^\omega i rozważmy relację

n\sim_A m \iff n,m\in A\text{ lub }n,m\in \mathbb{N}\setminus A.

Mamy \sim_A = \sim_B wtedy i tylko wtedy, gdy A = \mathbb{N}\setminus B lub A=B, a więc rodzina relacji

\{\sim_A\colon A\in [\mathbb{N}]^\omega\}

ma istotnie moc continuum.
Tylko, że należałoby zadbać, że taka relacja jest relacją równoważnosci sprawiedliwą, czyli jej obydwie klasy równoważnosci są równoliczne. O to jednak nie zadbałeś.

Spróbuję poprawić rozwiązanie.

Rozważmy rodzinę \mathbb  {X}:

\mathbb {X}=\left\{ A \subset \NN\Bigl| \  \ A \hbox{ jest nieskończony i }\NN \setminus A \hbox { jest nieskończony }\right\}.

Popatrzmy na jej dopełnienie (do P\left( \NN\right), )

\mathbb {X}' =\left\{ A \subset \NN\Bigl| \  \ A\hbox { nie jest nieskończony } \vee \NN \setminus A\hbox { nie jest nieskończony }\right\}=\left\{ A \subset \NN\Bigl| \  \ A \hbox { jest skończony }\right\}  \cup \left\{ A \subset \NN\Bigl| \  \ \NN \setminus A \hbox { jest skończony }\right\}.

Wiemy, że rodzina wszystkich skończonych podzbiorów \NN(oznaczony ją jako \mathbb{A}) jest przeliczalna. Prostym faktem jest, że rodzina druga oznaczmy ją jako \mathbb {B} wszystkich podzbiorów \NN, których dopełnienie do \NN jest skończone, taka rodzina jest z nią równoliczna, a więc przeliczalną. W efekcie \mathbb {X}' jest przeliczalna. Ponieważ \mathbb {X}=\left(  \mathbb{X}'\right) ' =P\left( \NN\right) \setminus \mathbb {X}', ponieważ P\left( \NN\right) jest mocy continuum, to po odjęciu zbioru przeliczalnego otrzymamy zbiór dalej mocy continuum( jest na to odpowiedni lemat, udowadniałem to kiedyś). Czyli rodzina \mathbb {X} jest mocy continuum.

Niech A \in \mathbb {X}. Wtedy A jest nieskończonym podzbiorem \NN, zatem jest równoliczny z \NN, i \NN\setminus A jest nieskończonym podzbiorem \NN, zatem również jest równoliczny z \NN. Oczywiście rodzina dwuzbiorowa \left\{ A, \NN \setminus A\right\} jest rozkladem \NN na dwa zbiory równoliczne. Ponieważ jest rozkładem, to relacja \approx  _{A} na zbiorze liczb naturalnych daną jako:

n \approx   _{A}m\Longleftrightarrow n,m \in A \vee n,m \in  \NN\setminus A.

jest relacją równoważnosci, i zbiorem wszystkich klas równoważności jest właśnie ten rozkład \left\{ A,\NN \setminus A\right\}. Te dwa zbiory rozkładu są równoliczne, zatem jest to relacja równoważnosci sprawiedliwa.

Utworzyliśmy zatem przypisanie zbiorom rodziny \mathbb {X} relacji równoważności sprawiedliwych.

Niestety pojawia się problem, że to przypisanie nie jest różnowartościowe, bo zbiorom A,\NN \setminus A przypisany jest ten sam rozkład \left\{ A,  \NN\setminus A\right\}, a zatem ta samą relacja równoważnosci sprawiedliwa.

Wszystko dobrze szło (tylko pisanie pomału na tablecie), a tu pod koniec problem się wyłonił. Ale tyle na dziś.
Góra
Mężczyzna
PostNapisane: 2 lut 2019, o 11:25 
Użytkownik
Avatar użytkownika

Posty: 3692
Lokalizacja: blisko
Cytuj:
Wynik w tym zadaniu to 2^n i można to dość elegancko, bez machania rękami udowodnić.


I to nieprawda
Góra
Mężczyzna
PostNapisane: 2 lut 2019, o 13:25 
Administrator

Posty: 24725
Lokalizacja: Wrocław
Jakub Gurak napisał(a):
a tu pod koniec problem się wyłonił. Ale tyle na dziś.

Nie jest to istotny problem. Można go bez problemu wyeliminować. Wystarczy np. na początku rozważać rodzinę nieskończonych, konieskończonych podzbiorów \NN, których elementem jest zero. Albo zdefiniować injekcję z P(\NN) w rodzinę sprawiedliwych relacji równoważności wzorem

F(A)=\sim_{\hat{A}}

gdzie \hat{A}=\{2n+1:n\in A\}\cup\{4n:n\in\NN\}.

JK
Góra
Mężczyzna
PostNapisane: 2 lut 2019, o 21:20 
Użytkownik

Posty: 531
Lokalizacja: Rzeszów
Jakub Gurak napisał(a):
a tu pod koniec problem się wyłonił. Ale tyle na dziś.
Jan Kraszewski napisał(a):
Nie jest to istotny problem. Można go bez problemu wyeliminować. Wystarczy np. na początku rozważać rodzinę nieskończonych, konieskończonych podzbiorów \NN, których elementem jest zero.
Co to znaczy :?: Chodzi o rodzinę taką jak ja rozważałem, nieskończonych podzbiorów \NN, których dopełnienie do \NN jest nieskończone, dla których dodatkowo ich elementem jest 0,tak? A jak pokazać, że taka rodzina ma dalej moc continuum :?:
Góra
Mężczyzna
PostNapisane: 2 lut 2019, o 21:33 
Użytkownik

Posty: 16601
Lokalizacja: Bydgoszcz
Można prościej: bierzemy trzy parami rozłączne nieskończone podzbiory A,B,C\subset\NN. takie, że A\cup B\cup C=\NN Każdy podzbiór X\subset A daje partycję (X\cup B, (A\setminus X)\cup C).
Góra
Mężczyzna
PostNapisane: 2 lut 2019, o 21:49 
Administrator

Posty: 24725
Lokalizacja: Wrocław
Jakub Gurak napisał(a):
Co to znaczy :?:

konieskończony = o nieskończonym dopełnieniu

Jakub Gurak napisał(a):
Chodzi o rodzinę taką jak ja rozważałem, nieskończonych podzbiorów \NN, których dopełnienie do \NN jest nieskończone, dla których dodatkowo ich elementem jest 0,tak? A jak pokazać, że taka rodzina ma dalej moc continuum :?:

No przecież poniżej napisałem Ci stosowną injekcję, która - przy okazji - załatwia kwestię tego, że taka rodzina ma moc continuum. Zauważ, że jeśli A\ne B, to \hat{A}\ne\hat{B} oraz że zbiory z daszkami należą do wspomnianej rodziny.

No ale dlatego prościej wziąć od razu tę injekcję.

a4karo napisał(a):
Można prościej: bierzemy trzy parami rozłączne nieskończone podzbiory A,B,C\subset\NN. takie, że A\cup B\cup C=\NN Każdy podzbiór X\subset A daje partycję (X\cup B, (A\setminus X)\cup C).

Zauważ, że podobną rzecz robi moja injekcja. Nasze propozycje są zatem podobne, bo u Ciebie też trzeba trochę rzeczy pouzasadniać.

JK
Góra
Mężczyzna
PostNapisane: 2 lut 2019, o 21:53 
Użytkownik

Posty: 16601
Lokalizacja: Bydgoszcz
Jan Kraszewski napisał(a):

a4karo napisał(a):
Można prościej: bierzemy trzy parami rozłączne nieskończone podzbiory A,B,C\subset\NN. takie, że A\cup B\cup C=\NN Każdy podzbiór X\subset A daje partycję (X\cup B, (A\setminus X)\cup C).

Zauważ, że podobną rzecz robi moja injekcja. Nasze propozycje są zatem podobne, bo u Ciebie też trzeba trochę rzeczy pouzasadniać.

JK


Ale do tego trzeba umieć czytać takie robaczki jak F(A)=\sim_{\hat{A}}. A ja jestem prosty człowiek :D
Góra
Mężczyzna
PostNapisane: 3 lut 2019, o 15:10 
Użytkownik
Avatar użytkownika

Posty: 3692
Lokalizacja: blisko
Według moich spostrzeżeń maksimum tej funkcji będzie gdy:

Każda para zbiorów ma niepuste przecięcie a już każda trójka zbiorów ma puste przecięcie...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 17 ]  Przejdź na stronę 1, 2  Następna strona


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [studia] Politechnika Warszawska  Nostry  162
 [studia] Uniwersytet Łódzki  Nostry  0
 [studia] Uniwersytet Szczeciński  Nostry  0
 [studia] Politechnika Wrocławska  Nostry  18
 [studia] Uniwersytet Rzeszowski  Nostry  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl