szukanie zaawansowane
 [ Posty: 9 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 4 wrz 2015, o 22:59 
Użytkownik

Posty: 4
Lokalizacja: Poznań
Mój pierwszy post na forum, więc się przywitam - cześć :)
Mam problem z tym zadaniem. Ma ono zostać rozwiązane zasadą włączeń i wyłączeń, ale nie jestem w stanie wymyślić, jak można je pod nią przystosować.

Pewna pani ma 80 sukienek. Każdego dnia w roku (365 dni) ubiera jedną z nich. Na ile sposobów może ubierać się przez rok, zakładając, że musi ubrać każdą sukienkę co najmniej raz.

Z góry dziękuje za wszelką pomoc :)
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 5 wrz 2015, o 02:20 
Użytkownik

Posty: 59
Lokalizacja: Polska
Cześć!
Musisz zastosować zasadę włączeń i wyłączeń w zależności od ilości sukienek, których dama NIE założyła. Czyli zbiory A_i to takie ustawienia, że nie w żaden z dni nie jest zakładana i-ta sukienka, a S_i, czyli części wspólne zbiorów, ustalasz wybierając i sukienek, które nie zostały założone oraz zliczając możliwości dopasowania 80-i sukienek do 365 dni. W ogólności jest to problem zliczania suriekcji (w tym wypadku ze zbioru 365 elementowego na 80 elementowy)
Góra
Mężczyzna Offline
PostNapisane: 5 wrz 2015, o 17:11 
Użytkownik

Posty: 4
Lokalizacja: Poznań
Mógłbyś to jakoś szerzej rozwinąć? Na chwilę obecną dalej nie jestem w stanie zrozumieć o co chodzi.
Góra
Mężczyzna Offline
PostNapisane: 5 wrz 2015, o 18:02 
Użytkownik

Posty: 59
Lokalizacja: Polska
Masz dwa zbiory, jeden z nich to zbiór dni w roku, a drugi to zbiór sukienek. Będziemy przyporządkowywać każdemu z dni jedną sukienkę, czyli zrobimy funkcję ze zbioru dni do zbioru sukienek. Każda sukienka ma być użyta co najmniej raz, czyli funkcje, których szukamy, muszą być suriekcjami (czyli funkcjami "na"). Do zliczania suriekcji można użyć zasady włączeń i wyłączeń tak jak tutaj (dwa ostatnie posty to poprawne odpowiedzi).
Góra
Mężczyzna Offline
PostNapisane: 5 wrz 2015, o 18:07 
Użytkownik

Posty: 1427
Lokalizacja: Warszawa
W takich sytuacjach liczy się "od tyłu". Od wszystkich możliwości ubrania się odejmiemy te "złe". Co to znaczy "złe"? Skoro dobre to takie, w których każda sukienka wystąpi co najmniej raz, złe to takie, w których pewna sukienka nie wystąpi w ogóle. Ale nie wiadomo która. To może być którakolwiek z tych 80. Oznaczmy

A_i - zbiór tych wszystkich możliwości ubrania się, w których i-ta sukienka nie wystąpi.

W takim razie szukamy mocy zbioru A_1\cup A_2\cup\ldots\cup A_{80}. Zbiory występujące w tej sumie nie są parami rozłączne, np. A_{13}\cap A_{43} oznacza zbiór tych ubiorów, w których nie wystąpią suknie o numerach 13 i 43. Dlatego potrzebujemy teraz zasady włączeń i wyłączeń, która pozwala właśnie obliczać moc sumy zbiorów, które nie są parami rozłączne.

Spróbuj po tych wskazówkach, a w razie kłopotów pytaj dalej.
Góra
Mężczyzna Offline
PostNapisane: 11 wrz 2015, o 13:51 
Użytkownik

Posty: 4
Lokalizacja: Poznań
Ok, zrozumiałem czemu musi być zasada włączeń i wyłączeń, oraz, że najlepiej to zrobić jako suriekcje. Ten podrzucony temat mi sporo pomógł, dzięki :)

