Komentarze do notki: Mikołajki - zadanie matematyczne

@kaczazupaNo nie wiem, kto wciskał kit. Znajomi podali właściwy wynik i o to chodziło. Niechęć do rozwiązań numerycznych lub Monte Carlo jest niezrozumiała.

A nawet jeden przysiadł na dłużej i napisał następujący wzór:

P(.)=f(n)/n!
Gdzie f(1)=0; f(2)=1; f(n)=(n-1)*(f(n-1)+f(n-2))

Proszę sprawdzić, wzór działa!


PS. ((n-1)/n)^(n-1) zapewne zbiega do 1/e, ale baaaardzo powoli.

@kaczazupa"po ulicach chodzą sobie nierozpoznani geniusze"

a dlaczego miałoby to być niemożliwe?

@kaczazupa
"Oczywiście powinno być ((n-1)/n)^n"
- zbiega do 1/e tak samo baaardzo wolno, tylko od drugiej strony ;-)

"Numeryczne to nie rozwiązania" - zależy od definicji "rozwiązania", ale w sensie matematycznym pewnie racja.

"Bez przynajmniej refleksji nad tym" - pełna zgoda, konieczna refleksja wzmocniona przez świadomość ograniczeń i doświadczenie oparte na własnych błędach.

Odnośnie rozwiązań monte carlo proszę zobaczyć ten komentarz. Jak widać pomysł, żeby próbować rozgryźć problem w ten sposób nie jest rzadki.

@kaczazupa"W drugim - podzielić klasę i losy na pół."

A jeżeli liczba uczniów jest nieparzysta, np. 29?

@blazioFajne zadanko i fajna dyskusja.

Co do potrzebnej formuły, to nie trzba miec papierowych książek na półkach. Trzeba jednak znać "magiczne słowa", by wygooglać. Formułka wyżej pochodzi ze strony Wolframa (klik na nią tam prowadzi). Te "primy" przy sumach odnoszą się do krotności sumy - jeden prim: suma zwykła, dwa primy: suma podwójna, etc.

W tym zadanku rozważamy numer N(k), który dostaje liczba "k" (k-ty uczeń) przy permutacji (przetasowaniu), k=1,..., n=30. Interesuje nas prawdopodobieństwo zdarzenia

{N(1)≠1}∩{N(2)≠2}∩⋅⋅⋅∩{N(n)≠n}

Oznaczamy A_k={N(k)=k}. Wtedy szukane p-o wynosi

1-P(A₁ ∪⋅⋅⋅∪ A_n),

i tu stosujemy wzorek z Wolframa (tzn., nie jest on jego, tylko tam podany, np.), otrzymując formułe podaną wyżej przez eternala - częściową suma szeregu dla e^-1.

Ponieważ ów szereg ma zmienne znaki, zbiega bardzo szybko (błąd przy obcinaniu nie przekracza pierwszego wyrazu odrzucanego, czyli 1/(n+1)!. Oscylacja wokół granicy sprawia, że nie tylko "sama małość" ma znaczenie, ale także kasowanie się owych małości, co owe zmniejsza.

Z drugiej strony, ów wzór [(n-1)/n]ⁿ odpowiada losowaniu ze zwracaniem. To znaczy, że uczeń losuje, patrzy co wylosował, i zwraca los z powrotem do czapki - niech się inni też pomęczą.

Ten ciąg maleje do 1/e bardzo wolno. Łatwo to zobaczyć, biorąc odwrotność (bo gdy granica jest różna od zera, to odwrotność zbiega circa tak samo szybko, z dokładnościa do stałej). Innymi słowy,
e - [(n+1)/n]ⁿ > 1/(2n)

@tichyDzięki za piękne podsumowanie dyskusji i wyjaśnienie rozwiązania.

Link do wolphram otworzył przede mną kolejną komnatę internetu - dzięki. Ale i tak pójdę do biblioteki po Wilinkina i Borowkowa i zobaczę, co to za jedni ;-)

@tichy 2Jeżeli dyskusja się podobała, to na wszelki wypadek zwracam uwagę na to, że część dyskusji jest również pod następną notką.

http://blazio.salon24.pl/256609,mikolajki-zadanie-2

@blazio"Ale i tak pójdę do biblioteki po Wilinkina i Borowkowa..."

Przy okazji pójścia do biblioteki (lub antykwariatu) polecam: William Feller "Wstęp do rach pdbństwa", tom I i II.

Ongiś powszechnie używany jako podręcznik aż tak, że ową teorię pdbństwa niektórzy złośliwie (acz dobrodusznie i baaardzo trafnie, z uwagi na znaczenie słówka "feler" po polsku) zwali "fellerologią".

Pochodzi on z circa połowy XX w, i w ramach pędu za nowszym i lepszym, prostszym i zwiężlejszym (bo kto ma czas i głowę i checi!), został już wyparty przez bardziej spolegliwe podręczniki. To znaczy, takie, które odpowiadają powszechnemu podejściu "czy to będzie na egzaminie".

Tom pierwszy jest strawny dla początkujących (acz koniecznie dojrzałych) matematycznie (Analiza pierwsza wystarcza, a nawet niekonieczna, gdy ktoś chce dowody pomijać).

Tom drugi jest bardziej zaawansowany, wymaga sporego podłoża matematycznego, przede wszystkim - solidnej analizy matematycznej, ale wciąż w ramach kursów uniwersyteckich.

Dodam jeszcze, że polskie tłumaczenie jest świetne. Rzekłbym - lepsze od oryginału, dzięki dodaniu wielu informacji i wyjaśnień przez tłumaczy. Jezeli znasz moją opinię o tłumaczeniach żródeł obcojęzycznych. W skrócie: są fatalne, począwszy od Szekspira, poprzez Camusa czy nawet "Anię z Zielonego Wzgórza, aż do tekstów matematycznych. O, informatyczne - to wiadomo, włos się jeży.

książkiW sprawie książek.
Właśnie miałem chwilę czasu i wyruszyłem na poszukiwania Wilenkina.

„Kombinatorykę” Wilenkina zidentyfikowałem w lokalnej czytelni naukowej.

Rzeczywiście, tak jak twierdził rekontra, mamy do czynienia z ogólnym zadaniem o przesunięciu.

Nie wiem, czy wszystkie książki od kombinatoryki tak mają, ale tytuły podrozdziałów w tej książce pozostają w naszej mikołajkowej poetyce: „Przesądni kolarze”, „Sekretny zamek”, „Mistrzostwa piłkarskie, krąg taneczny. „Nasz” rozdział zaczyna się od „Lwy i tygrysy” i przez „Rycerzy króla Artura” przechodzi do podrozdziału „Dziewczyna spieszy na spotkanie”, który na przykładzie innej sytuacji opisuje nasz problem.

Przy okazji dowiedziałem się, że opisana powyżej jako f(n) funkcja „odkryta” przez mojego znajomego nazywa się „pseudosilnią”.

@tichy Dzięki za kolejny trop (Feller).