Rękawiczki - model drzewkowy

[Majeskas]

Ja nie wiem tylko które rozumowanie moje czy Twoje jest bardziej prawidłowe, które opisuje lepiej rzeczywistość, przydałby się sędzia sprawiedliwy, który oceniłby oba rozumowania.

Trudno oceniać, które rozumowanie jest "bardziej prawidłowe", skoro dotyczą dwóch różnych zadań. Co do Twojego problemu (jeśli już dobrze go rozumiem), to ja bym go rozwiązał tak:
Skoro chcemy, żeby \(\displaystyle{ k}\) dwójek składało się z par, to musimy wybrać te \(\displaystyle{ k}\) par: \(\displaystyle{ {15\choose k}}\). Został zbiór \(\displaystyle{ 30-2k}\) rękawiczek, który chcemy podzielić na \(\displaystyle{ 15-k}\) podzbiorów dwuelementowych w taki sposób, żeby w każdej dwójce były rękawiczki nie do pary. Powiedzmy, że ten zbiór to \(\displaystyle{ \left\{ p_1,l_1,p_2,l_2,\ldots,p_{15-k},l_{15-k}\right\}}\). Arbitralnie ustawmy prawe rękawiczki w ciąg, np. \(\displaystyle{ p_1,p_2,\ldots,p_{15-k}}\). Pod spodem możemy dopisać ciąg lewych rękawiczek i wówczas kolumny będą wyznaczać podzbiory dwuelementowe. Skoro rękawiczki mają być zawsze nie do pary, to interesują nas takie permutacje zbioru \(\displaystyle{ \left\{ 1,2,\ldots,15-k\right\}}\), które nie mają punktów stałych, czyli nieporządki. Każdej takiej permutacji odpowiada wzajemnie jednoznacznie poszukiwany podział. Z gotowego wzoru na liczbę nieporządków mamy: \(\displaystyle{ (15-k)!\sum_{m=2}^{15-k}\frac{(-1)^m}{m!}}\). Stąd poszukiwane prawdopodobieństwo wynosi:

\(\displaystyle{ \frac{2^{15}\cdot15!\cdot{15\choose k}\cdot(15-k)!\sum_{m=2}^{15-k}\frac{(-1)^m}{m!}}{30!}=\frac{2^{15}\cdot(15!)^2\sum_{m=2}^{15-k}\frac{(-1)^m}{m!}}{30!\cdot k!}}\)



Zabranie głosu przez kogoś kompetentnego byłoby mile widziane i nikt nikogo nie wygryzł. Do Piaska101 nic nie mam. Po prostu jeśli ktoś daje mi takie cenne rady jak: "często losując po jednej zapominacie, że kolejność jest ważna", albo prezentuje, jak działa forumowa wyszukiwarka (notabene skorzystałem z niej, zanim założyłem temat; mimo wielu wątków w związku z tym zadaniem nikt nie próbował rozwiązywać go drzewem), to mam wrażenie, że chyba nawet za bardzo nie przeczytał mojego posta, więc może zwyczajnie szkoda jego czasu. Tyle.

[arek1357]

Coś mi się nie zgadza w twoim wzorze weźmy trzy pary rękawic.

Obliczmy ilość nieporządków:

\(\displaystyle{ (3-0)! \sum_{m=2}^{3} \frac{(-1)^m}{m!}=6( \frac{1}{2}- \frac{1}{6})=3-1=2}\)

a powinno być:

\(\displaystyle{ a_{6}^0=8}\) - u mnie nazywa się to pokoje czyste.


pokoje brudne:

\(\displaystyle{ a_{6}^1=6}\) - pokoje w których jest tylko jedna para dobra,

\(\displaystyle{ a_{6}^3=1}\) - pokój w którym wszystkie pary są dobre

razem \(\displaystyle{ =7}\)

wszystkich pokoi jest:

\(\displaystyle{ \frac{6!}{3! \cdot 2^3}=15}\)

stąd pokoi czystych jest:

\(\displaystyle{ 15-7=8}\)

a nie dwa

[Majeskas]

Coś mi się nie zgadza w twoim wzorze weźmy trzy pary rękawic.

Obliczmy ilość nieporządków:

\(\displaystyle{ (3-0)! \sum_{m=2}^{3} \frac{(-1)^m}{m!}=6( \frac{1}{2}- \frac{1}{6})=3-1=2}\)

Nie wiem, o czym wg Ciebie ma informować ta liczba. Liczba nieporządków jest w moim rozwiązaniu potrzebna do ustalania tych podziałów na dwójki, w których żadna rękawiczka nie trafia na swoją parę. To, co wyznaczyłeś, to po prostu liczba nieporządków permutacji zbioru trzyelementowego, których jest niewątpliwie \(\displaystyle{ 2}\): \(\displaystyle{ 231,312}\).

[arek1357]

Ile jest według Twoich obliczeń pokoi czystych dla \(\displaystyle{ n=3, 2n=6}\)

i dla \(\displaystyle{ n=4, 2n=8}\)

I pokaż jak to obliczasz.

[Majeskas]

Prosiłbym trochę bardziej po ludzku. Pytasz, jak obliczę, ile jest takich podziałów zbioru sześciu/ośmiu rękawiczek na dwuelementowe podzbiory, że w każdym z nich rękawiczki są nie do pary?

[arek1357]

Tak pokaż obliczenie.

[Majeskas]

To po prostu liczba nieporządków trzyelementowych i czteroelementowych. Jak już wiadomo, są dwa nieporządki dla trójki elementów. Napisałem we wcześniejszym poście, jakie to permutacje. Każdej z nich w naturalny sposób odpowiadają rozbicia: \(\displaystyle{ \left\{p_1,l_2|p_2,l_3|p_3,l_1 \right\},\left\{p_1,l_3|p_2,l_1|p_3,l_2 \right\}}\). I to są wszystkie takie podziały.

Dla \(\displaystyle{ n=4}\) mamy \(\displaystyle{ 9}\) nieporządków. Nie chce mi się ich wypisywać, ale gdyby ktoś miał na to ochotę, to widać po tym, co wyżej, w jaki sposób po wypisaniu permutacji wypisać rozbicia.

[arek1357]

Ale zaraz zaraz dla n=3 mamy trzy pary rękawic:

\(\displaystyle{ (p_{1},r_{1})(p_{2},c_{2})(c_{1},r_{2})}\) - tu masz nieporządek jeden a takich będzie 8 a nie dwa

możliwości jest \(\displaystyle{ 15= \frac{6!}{2^33!}}\) - nieporządków jest 8 a takich z parami z jednej pary np:

\(\displaystyle{ (p_{1},p_{2})(r_{2},c_{2})(c_{1},r_{1})}\) - i takich masz 7

itd...

[Majeskas]

Czy mógłbyś, trzymając się mojej (chyba dość naturalnej) notacji, podać mi przykład jakiegoś innego podziału niż te dwa podane przeze mnie, który spełniałby warunek "w każdej dwójce rękawiczki są nie do pary"?

[arek1357]

\(\displaystyle{ (p_{1},r_{1})(p_{2},c_{2})(c_{1},r_{2})}\) - pierwszy pokój, pokój czysty

\(\displaystyle{ (p_{1},r_{2})(p_{2},c_{2})(c_{1},r_{1})}\) - drugi pokój, pokój czysty

\(\displaystyle{ (p_{1},r_{1})(p_{2},c_{1})(c_{2},r_{2})}\) - trzeci pokój , pokój czysty

dla trzech par rękawic

masz tu trzy nieporządki już a jest ich 8.

[Majeskas]

Prosiłem o trzymanie się mojej notacji, bo Twoja trochę mnie zbija z tropu. Ja to rozumiem tak, że \(\displaystyle{ p_1}\) jest do pary z \(\displaystyle{ r_1}\), \(\displaystyle{ p_2}\) z \(\displaystyle{ r_2}\), a \(\displaystyle{ c_1}\) z \(\displaystyle{ c_2}\). Jeśli tak, to żaden z zaproponowanych przez Ciebie podziałów nie spełnia pożądanego warunku. Jeśli nie, to nie wiem, jak rozumieć te oznaczenia (i dlatego prosiłem o trzymanie się moich).

-- 13 stycznia 2016, 00:43 --

Dobra. Nie wiem, dlaczego założyłem, że w każdej parze rękawiczka prawa ma się znaleźć z lewą. Moje rozwiązanie odpowiada takiej sytuacji. Sorry. Zaraz pomyślę nad modyfikacją.

