• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie z kombinatoryki

VPS Starter Arubacloud
+2 głosów
1,822 wizyt
pytanie zadane 27 stycznia 2017 w Matematyka, fizyka, logika przez Krzysztof Rak Bywalec (2,420 p.)
edycja 29 stycznia 2017 przez Krzysztof Rak
Witam,

trudzę się z rozwiązaniem następującego zadania:

Na ile sposobów można posadzić 8 osób przy 4 nierozróżnialnych okrągłych stolikach, przy założeniu, że przy każdym stoliku siedzi co najmniej jedna osoba i liczy się kto obok kogo siedzi.

Czy należy znaleźć ilość możliwych podziałów zbioru osób na 4 rozłączne niepuste podzbiory uporządkowane, przy czym kolejność w jakiej występują te podzbiory nie ma znaczenia bo stoły są nierozróżnialne?

Jeżeli już mam x osób przy danym stole to mogę je posadzić przy nim na x! sposobów? Tylko jakie znaczenie ma, że stół jest okrągły - czy to będzie (x - 1)! sposobów?

Wiem, pytania być może są głupie i nie logiczne za co przepraszam. :( Liczę na Państwa pomoc w dojściu do rozwiązania.

2 odpowiedzi

+3 głosów
odpowiedź 30 stycznia 2017 przez Benek Szeryf (91,270 p.)
wybrane 31 stycznia 2017 przez Krzysztof Rak
 
Najlepsza

Zgodnie z kalkulatorem 6769 sposobów. Korzystamy z pierwszego wzoru na tej stronie, ponieważ:

(...) i liczy się kto obok kogo siedzi.

oznacza, że mamy do czynienia z permutacją.

+1 głos
odpowiedź 30 stycznia 2017 przez gi90 Nowicjusz (200 p.)
Ciekawe zadanie. Wygląda na trudne. Ale spróbuję pomóc.

Ja najpierw posadziłbym 4 osoby przy stołach, bo przy każdym musi ktoś siedzieć. Na ile sposobów można posadzić tak 4 osoby z 8? Gdyby te stoły były rozróżnialne, to było by 8!/4!. Tutaj stołów nie rozróżniamy, więc mogę podzielić ten wynik przez 4!(bo kolejność w jakiej będę sadzać ludzi nie ma tutaj znaczenia).

Co dalej? Ano teraz każdą z 4 osób mogę posadzić przy dowolnym stole - przy każdym już ktoś siedzi, więc mam wolną rękę. Pierwszą posadzę na 4 sposoby, drugą też. Razem będzie 4^4. Byłoby dobrze, gdyby kolejność nie miała znaczenia. A ma.

Natomiast co to oznacza, że liczy się kto obok kogo siedzi? Czy przy każdym stoliku jest pewna ilość krzeseł na których można posadzić? Czy jeśli posadzę dwie osoby obok siebie to znaczy, że nie mogę już nikogo posadzić między nich?

Ja to widzę tak: mamy 4 stoliki, przy nich siedzą 4 osoby, teraz chcemy umieścić gdzieś jedną z pozostałej czwórki. Do dowolnego stolika, ale jak rozumiem ma znaczenie, czy usiądzie po prawej stronie czy lewej. Ale najpierw posadźmy, w tej chwili nie ma znaczenia, czy siedzi po prawej czy lewej, bo jak posadzę drugą osobę przy stoliku, to nie wpływa to na kolejność(bo niby jak? jest po prawej, czy lewej? to w tej chwili nie gra roli). Dla pierwszej osoby daje to 4 możliwości. Teraz kolejna. W 3 stolikach można posadzić na 1 sposób, ale w jednym na 2(po prawej albo lewej stronie jednego z siedzących przy 2 osobowym stoliku). To 5 sposobów. Kolejną posadzimy na 6 wg. tego rozumowania. Ostatnią na 7.

No ale mogę się mylić albo coś źle zrozumieć. Jaka była dokładna treść zadania?
komentarz 30 stycznia 2017 przez Benek Szeryf (91,270 p.)
edycja 30 stycznia 2017 przez Benek

Gdyby te stoły były rozróżnialne, to było by 8!/4!

Nie do końca. To wyrażenie oznacza liczbę 4-elementowych permutacji, które możesz utworzyć z 8 elementów. A przecież przy każdym stole mogą siedzieć po 2 osoby albo przy dwóch stołach po 3 osoby i przy pozostałych dwóch po 1. Tak więc w tym wzorze ciężko mieszać stoły z liczbą osób.

Natomiast co to oznacza, że liczy się kto obok kogo siedzi?

To oznacza, że ważna jest kolejność w podzbiorach, które są zdefiniowane przez liczbę osób siedzących przy danym stoliku. Tak więc badamy permutacje, a nie kombinacje. Ustalenie tego faktu jest kluczowe przy rozwiązywaniu tego typu zadań.

komentarz 31 stycznia 2017 przez gi90 Nowicjusz (200 p.)

blush kurczę, teraz widzę, że zabieram się do pomocy a tu takie braki w wiedzy, trochę wstyd... oczywiście masz rację, mój błąd.

komentarz 31 stycznia 2017 przez Benek Szeryf (91,270 p.)
Liczą się chęci zrozumienia zagadnienia i podjęcie działania. To jest podstawa i to się bardzo ceni. Nieraz już rozgryzałem zagadnienie od złej strony, orientowałem się gdy trafiałem na rozbieżności w rozumowaniu. Wtedy trzeba dalej przeszukiwać materiały. Ale nie jest źle. Mamy dostęp do Internetu, wyobraź sobie jakby było ciężko biegać do biblioteki za każdym razem i wertować setki książek ;)

Podobne pytania

0 głosów
2 odpowiedzi 187 wizyt
pytanie zadane 30 kwietnia 2020 w Matematyka, fizyka, logika przez damiang19 Nowicjusz (220 p.)
0 głosów
1 odpowiedź 306 wizyt
pytanie zadane 24 lutego 2020 w Matematyka, fizyka, logika przez damiang19 Nowicjusz (220 p.)

92,839 zapytań

141,780 odpowiedzi

320,848 komentarzy

62,171 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...