szukanie zaawansowane
 [ Posty: 7 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 21 sie 2015, o 10:59 
Użytkownik

Posty: 164
1. "Na ile sposobów można utworzyć paczki złożone z jedenastu owoców, mając do dyspozycji cztery ananasy, trzy banany i jedenaście cytryn?"

2. "Na ile sposobów możemy rozmieścić k rozróżnialnych kul w n oznaczonych szufladkach, przy założeniu, że każda szufladka zawiera co najwyżej jedną kulę?"

3. "Ile jest liczb naturalnych mniejszych bądź równych 10^n, w których nie występują obok siebie dwie jednakowe cyfry?"

Nie mam pomysłu na rozwiązanie tych zadań. Pochodzą z książki "Matematyka dyskretna dla informatyków" z działu o prawie dodawania i mnożenia oraz zasadzie włączeń i wyłączeń, więc bardzo bym prosił o podpowiedzi właśnie związane z tymi zagadnieniami.

W 3 zadaniu wydaje mi się, że odpowiedzią jest 8^{n-1} * 9, ale nie jestem pewny.
Góra
Mężczyzna Offline
PostNapisane: 21 sie 2015, o 11:32 
Użytkownik

Posty: 59
Lokalizacja: Polska
1. Jeżeli ułożenie przedmiotów w paczce nie ma znaczenia (czyli {ananas, ananas, cytryna} jest tym samym co {ananas, cytryna, ananas}), to wystarczy wybrać ilość ananasów i bananów, ilość cytryn do dołożenia jest wtedy jednoznaczna. Do tego nie da się tak wybrać liczby ananasów i cytryn, aby nimi samymi przepełnić paczkę, więc nie trzeba się przejmować jakimiś przypadkami. Odpowiedź:
Ukryta treść:    


2. Wybrać szufladki, do których włożymy k kulek (reszta pozostaje pusta), a potem rozmieścić w wybranych szufladkach dokładnie po jednej kulce (permutacja). Odpowiedź:
Ukryta treść:    


3. A tu nie będzie przypadkiem tak, że dla liczby k-cyfrowej na pierwsze miejsce wybieramy jedną z cyfr [1;9], na następną jedną z 10 możliwych, ale nie tą, którą wybraliśmy poprzednio, czyli znów 9 sposobów, itd., aż wybierzemy k cyfr.

Teraz sumując po możliwych długościach tej liczby, czyli od 1 do n dostaniemy prostą sumę: \sum_{k=1}^{n}9^k, co bez wysiłku, ze wzoru na sumę skończonego ciągu geometrycznego, da \frac{9}{8}(9^n-1).

Trzeba jednak zauważyć, że ten wzór działa dla n\geq2, gdyż nie otrzymamy w taki sposób liczby 10^n, która zalicza się do naszego zbioru gdy n\leq1. Czyli dla n=0 odpowiedź wynosi 1, dla n=1 odpowiedź wynosi 10, dla n\geq2 odpowiedź jest taka, jak wyżej.

To zadanie wygląda trochę jak na zasadę włączeń i wyłączeń, ale widać, da się je zrobić przez prawo mnożenia.
Góra
Mężczyzna Offline
PostNapisane: 21 sie 2015, o 17:13 
Użytkownik

Posty: 164
Dzięki za szybką odpowiedź :). Masz jakiś pomysł jak zrobić zadanie 3 za pomocą zasady włączeń i wyłączeń (wspomniałeś, że się da, ponadto kolejność zadań wskazuje na takie rozwiązanie, niestety książka nie zawiera odpowiedzi)?
Góra
Mężczyzna Offline
PostNapisane: 21 sie 2015, o 17:47 
Użytkownik

Posty: 59
Lokalizacja: Polska
Powiedziałem tylko, że wygląda na takie :) Jeżeli da się to zrobić, to również chciałbym zobaczyć rozwiązanie, bo sam dochodziłem do problemów, których nie potrafiłem rozwiązać.
Góra
Mężczyzna Online
PostNapisane: 23 sie 2015, o 18:37 
Użytkownik
Avatar użytkownika

Posty: 3478
Lokalizacja: blisko
W zadaniu pierwszym tak nie będzie, będzie to ilość rozwiązań równania:

x+y+z=11

0 \le x \le 4 - ananasy

0 \le x \le 3 - banany

0 \le x \le 11 - cytryny

No ale w sumie wynik wychodzi dwadzieścia czyli raczej spoko
Góra
Mężczyzna Offline
PostNapisane: 24 sie 2015, o 16:20 
Użytkownik

Posty: 59
Lokalizacja: Polska
arek1357, moje rozwiązanie działa tylko dlatego, że po wybraniu x i y z przedziałów jakie podałeś, wybór z jest jednoznaczny i za każdym razem możliwy. Nie byłoby to prawdą, gdyby nie dało się wypełnić całej paczki cytrynami.
Góra
Mężczyzna Online
PostNapisane: 25 sie 2015, o 09:14 
Użytkownik
Avatar użytkownika

Posty: 3478
Lokalizacja: blisko
Właśnie teraz zauważyłem, że ma to prawo działać...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 7 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zadania testowe - pemutacje, zwracanie :)  Anonymous  2
 3 zadania...  Ciapanek  2
 Zadania z kombinatoryki  neworder  1
 Dwa SKOMPLIKOWANE zadania :)))  domel666  5
 :(:( jak rozwiazywac zadania z kombinatoryki :(:(  kuczek87  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl