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

Wszystkie kombinacje miejsc z wyłączeniem miejsc początkowych

Object Storage Arubacloud
0 głosów
536 wizyt
pytanie zadane 22 stycznia 2017 w Matematyka, fizyka, logika przez VirtualMember Pasjonat (15,790 p.)

Witam, czy mógłby ktoś mi wytłumaczyć jak zrobić takie zadanie?

Cztery osoby siedzą na ławce. W pewnym momencie wstają z ławki, zaś po jakimś czasie siadają ponownie. Na ile sposobów mogą usiąść tak, aby żadna z nich nie usiadła na miejscu poprzednio zajmowanym.

Coś ktoś pisał o zasadzie włączeń i wyłączeń, ale nie ma na to logicznego prostszego sposobu?

komentarz 22 stycznia 2017 przez Czort Nałogowiec (32,500 p.)
Trochę dziwne to zadanie, jakby ułożyła je jakaś niedojda matematyczna. To nie mogą siąść tylko na miejscach początkowych, czy w ogóle nie mogą siąść na miejscach, które już wcześniej zajmowali?
komentarz 22 stycznia 2017 przez VirtualMember Pasjonat (15,790 p.)
na początkowym, bo raz siadają
komentarz 24 stycznia 2017 przez gi90 Nowicjusz (200 p.)
Zadanie jest czytelne. Mamy ustalone miejsca na ławce(zakładam, że więcej jak 4 osoby nie usiądą), które zajmują cztery osoby. Potem wstają, ale po jakimś czasie znowu siadają. Teraz chodzi o to, że żaden nie może usiąść na miejscu, na którym siedział wcześniej.

mvxxx Jeśli chodzi o zasadą włączeń i wyłączeń, to chyba nie ma tutaj zastosowania(jeśli jest, chętnie zobaczę).

Spróbuj w ten sposób: narysuj sobie schemat, ławkę na której umieszczasz w 4 miejscach 4 osoby - oznacz sobie np. tak: A, B, C, D. Potem zobacz, na ile sposobów możesz ponownie posadzić pierwszą z nich(może ona zająć 3 miejsca, to wiadomo). Jak posadzisz osobę A, na miejscu, które poprzednio zajmowała osoba B, to na ile sposobów możesz posadzić teraz osobę B? A pozostałe? Jak zrobisz, to spróbuj może z 5 osobami?

1 odpowiedź

0 głosów
odpowiedź 2 lutego 2017 przez Benek Szeryf (91,210 p.)

Coś ktoś pisał o zasadzie włączeń i wyłączeń, ale nie ma na to logicznego prostszego sposobu?

Według mnie jest, choć z zasady włączeń i wyłączeń też się podobno da. Najprostszy sposób polega na wypisaniu sobie wszystkich możliwości, ponieważ n=4 to nie jest jakiś skomplikowany przypadek. Spróbujmy jednak choć częściowo wyprowadzić wzór, zakładając że początkowo osoby siedzą w porządku ABCD:

A B C D # początkowy porządek
-------
A . . . # ten przypadek odrzucamy,
.       # bo A jest na 1. pozycji
.
.
A . . .


B A D C # przesuwamy A w prawo i wypisujemy
C A D B # wszystkie dopuszczalne kombinacje
D A B C
.
.
. . . .

B D A C # przesuwamy A w prawo i wypisujemy
C D A B # wszystkie dopuszczalne kombinacje
D C A B
.
.
. . . .

B C D A # przesuwamy A na ostatnią pozycję,
C D B A # wypisujemy wszystkie dopuszczalne
D C B A # kombinacje
.
.
. . . .

Gdybyśmy nie ograniczali w żaden sposób porządku, to wszystkich możliwych przypadków byłoby 4!  = 24. Z powyższej tabelki widzimy, że A na pierwszej pozycji odejmuje nam aż 6 przypadków, czyli rozważając TYLKO pierwszą warstwę mielibyśmy:

3 x 3!
(n-1) x (n-1)!

sposobów. Jednak widzimy, że w każdym bloku nie mamy po 6 = 3! kombinacji, tylko po 3, co daje nam całościowy wynik równy 9. Jak sobie z tym poradzić? Oznaczmy liczbę ciągów dla danego n przez S(n). Musimy policzyć S(4). Pierwszy poziom już rozważyliśmy, mamy więc:

S(4) = (4-1)*lvl2

Sednem sprawy jest wytypowanie liczby lvl2, odpowiadającej za drugi poziom.

  1. Załóżmy, że A zajmuje pozycję B. Wtedy pozostałe trzy elementy mogą zająć trzy pozycje. Nie będzie to jednak permutacja z 3 elementów (3!), bo część elementów zajęłaby poprzednie miejsca. Na przykład D ponownie zajęłoby tę samą pozycję. Jest to więc ponownie problem taki sam jak w przypadku pierwszego poziomu, przy czym rozważamy już poziom drugi. Przyczynek do lvl2 będzie więc zawierał S(3) = S(n-1).
  2. Drugi przypadek to taki, że A zajmuje pozycję inną niż B, a to oznacza że B nie może zająć pozycji zajętej przez A oraz dodatkowo swojej pierwotnej B. Liczba elementów (wolnych parametrów) zmniejsza się więc o 2, toteż musimy policzyć S(2) = S(n-2).

Ponieważ mamy dwa przypadki, to lvl2 będzie składał się z sumy:

S(n) = (n-1)[S(n-1) + S(n-2)]

I jest to wzór rekurencyjny. W rzeczywistości funkcję S(n) nazywamy nieporządkiem i oznaczamy symbolem !n. Więcej można przeczytać na Wikipedii.

Podobne pytania

0 głosów
3 odpowiedzi 361 wizyt
pytanie zadane 20 maja 2019 w Matematyka, fizyka, logika przez belkowski656 Nowicjusz (220 p.)
+1 głos
3 odpowiedzi 4,713 wizyt
pytanie zadane 15 lipca 2015 w C i C++ przez Maurycy0621 Bywalec (2,140 p.)
0 głosów
1 odpowiedź 256 wizyt

92,757 zapytań

141,679 odpowiedzi

320,429 komentarzy

62,101 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!

...