-- 13 stycznia 2016, 01:11 --

Ja bym użył po prostu zasady włączeń i wyłączeń. Dla zbioru sześciu rękawiczek policzymy sytuacje, w których pewne dwie rękawiczki będą w parze:

\(\displaystyle{ 3\cdot\frac{4!}{2\cdot2^2}-3+1=7}\), czyli tego, o co chodzi, będzie \(\displaystyle{ \frac{6!}{3!\cdot2^3}-7=8}\)

Dla \(\displaystyle{ n=4}\):

\(\displaystyle{ \frac{8!}{4!\cdot2^4}-4\cdot\frac{6!}{3!\cdot2^3}+{4\choose2}\cdot\frac{4!}{2\cdot2^2}-4+1=60}\)

Teraz można przejść do sytuacji ogólnej: jeśli \(\displaystyle{ k}\) rękawiczek się sparowało, to trzeba podzielić zbiór \(\displaystyle{ 30-2k}\) rękawiczek na te nie sparowane. Takich możliwości będzie:

\(\displaystyle{ \sum_{m=0}^{15-k}{15-k\choose m}\cdot\frac{(-1)^m(30-2k-2m)!}{(15-k-m)!\cdot2^{15-k-m}}}\)

Ostatecznie poszukiwane prawdopodobieństwo wynosi

\(\displaystyle{ \frac{2^{15}\cdot(15!)^2\sum_{m=0}^{15-k}\frac{(-1)^m(30-2k-2m)!(15-k)!}{m!((15-k-m)!)^2\cdot2^{15-k-m}}}{30!\cdot k!(15-k)!}}\)

[arek1357]

No teraz doszliśmy do konsensusu z drobną korektą rękawiczki z pary u mnie to:

\(\displaystyle{ \left( p_{1},p_{2}\right) ,\left(r_{1},r_{2}\right),...}\)

I teraz widzę że Twoje obliczenia zgadzają się z moimi bo dla n=3 np, wychodzi ok. dla n=4 to samo...

Tylko ja napisałem wzory rekurencyjne, Ty masz jawne ale i tak powtarzam spotkaliśmy się w punkcie wyjścia czyli jest ok!.

Pozostaje tylko problem otwarty która sytuacja losowa bardziej odpowiada rzeczywistości, bo wydaje mi się że moje losowanie odpowiada wybieraniu \(\displaystyle{ 2n}\) rękawic na raz czyli \(\displaystyle{ n}\) par.

Ale jak widać dobrze, że ten problem został poruszony, sprawdź teraz o ile będą się różnić wyniki
dla obu procesów myślowych!

W sumie ciekawy i pouczający przykład nadający się na zajęcia dla studentów różne widzenie tej samej rzeczywistości. Po drugie sam model parowania dość ciekawe zadanie kombinatoryczne.

[a4karo]

A czy te pary rękawiczek się różnią? Bo jeżeli nie, to de facto interesują nas tylko rękawiczki prawe i lewe. To znacznie upraszcza zadanie

[arek1357]

Jak masz rękawiczki z pary to jest ok.

Masz po prostu n par rękawiczek czyli sztuk 2n i łączysz je przypadkowo potem i badasz ile jest
różnych połączeń w pary, a my badaliśmy ile w danym połączeniu (pokoju) jest par z pary oraz par tak zwanych "złych" czyli niesparowanych!
Dla przykładu wyżej wypisywałem i liczyłem dla trzech i czterech par oraz dla dwóch par!
przykład uznałem za dydaktyczny i ciekawy.

Te cztery pary to po prostu jeden rodzaj drugi trzeci i czwarty rękawic
Trzy albo cztery pary rękawic, które mieszamy a potem z powrotem parujemy przypadkowo i badamy ilość
możliwości sparowań.


Nawet dzięki a4karo nasunęło mi się jeszcze jedno zadanie do tego naszego projektu.

Zliczać ile jest np absolutnych nieporządków czyli rękawic nie dość, że nie z jednej pary ale wszystkie pary tylko i wyłącznie typu:

(prawa prawa) lub (lewa lewa) czyli mówiąc moim językiem nieporządek absolutny.

