Zadania z kombinatoryki
Zadania z kombinatoryki
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
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
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Zadania z kombinatoryki
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.
\(\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
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Zadania z kombinatoryki
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...
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...
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Zadania z kombinatoryki
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}\)
Re: Zadania z kombinatoryki
Czy odp do zadania 4 nie dotyczy tylko sytuacji, w której żadna para nie jest rozrożnialna?
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Zadania z kombinatoryki
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ę.
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Zadania z kombinatoryki
Ad 1.
Ad 2.
Ad 4.
Sądzę że to raczej: \(\displaystyle{ {60 \choose 20} \cdot \frac{ {40 \choose 20} }{2} }\)FasolkaBernoulliego pisze: ↑28 sty 2020, o 21:30 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.
Ad 2.
Trzeba cisnąć Arka o wytłumaczenie, gdyż wcale nie ma 16, a jedynie 9 kwadratów. (ale 9 kwadratów wystarczy jeśli .....)FasolkaBernoulliego pisze: ↑30 sty 2020, o 13:58 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.
Ad 4.
. 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 pisze: ↑28 sty 2020, o 21:30 W czwartym bym powiedział, że \(\displaystyle{ ((n-1)!)^2}\)
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Zadania z kombinatoryki
Hm, chyba racja.
Ale on robi takie pokrycie kwadratami, a nie wpisuje je do środka, więc czemu 9 a nie 16?
Te 2n to, jak rozumiem, przesunięcia wszystkich o k miejsc w prawo, k = 1, ..., 2n. A co z symetriami?kerajs pisze: ↑31 sty 2020, o 00:20Przy 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} }\)
- arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Zadania z kombinatoryki
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:
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:
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...Trzeba cisnąć Arka o wytłumaczenie, gdyż wcale nie ma 16, a jedynie 9 kwadratów.
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Zadania z kombinatoryki
O symetriach w ostatnim nie było mowy w końcu na poczatku musimy się określić jaka grupa działa na daną figurę...
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).Interesuje nas tylko kto, koło kogo siedzi
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Zadania z kombinatoryki
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.
Ż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.
Ostatnio zmieniony 31 sty 2020, o 17:30 przez FasolkaBernoulliego, łącznie zmieniany 1 raz.