Doszedłem do momentu następującego:
Wszystkich możliwości założenia sukienek jest 80^{365}
Problem jest taki, że trzeba wyłączyć te sytuacje, w których funkcja suriekcją nie jest.
Doszedłem do czegoś takiego: \sum_{i=0}^{365} (-1)^{i} {365 \choose i}(365-i) ^{80}
Nie wiem jednak, czy jest to prawidłowe (znalazłem wzór na suriekcje i wrzuciłem liczby do niego :d), a już tym bardziej nie mam pojęcia, jak to wyliczyć, poza żmudnym liczeniem (w teorii mógłbym napisać do tego program, coby mi pozwoliło wzór zapamiętać... ale to później :D).
Góra
Mężczyzna Offline
PostNapisane: 11 wrz 2015, o 14:16 
Użytkownik

Posty: 1427
Lokalizacja: Warszawa
Błąd polega na tym, że wstawiłeś te liczby odwrotnie. Gorsza sprawa, że to pokazuje, że nie wiesz, skąd się wziął ten wzór. Byłoby znacznie pożyteczniej, gdybyś spróbował rozwiązać to zadanie od podstaw, stosując tylko wzór włączeń i wyłączeń i wskazówki, które Ci podałem. Właśnie dlatego nie rzuciłem Ci wzoru na liczbę suriekcji. Ja nie widzę sensu w uczeniu się matematyki w taki sposób, że "wezmę jakiś wzór, bo ktoś mówił, że jest dobry, i może zadziała". Można rozwiązać to zadanie, nie znając słowa "suriekcja". Wystarczy tylko trochę pomyśleć.

Jeśli chodzi o sam rezultat, który już obaj znamy, to lepiej się tego nie da zapisać i właśnie taki wynik jest oczekiwany. Można sobie napisać program, który to obliczy (albo choćby skorzystać z Wolframa Alphy), ale to już inna rzecz.
Góra
Mężczyzna Offline
PostNapisane: 11 wrz 2015, o 15:06 
Użytkownik

Posty: 4
Lokalizacja: Poznań
\sum_{i=0}^{80} (-1)^{i} {80 \choose i}(80-i) ^{365}

Cóż, nie mogę Ci przyznać racji.
Z tego co rozumiem - iteracji będzie 80, ponieważ mamy 80 sytuacji, w których któraś sukienka nie zostanie wybrana.

Tym samym wynik całościowy to: 80^{365} - \sum_{i=0}^{80} (-1)^{i} {80 \choose i}(80-i) ^{365}
Góra
Mężczyzna Offline
PostNapisane: 11 wrz 2015, o 19:17 
Użytkownik

Posty: 1427
Lokalizacja: Warszawa
Nie wiem, w której kwestii nie możesz mi przyznać racji, ale nie jest mi to niezbędne do szczęścia. Nie wiem też, co dla Ciebie znaczy słowo "iteracja", bo chyba co innego niż dla mnie, dlatego nie jestem w stanie zweryfikować tego, co rozumiesz.

Wynik całościowy to: \sum_{i=0}^{80}(-1)^i{80\choose i}(80-i)^{365}

Chcemy obliczyć liczbę suriekcji ze zbioru 365-elementowego w zbiór 80-elementowy, dlatego - zgodnie ze wzorem - jest właśnie tak. Podejście, które Ci proponowałem, polegało na odjęciu od liczby wszystkich funkcji liczbę tych funkcji, które nie są suriekcjami. Tak więc skrzyżowałeś sposób rozumowania, który próbowałem podsunąć, z gotowym wzorem na to, co trzeba.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 9 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [Zasada podwójnego przeliczania] Uzasadnienie mocy zbioru  pelas_91  1
 Zasada włączeń i wyłączeń - zadanie 5  Fray  5
 zasada szufladkowa Dirichleta - zadanie 28  pg2464  3
 KOmbinatoryka zasada szufladkowa dirichleta  Wisienkaaa  4
 Zasada włączania i wyłączania z kartami (Na ile sposobów...)  kanarkowa  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl