Matematyka.pl

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!}\)

Do zadania 3 może przydać się znajomość tzw. wieżomianów.

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ć?

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.

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.

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)}\)

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

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

Wynik w tym zadaniu to \(\displaystyle{ 2^n}\) i można to dość elegancko, bez machania rękami udowodnić.

I to nieprawda

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

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)}\).

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

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

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