Zadanie kombinatoryczne
-
- Użytkownik
- Posty: 36
- Rejestracja: 22 kwie 2022, o 16:34
- Płeć: Kobieta
- wiek: 20
- Podziękował: 12 razy
Zadanie kombinatoryczne
1) Ile jest liczb całkowitych między 3000 i 9999, których suma cyfr wynosi dokładnie 12?
2) Ile spośród powyższych liczb ma wszystkie cyfry różne od 0 i 1?
2) Ile spośród powyższych liczb ma wszystkie cyfry różne od 0 i 1?
-
- Administrator
- Posty: 34335
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5204 razy
-
- Użytkownik
- Posty: 36
- Rejestracja: 22 kwie 2022, o 16:34
- Płeć: Kobieta
- wiek: 20
- Podziękował: 12 razy
Re: Zadanie kombinatoryczne
Pomyślałam, aby użyć \(\displaystyle{ x_1+x_2+x_3+x_4=12}\) i ilość rozwiązań wtedy jest równa \(\displaystyle{ {15 \choose 3} }\), ale nie mam pomysłu jak uwzględnić zadany przedział liczbowy.
Edit: Czy w momencie w którym wiem, że \(\displaystyle{ 3 \le x_1 \le 9}\), mogę kolejno podstawiać cyfry i obliczać ilości rozwiązań dla równania powyżej i je zsumować?
Dodano po 56 minutach 42 sekundach:
Czy raczej \(\displaystyle{ 3 \le x_1 \le 9}\) i \(\displaystyle{ 0 \le x_i \le 9}\) oraz \(\displaystyle{ x_1=y_1+3}\) oraz \(\displaystyle{ x_i=y_i}\), więc \(\displaystyle{ y_1+y_2+y_3+y_4=9}\) i ilosc rozwiązań wynosi \(\displaystyle{ {12 \choose 3}}\) ?
Dodano po 12 minutach 57 sekundach:
A w podpunkcie 2) będzie \(\displaystyle{ x_i \ge 2}\), więc \(\displaystyle{ x_1+x_2+x_3+x_4=4}\), ilość rozwiązań równa \(\displaystyle{ {4+4-1 \choose 4-1}= {7 \choose 3} }\) ?
-
- Administrator
- Posty: 34335
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5204 razy
Re: Zadanie kombinatoryczne
Ja tam policzyłem na palcach i wyszło mi
1) \(\displaystyle{ 210}\)
2) \(\displaystyle{ 20.}\)
JK
1) \(\displaystyle{ 210}\)
2) \(\displaystyle{ 20.}\)
JK
-
- Użytkownik
- Posty: 36
- Rejestracja: 22 kwie 2022, o 16:34
- Płeć: Kobieta
- wiek: 20
- Podziękował: 12 razy
Re: Zadanie kombinatoryczne
Kurcze, to mi żadnym sposobem zliczania tak nie wyszło, nie potrafię do tego dojść.Jan Kraszewski pisze: ↑15 maja 2022, o 23:59 Ja tam policzyłem na palcach i wyszło mi
1) \(\displaystyle{ 210}\)
2) \(\displaystyle{ 20.}\)
JK
-
- Administrator
- Posty: 34335
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5204 razy
Re: Zadanie kombinatoryczne
W 2) te liczby to:
\(\displaystyle{ 6222,\\
5322, 5232, 5223, 3522, 3252, 3225,\\
4422, 4242, 4224\\
4332, 4323, 4233, 3432, 3423, 3342, 3324, 3243, 3234,\\
3333.}\)
Uważam, że to wszystkie.
JK
\(\displaystyle{ 6222,\\
5322, 5232, 5223, 3522, 3252, 3225,\\
4422, 4242, 4224\\
4332, 4323, 4233, 3432, 3423, 3342, 3324, 3243, 3234,\\
3333.}\)
Uważam, że to wszystkie.
JK
- Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Zadanie kombinatoryczne
1) Najpierw wybieramy pierwszą cyfrę tej liczby (bo mogą to być \(\displaystyle{ 3,4,5,6,7,8,9}\)), pozostają nam trzy cyfry, które - gdy pierwszą cyfrą jest \(\displaystyle{ i}\) - mają dać sumę \(\displaystyle{ 12-i}\) (bardzo pomaga nam to, że \(\displaystyle{ i\ge 3}\), w przeciwnym razie chcielibyśmy uniknąć pseudo-cyfry równej np. \(\displaystyle{ 10}\)). Na ile sposobów można przedstawić wówczas (gdy pierwszą cyfrą jest \(\displaystyle{ i}\)) \(\displaystyle{ 12-i}\) w postaci sumy trzech nieujemnych składników (uwzględniając kolejność)? To dość znane, na \(\displaystyle{ {14-i \choose 2}}\) (ogólniej przy sumie \(\displaystyle{ k}\) całkowitych nieujemnych składników równej \(\displaystyle{ n}\) będzie to \(\displaystyle{ {n+k-1\choose k-1}}\)).
Zatem odpowiedź to \(\displaystyle{ \sum_{i=3}^{9}{14-i\choose 2}=\sum_{j=5}^{11}{j\choose 2}\\=\sum_{j=2}^{11}{j\choose 2}-\sum_{j=2}^{4}{j\choose 2}\\={12\choose 3}-{5\choose 3}=220-10=210.}\)
Użyłem tutaj kolejnej znanej tożsamości \(\displaystyle{ \sum_{k=m}^{n}{k\choose m}={n+1\choose m+1}}\), której dowód można przeprowadzić np. tak:
mamy encyklopedię o \(\displaystyle{ n+1}\) stronach i chcemy wybrać \(\displaystyle{ m+1}\) stron, które przeczytamy. Jeśli ostatnia wybrana przez nas strona będzie miała numer \(\displaystyle{ k+1}\), gdzie \(\displaystyle{ m\le k\le n}\), to znaczy, że spośród poprzedzających ją \(\displaystyle{ k}\) stron musimy wybrać do przeczytania dokładnie \(\displaystyle{ m}\), co możemy uczynić na \(\displaystyle{ {k\choose m}}\) sposobów.
2) Modyfikacja polega na tym, że pozostałe trzy cyfry muszą być równe co najmniej \(\displaystyle{ 2}\). Zatem jeśli tymi cyframi są \(\displaystyle{ x_1, x_2, x_3}\), to istnieją takie całkowite nieujemne \(\displaystyle{ y_1, y_2, y_3}\), że
\(\displaystyle{ x_1=y_1+2, \ x_2=y_2+2, \ x_3=y_3+2}\). Wówczas, gdy pierwszą cyfrą jest \(\displaystyle{ i}\), ma zajśc
\(\displaystyle{ 6-i=y_1+y_2+y_3}\), a takich rozkładów, uwzględniając kolejnośc, mamy \(\displaystyle{ \sum_{i=3}^{9}{8-i\choose 2}=\sum_{i=3}^6{8-i\choose 2}={5\choose 2}+{4\choose 2}+{3\choose 2}+{2\choose 2}=10+6+3+1=20}\).
Zatem odpowiedź to \(\displaystyle{ \sum_{i=3}^{9}{14-i\choose 2}=\sum_{j=5}^{11}{j\choose 2}\\=\sum_{j=2}^{11}{j\choose 2}-\sum_{j=2}^{4}{j\choose 2}\\={12\choose 3}-{5\choose 3}=220-10=210.}\)
Użyłem tutaj kolejnej znanej tożsamości \(\displaystyle{ \sum_{k=m}^{n}{k\choose m}={n+1\choose m+1}}\), której dowód można przeprowadzić np. tak:
mamy encyklopedię o \(\displaystyle{ n+1}\) stronach i chcemy wybrać \(\displaystyle{ m+1}\) stron, które przeczytamy. Jeśli ostatnia wybrana przez nas strona będzie miała numer \(\displaystyle{ k+1}\), gdzie \(\displaystyle{ m\le k\le n}\), to znaczy, że spośród poprzedzających ją \(\displaystyle{ k}\) stron musimy wybrać do przeczytania dokładnie \(\displaystyle{ m}\), co możemy uczynić na \(\displaystyle{ {k\choose m}}\) sposobów.
2) Modyfikacja polega na tym, że pozostałe trzy cyfry muszą być równe co najmniej \(\displaystyle{ 2}\). Zatem jeśli tymi cyframi są \(\displaystyle{ x_1, x_2, x_3}\), to istnieją takie całkowite nieujemne \(\displaystyle{ y_1, y_2, y_3}\), że
\(\displaystyle{ x_1=y_1+2, \ x_2=y_2+2, \ x_3=y_3+2}\). Wówczas, gdy pierwszą cyfrą jest \(\displaystyle{ i}\), ma zajśc
\(\displaystyle{ 6-i=y_1+y_2+y_3}\), a takich rozkładów, uwzględniając kolejnośc, mamy \(\displaystyle{ \sum_{i=3}^{9}{8-i\choose 2}=\sum_{i=3}^6{8-i\choose 2}={5\choose 2}+{4\choose 2}+{3\choose 2}+{2\choose 2}=10+6+3+1=20}\).
-
- Użytkownik
- Posty: 36
- Rejestracja: 22 kwie 2022, o 16:34
- Płeć: Kobieta
- wiek: 20
- Podziękował: 12 razy
Re: Zadanie kombinatoryczne
Dziękuję bardzo za wytłumaczenie!
Ostatnio zmieniony 16 maja 2022, o 19:46 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Po co cytujesz cały post, który jest tuż wyżej?
Powód: Po co cytujesz cały post, który jest tuż wyżej?