Zadania z kombinatoryki

[Angela09]

Cześć,

Czy byłby ktoś tak miły i rozwiązał poniższe zadania:
1)Do dwóch niebieskich autobusów i jednego czerwonego wsiadło w sumie 60 osób. Na ile sposobów te osoby mogły się rozsadzić w tych autobusach, jest dla nas kto z kim jest w autobusie i czy dana osoba jest w niebieskim czy czerwonym autobusie, natomiast oba niebieskie autobusy są dla nas nierozróżnialne. Dodatkowo wiemy, że do każdego z autobusów wsiadło 20 osób.
2)Do koła o promieniu 2 cm wrzucono 17 pkt. Udowodnić, że przynajmniej 2 znajdują się w odległości nie większej niż pierwiastek z 2 cm.
3) Ile jest ciągów binarnych ( złożonych z cyfr 0 i 1) zbudowanych z 20stu jedynek i 5ciu zer, a w których 0 nie występują koło siebie.
4)Na ile sposobów można posadzić n kobiet i n mężczyzn przy okrągłym stole, tak aby żadne z pań nie siedziały obok siebie, a konkretne jedna para kobieta i mężczyzna właśnie siedzieli obok siebie. Interesuje nas tylko kto, koło kogo siedzi, a nie przy którym miejscu przy stole

[FasolkaBernoulliego]

Nie wiem, czy dobrze rozumiem treść, jak tak to w pierwszym by było
\(\displaystyle{ 3 \binom{60}{40} \binom{40}{20}}\),
czyli dzielimy 60 osób na trzy grupy po 20 i z tych grup wybieramy jedną, która wsiądzie do czerwonego autobusu.

W drugim próbowałbym tak zrobić, że rozważam koło trochę większe, o promieniu \(\displaystyle{ (2 + \sqrt{2})}\)cm i pokazywał, że nie może się w nim zmieścić 17 rozłącznych kół o promieniu \(\displaystyle{ \sqrt{2}}\)cm.

W trzecim rozważ ciąg 20 jedynek i zastanów się ile jest miejsc, gdzie mogłyby stać zera, żeby nie stały obok siebie. Następnie liczysz na ile sposobów można wybrać 5 z tych miejsc.

W czwartym bym powiedział, że \(\displaystyle{ ((n-1)!)^2}\), ale może niech się ktoś bardziej zorientowany wypowie.

[arek1357]

Co do drugiego to nie jest dobrze bo rozłącznymi kołami nie podzielisz koła , bo zawsze będą luki a w tych lukach mogą siedzieć punkty i będzie baaaa...

Lepiej to kółko podziel na kwadraty o boku jeden , oczywiście dużo z nich wystaje poza kółko ale to nie ma znaczenia , ale tych kwadracików będzie 16 więc wniosek sam się nasuwa...

Dodano po 4 minutach 28 sekundach:
co do czwartego widać że racja ale to ciut dziwnie brzmi no ale niech tam...

[FasolkaBernoulliego]

Lepiej to kółko podziel na kwadraty o boku jeden , oczywiście dużo z nich wystaje poza kółko ale to nie ma znaczenia , ale tych kwadracików będzie 16 więc wniosek sam się nasuwa...

Zgadza się, źle pomyślałem - dzięki za uwagę. Raczej trzeba by brać koło o promieniu \(\displaystyle{ 2 + \sqrt{2}/2}\) (jego pole jest mniejsze, niż \(\displaystyle{ 7,33 \pi}\)) i pokazać, że nie wejdzie do środka 17 rozłącznych kół o promieniu \(\displaystyle{ \sqrt{2}/2}\) (ich sumaryczne pole to \(\displaystyle{ 8,5 \pi}\)), ale kwadraty o boku jeden może są bardziej eleganckie.

Dodano po 1 godzinie 1 minucie 30 sekundach:
Chociaż w moim rozwiązaniu wniosek jest chyba łatwiejszy do wyciągnięcia, bo z tego podziału kwadratami moim zdaniem nie jest taki oczywisty - może wytłumacz w jaki sposób się sam nasuwa.

Dodano po 1 godzinie 51 minutach 18 sekundach:
No dobra, też jest oczywisty. Tak się zafiksowałem na swoim sposobie myślenia, że nie ogarnąłem. A u mnie musiałbym brać w miejsce \(\displaystyle{ \sqrt{2}/2}\) wszędzie \(\displaystyle{ \sqrt{2}/2 + \epsilon}\)

[Angela09]

Czy odp do zadania 4 nie dotyczy tylko sytuacji, w której żadna para nie jest rozrożnialna?

[FasolkaBernoulliego]

Przyznam, że nie czuję dobrze tego zadania, ale myślałem w ten sposób: skoro nie interesuje nas konkretne miejsce, to usadzam sobie tę ustaloną parę (powiedzmy świeżo upieczone małżeństwo) gdziekolwiek (kobietę sadzam z prawej strony, bo podobno tak wypada ). W ten sposób automatycznie ustawia się n-1 miejsc dla kobiet i n-1 miejsc dla mężczyzn. No i teraz te miejsca już mają znaczenie, bo określają położenie względem tej ustalonej pary. Dalej po prostu rozważam na ile sposobów mogę rozsadzić towarzystwo na tych miejscach, które mają znaczenie. Zauważ, że zamiana miejsc spowoduje, że dla kogoś zmienią się sąsiedzi, bo Państwa Młodych przesadzać przecież nie będę.

