Zadania na Studia Doktoranckie z Nauk Matematycznych (cz.1)

Wszystko, co chcielibyście wiedzieć o studiowaniu: co wybrać? jakie są warunki przyjęć? życie studenckie? Zajrzyjcie tutaj!
BraveMind
Użytkownik
Użytkownik
Posty: 106
Rejestracja: 9 maja 2011, o 18:23
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 7 razy
Pomógł: 12 razy

Zadania na Studia Doktoranckie z Nauk Matematycznych (cz.1)

Post autor: BraveMind »

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 \(\displaystyle{ m(A_1,...,A_7}\)) oznacza liczbę zbiorów możliwych do wykonstruowania ze zbiorów \(\displaystyle{ A_1,...,A_7 \subseteq R}\) za pomocą operacji: \(\displaystyle{ \, \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ć \(\displaystyle{ 8}\) wież na szachownicy \(\displaystyle{ 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 \(\displaystyle{ \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 (\(\displaystyle{ 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 \(\displaystyle{ 7 \cdot 7!}\)
macciej91
Użytkownik
Użytkownik
Posty: 105
Rejestracja: 15 mar 2007, o 22:24
Płeć: Mężczyzna
Podziękował: 1 raz
Pomógł: 10 razy

Zadania na Studia Doktoranckie z Nauk Matematycznych (cz.1)

Post autor: macciej91 »

Do zadania 3 może przydać się znajomość tzw. wieżomianów.
adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

Zadania na Studia Doktoranckie z Nauk Matematycznych (cz.1)

Post autor: adambak »

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ę \(\displaystyle{ B}\) wymiarów \(\displaystyle{ 8\times 8}\) bez przekątnej i \(\displaystyle{ 8}\) wież do dyspozycji, aby zgodnie z zasadami rozstawić je na niej.. niech \(\displaystyle{ r(B)}\) to wieżomian dla planszy \(\displaystyle{ B}\), a \(\displaystyle{ r_n(B)}\) to współczynnik przy \(\displaystyle{ x^n}\) w wieżomianie czyli to co nas interesuje - liczba sposobów rozstawienia \(\displaystyle{ n}\) wież na danej planszy zgodnie z zasadami.. liczenie wieżomianu dla \(\displaystyle{ B}\) jest oczywiście straszne, ale trywialne jest policzenie wieżomianu dla dopełnienia czyli \(\displaystyle{ B'}\), bowiem \(\displaystyle{ 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:

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

problemem jest oczywiście znajomość tego wzoru, który jest i tak szczególnym przypadkiem liczenia \(\displaystyle{ n}\)-tego współczynnika wieżomianu dla planszy mając wieżomian dopełniania planszy - dla planszy kwadratowej o boku \(\displaystyle{ n}\) i liczby wież też równej \(\displaystyle{ 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: \(\displaystyle{ 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 \(\displaystyle{ n\times m}\) i \(\displaystyle{ k}\) wież



w zadaniu drugim tych relacji będzie continuum? mógłby ktoś to pokazać?
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Zadania na Studia Doktoranckie z Nauk Matematycznych (cz.1)

Post autor: arek1357 »

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

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

\(\displaystyle{ A_{1},A_{2}}\)

wtedy je dzielimy na:

\(\displaystyle{ 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.
Awatar użytkownika
Spektralny
Użytkownik
Użytkownik
Posty: 3976
Rejestracja: 17 cze 2011, o 21:04
Płeć: Mężczyzna
Lokalizacja: Praga, Katowice, Kraków
Podziękował: 9 razy
Pomógł: 929 razy

Zadania na Studia Doktoranckie z Nauk Matematycznych (cz.1)

Post autor: Spektralny »

Zadanie 2. Relacja równoważności na \(\displaystyle{ \mathbb{N}}\) to w szczególności element \(\displaystyle{ \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 \(\displaystyle{ [\mathbb{N}]^\omega}\) wszystkich nieskończonych podzbiorów \(\displaystyle{ \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 \(\displaystyle{ \mathbb{N}}\) złożonych z dwóch zbiorów. To jednak jest łatwe.

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

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

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

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

ma istotnie moc continuum.
Ostatnio zmieniony 23 gru 2014, o 23:44 przez Spektralny, łącznie zmieniany 1 raz.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11264
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Zadania na Studia Doktoranckie z Nauk Matematycznych (cz.1)

Post autor: mol_ksiazkowy »

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 \(\displaystyle{ D_8}\) ilość permutacji bez punktów stałych, spełnia te sama rekurencję co \(\displaystyle{ P_n=n!}\) z \(\displaystyle{ D_1=0 \ D_2=1}\), tj.
\(\displaystyle{ D_{n+1} = n(D_{n-1}+D_n)}\)
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Zadania na Studia Doktoranckie z Nauk Matematycznych (cz.1)

Post autor: Zordon »

arek1357 pisze:Co do zadania 1 uważam, że powinno się podzielić zbiory:

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

\(\displaystyle{ A_{1},A_{2}}\)

wtedy je dzielimy na:

\(\displaystyle{ 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 \(\displaystyle{ 2^n}\) i można to dość elegancko, bez machania rękami udowodnić.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Zadania na Studia Doktoranckie z Nauk Matematycznych (cz.1)

Post autor: Jakub Gurak »

Spektralny pisze: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 \(\displaystyle{ [\mathbb{N}]^\omega}\) wszystkich nieskończonych podzbiorów \(\displaystyle{ \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 \(\displaystyle{ \mathbb{N}}\) złożonych z dwóch zbiorów. To jednak jest łatwe.

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

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

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

\(\displaystyle{ \{\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ę \(\displaystyle{ \mathbb {X}}\):

\(\displaystyle{ \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 \(\displaystyle{ P\left( \NN\right)}\), )

\(\displaystyle{ \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 \(\displaystyle{ \NN}\)(oznaczony ją jako \(\displaystyle{ \mathbb{A}}\)) jest przeliczalna. Prostym faktem jest, że rodzina druga oznaczmy ją jako \(\displaystyle{ \mathbb {B}}\) wszystkich podzbiorów \(\displaystyle{ \NN,}\) których dopełnienie do \(\displaystyle{ \NN}\) jest skończone, taka rodzina jest z nią równoliczna, a więc przeliczalną. W efekcie \(\displaystyle{ \mathbb {X}'}\) jest przeliczalna. Ponieważ \(\displaystyle{ \mathbb {X}=\left( \mathbb{X}'\right) ' =P\left( \NN\right) \setminus \mathbb {X}',}\) ponieważ \(\displaystyle{ 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 \(\displaystyle{ \mathbb {X}}\) jest mocy continuum.

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

\(\displaystyle{ 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 \(\displaystyle{ \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 \(\displaystyle{ \mathbb {X}}\) relacji równoważności sprawiedliwych.

Niestety pojawia się problem, że to przypisanie nie jest różnowartościowe, bo zbiorom \(\displaystyle{ A,\NN \setminus A}\) przypisany jest ten sam rozkład \(\displaystyle{ \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ś.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Zadania na Studia Doktoranckie z Nauk Matematycznych (cz

Post autor: arek1357 »

Wynik w tym zadaniu to \(\displaystyle{ 2^n}\) i można to dość elegancko, bez machania rękami udowodnić.
I to nieprawda
Jan Kraszewski
Administrator
Administrator
Posty: 34124
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Zadania na Studia Doktoranckie z Nauk Matematycznych (cz.1)

Post autor: Jan Kraszewski »

Jakub Gurak pisze: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 \(\displaystyle{ \NN}\), których elementem jest zero. Albo zdefiniować injekcję z \(\displaystyle{ P(\NN)}\) w rodzinę sprawiedliwych relacji równoważności wzorem

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

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

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Zadania na Studia Doktoranckie z Nauk Matematycznych (cz.1)

Post autor: Jakub Gurak »

Jakub Gurak pisze:a tu pod koniec problem się wyłonił. Ale tyle na dziś.
Jan Kraszewski pisze: 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 \(\displaystyle{ \NN}\), których elementem jest zero.
Co to znaczy Chodzi o rodzinę taką jak ja rozważałem, nieskończonych podzbiorów \(\displaystyle{ \NN}\), których dopełnienie do \(\displaystyle{ \NN}\) jest nieskończone, dla których dodatkowo ich elementem jest \(\displaystyle{ 0,}\)tak? A jak pokazać, że taka rodzina ma dalej moc continuum
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Zadania na Studia Doktoranckie z Nauk Matematycznych (cz

Post autor: a4karo »

Można prościej: bierzemy trzy parami rozłączne nieskończone podzbiory \(\displaystyle{ A,B,C\subset\NN}\). takie, że \(\displaystyle{ A\cup B\cup C=\NN}\) Każdy podzbiór \(\displaystyle{ X\subset A}\) daje partycję \(\displaystyle{ (X\cup B, (A\setminus X)\cup C)}\).
Jan Kraszewski
Administrator
Administrator
Posty: 34124
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Zadania na Studia Doktoranckie z Nauk Matematycznych (cz.1)

Post autor: Jan Kraszewski »

Jakub Gurak pisze:Co to znaczy
konieskończony = o nieskończonym dopełnieniu
Jakub Gurak pisze:Chodzi o rodzinę taką jak ja rozważałem, nieskończonych podzbiorów \(\displaystyle{ \NN}\), których dopełnienie do \(\displaystyle{ \NN}\) jest nieskończone, dla których dodatkowo ich elementem jest \(\displaystyle{ 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 \(\displaystyle{ A\ne B}\), to \(\displaystyle{ \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 pisze:Można prościej: bierzemy trzy parami rozłączne nieskończone podzbiory \(\displaystyle{ A,B,C\subset\NN}\). takie, że \(\displaystyle{ A\cup B\cup C=\NN}\) Każdy podzbiór \(\displaystyle{ X\subset A}\) daje partycję \(\displaystyle{ (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
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Zadania na Studia Doktoranckie z Nauk Matematycznych (cz.1)

Post autor: a4karo »

Jan Kraszewski pisze:
a4karo pisze:Można prościej: bierzemy trzy parami rozłączne nieskończone podzbiory \(\displaystyle{ A,B,C\subset\NN}\). takie, że \(\displaystyle{ A\cup B\cup C=\NN}\) Każdy podzbiór \(\displaystyle{ X\subset A}\) daje partycję \(\displaystyle{ (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 \(\displaystyle{ F(A)=\sim_{\hat{A}}}\). A ja jestem prosty człowiek
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Zadania na Studia Doktoranckie z Nauk Matematycznych (cz

Post autor: arek1357 »

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...
ODPOWIEDZ