Po drugie wyszła korelacja między moim równaniem rekurencyjnym a kolegi Majeskasa jawnym.
Co też dobrze wróży.

[Majeskas]

Pozostaje tylko problem otwarty która sytuacja losowa bardziej odpowiada rzeczywistości, bo wydaje mi się że moje losowanie odpowiada wybieraniu \(\displaystyle{ 2n}\) rękawic na raz czyli \(\displaystyle{ n}\) par.

Ale jak widać dobrze, że ten problem został poruszony, sprawdź teraz o ile będą się różnić wyniki
dla obu procesów myślowych!

W sumie ciekawy i pouczający przykład nadający się na zajęcia dla studentów różne widzenie tej samej rzeczywistości. Po drugie sam model parowania dość ciekawe zadanie kombinatoryczne.

Nadal nie rozumiem, co z czym chcesz porównywać, ale chyba już nie zrozumiem. A że wyszło ciekawe zadanie kombinatoryczne, to się zgadzam

A czy te pary rękawiczek się różnią? Bo jeżeli nie, to de facto interesują nas tylko rękawiczki prawe i lewe. To znacznie upraszcza zadanie

Oczywiście, standardowo wybieramy model najbliższy rzeczywistości, tj. rozróżnialne rękawiczki. Gdyby rozróżniać tylko rękawiczki prawe i lewe, to oba zadania się dosyć trywializują. Wówczas mamy w pierwszym \(\displaystyle{ \Omega=\left\{ (x,y):\ 0\le x,y\le4,\,x+y=4\right\}}\), gdzie \(\displaystyle{ x}\) oznacza liczbę rękawiczek prawych, \(\displaystyle{ y}\) lewych. Wtedy \(\displaystyle{ |\Omega|=5}\), a szukane prawdopodobieństwo wybrania czterech rękawiczek nie do pary wynosi \(\displaystyle{ \tfrac25}\), bo jedyne możliwości to cztery prawe albo cztery lewe.
Drugie zadanie jest tylko trochę bardziej skomplikowane. Tym razem możemy przyjąć \(\displaystyle{ \Omega=\left\{ (x,y,z):\ 0\le x,y,z\le30,\,x+y+z=30\right\}}\), gdzie \(\displaystyle{ x}\) oznacza liczbę dwójek składających się z dwóch prawych, \(\displaystyle{ y}\) z dwóch lewych i \(\displaystyle{ z}\) z dwóch różnych. Wówczas \(\displaystyle{ |\Omega|={32\choose2}}\). Zdarzenie \(\displaystyle{ A}\): \(\displaystyle{ k}\) dwójek składa się z rękawiczki prawej i lewej składa się po prostu ze wszystkich trójek \(\displaystyle{ (x,y,k)}\), których jest tyle, ile rozwiązań równania \(\displaystyle{ x+y=30-k}\) (w liczbach naturalnych). Stąd \(\displaystyle{ |A|=31-k}\) i \(\displaystyle{ \PP(A)=\tfrac{31-k}{496}}\)

-- 13 stycznia 2016, 23:09 --

Nawet dzięki a4karo nasunęło mi się jeszcze jedno zadanie do tego naszego projektu.

Zliczać ile jest np absolutnych nieporządków czyli rękawic nie dość, że nie z jednej pary ale wszystkie pary tylko i wyłącznie typu:

(prawa prawa) lub (lewa lewa) czyli mówiąc moim językiem nieporządek absolutny.

Tym razem mamy podzielić zbiór \(\displaystyle{ 30-2k}\) rękawic na \(\displaystyle{ 15-k}\) dwójek z samymi rękawicami prawymi i tyle samo z samymi lewymi. Widać więc, że zadanie ma rozwiązanie tylko dla nieparzystych \(\displaystyle{ k}\). Teraz trzeba po prostu zliczyć niezależnie wszystkie takie podziały dla rękawic prawych i lewych. W obu wypadkach wynik będzie oczywiście taki sam:\(\displaystyle{ \frac{(15-k)!}{2^{(15-k)/2}\cdot((15-k)/2)!}}\).

Ostatecznie szukane prawdopodobieństwo wynosi \(\displaystyle{ \frac{2^k\cdot(15!)^2\cdot(15-k)!}{30!(((15-k)/2)!)^2k!}}\).