[arek1357]

masz rację para młoda musi być na najważniejszym miejscu...

[Angela09]

ok, dziękuję!:)

[kerajs]

Ad 1.

Nie wiem, czy dobrze rozumiem treść, jak tak to w pierwszym by było
\(\displaystyle{ 3 \binom{60}{40} \binom{40}{20}}\),
czyli dzielimy 60 osób na trzy grupy po 20 i z tych grup wybieramy jedną, która wsiądzie do czerwonego autobusu.

Sądzę że to raczej: \(\displaystyle{ {60 \choose 20} \cdot \frac{ {40 \choose 20} }{2} }\)

Ad 2.

Chociaż w moim rozwiązaniu wniosek jest chyba łatwiejszy do wyciągnięcia, bo z tego podziału kwadratami moim zdaniem nie jest taki oczywisty - może wytłumacz w jaki sposób się sam nasuwa.
Dodano po 1 godzinie 51 minutach 18 sekundach:
No dobra, też jest oczywisty.
(...)
ale kwadraty o boku jeden może są bardziej eleganckie.

Trzeba cisnąć Arka o wytłumaczenie, gdyż wcale nie ma 16, a jedynie 9 kwadratów. (ale 9 kwadratów wystarczy jeśli .....)

Ad 4.

W czwartym bym powiedział, że \(\displaystyle{ ((n-1)!)^2}\)

. Przy założeniu iż przy stole jest dokładnie 2n miejsc, to liczyłbym tak: Sadzam wyróżnioną niewiastę, jej partnera, pozostałe panie i panów, i dzielę przez ilość równoważnych usadzeń przy okrągłym stole: \(\displaystyle{ \frac{2n \cdot 2 \cdot (n-1)! \cdot (n-1)!}{2n} }\)

[FasolkaBernoulliego]

Sądzę że to raczej: \(\displaystyle{ {60 \choose 20} \cdot \frac{ {40 \choose 20} }{2} }\)

Hm, chyba racja.

Trzeba cisnąć Arka o wytłumaczenie, gdyż wcale nie ma 16, a jedynie 9 kwadratów. (ale 9 kwadratów wystarczy jeśli .....)

Ale on robi takie pokrycie kwadratami, a nie wpisuje je do środka, więc czemu 9 a nie 16?

Przy założeniu iż przy stole jest dokładnie 2n miejsc, to liczyłbym tak: Sadzam wyróżnioną niewiastę, jej partnera, pozostałe panie i panów, i dzielę przez ilość równoważnych usadzeń przy okrągłym stole: \(\displaystyle{ \frac{2n \cdot 2 \cdot (n-1)! \cdot (n-1)!}{2n} }\)

Te 2n to, jak rozumiem, przesunięcia wszystkich o k miejsc w prawo, k = 1, ..., 2n. A co z symetriami?

[arek1357]

dokładnie ja robię pokrycie kwadratami i jest ich 16...

Dodano po 1 minucie 17 sekundach:
O symetriach w ostatnim nie było mowy w końcu na poczatku musimy się określić jaka grupa działa na daną figurę...

Dodano po 3 minutach 49 sekundach:

Trzeba cisnąć Arka o wytłumaczenie, gdyż wcale nie ma 16, a jedynie 9 kwadratów.

Będzie 16 bo niepełne tez biore pod uwagę ale mi nie zależy czy są pełne czy niepełne, wystarczy mi , ze jest ich 16...

[FasolkaBernoulliego]

O symetriach w ostatnim nie było mowy w końcu na poczatku musimy się określić jaka grupa działa na daną figurę...

Interesuje nas tylko kto, koło kogo siedzi

Ja zrozumiałem to w ten sposób, że rozróżniamy zbiór sąsiadów, bez ustalonej kolejności (czyli rybka mi czy siedzę obok Aśki i Maryśki, czy obok Maryśki i Aśki).

[Angela09]

Sądzę że to raczej: \(\displaystyle{ {60 \choose 20} \cdot \frac{ {40 \choose 20} }{2} }\)

Dlaczego tak?

[FasolkaBernoulliego]

Licznik odpowiada liczbie podziałów na trzy grupy, ale w sposób uporządkowany (czyli pierwsza grupa, druga grupa i trzecia grupa), czyli tak jak byśmy wsadzali już do kolejnych autobusów. Ale możemy dwie grupy z niebieskich autobusów zamienić miejscami i wg zadania mamy tych dwóch sytuacji nie rozróżniać. Rozwiązując samemu pomyślałem z jakiegoś dziwnego powodu, że to jest liczba podziałów na trzy grupy bez ustalonego porządku tych grup i dlatego pomnożyłem przez 3, żeby wyróżnić ten jeden autobus.

Żeby zobaczyć, że nie miałem racji, wystarczy rozważyć analogiczne zadanie z 3 osobami.

\(\displaystyle{ {3 \choose 1} {2 \choose 1} = 6}\),

a tak naprawdę zadanie sprowadza się do wybrania kto jedzie w czerwonym autobusie.

[Angela09]

ok, rozumiem, dziękuję:)