szukanie zaawansowane
 [ Posty: 15 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 4 gru 2014, o 23:01 
Użytkownik

Posty: 34
Lokalizacja: Elbląg
Ile jest calkowitoliczbowych nieujemnych rozwiazan rownania :
a + b + c + d = 12
gdzie a,b,c,d \le 5.

Proszę o pomoc.
Przy podobnych zadaniach tworzyłem zazwyczaj zmienne pomocnicze po czym stosowałem kombinację ale z tym nie wiem co mam zrobić
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 4 gru 2014, o 23:26 
Użytkownik
Avatar użytkownika

Posty: 6326
Jakie sumy spełniające założenie wynoszą 12?
Składające się z liczb:
5,5,2,0
5,5,1,1
5.4,3,0
5,4,3,1
5,3,3,1
5,3,2,2
4,4,4,0
4,4,3,1
4,4,2,2
4,3,3,2
3,3,3,3
Teraz wystarczy dla każdego układu policzyć ilość permutacji i je zsumować otrzymując liczbę rozwiązań.
Góra
Mężczyzna Offline
PostNapisane: 4 gru 2014, o 23:35 
Użytkownik

Posty: 34
Lokalizacja: Elbląg
Dziękuje! Czy znasz może jakiś szybszy sposób niż wypisywanie?
Góra
Mężczyzna Offline
PostNapisane: 4 gru 2014, o 23:37 
Użytkownik
Avatar użytkownika

Posty: 6326
Przypuszczam że to najszybszy sposób.
Góra
Mężczyzna Offline
PostNapisane: 4 gru 2014, o 23:48 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
kerajs, źle Ci się wydaje :)
hasło kluczowe to "Funkcje generujące"
dla a możemy wybrać wartości od 0 do 5, tak samo dla każdej pozostałej stąd mamy:
\left(z^0+z^1+z^2+z^3+z^4+z^5\right)^4
potęgi reprezentują tu wartości a potęga 4 dlatego że dla każdej zmiennej mamy ten sam wybór, po przemnożeniu wszystkiego (co można zrobić np. wolframem: http://www.wolframalpha.com/input/?i=%2 ... 5E5%29%5E4) patrzymy na współczynnik przy z^{12} bo taka suma nas interesowała (w wolframie patrz na "expanded form"), wychodzi 125 ale przy zadaniach tego typu akceptowalną odpowiedzią jest taki zapis:
\left(z^0+z^1+z^2+z^3+z^4+z^5\right)^4 \quad \left[z^{12}\right]
to znaczy dokładnie tyle że chodzi nam o ten współczynnik w kwadratowych nawiasach z podanego wyrażenia
Góra
Mężczyzna Offline
PostNapisane: 5 gru 2014, o 00:28 
Użytkownik
Avatar użytkownika

Posty: 6326
Moim zdaniem sposób który podałeś nie jest szybszy wtym zadaniu. Pisemne mnożenie i porządkowanie wielomianu jest czasochłonne, a samo szukanie współczynników przy z ^{12} sprowadza się do znalezienia permutacji między odpowiednimi potęgami czyli do wypisania układów wykładników .




Ps. W piątym układzie zamiast 5,3,3,1 ma być 5,3,2,1.
Góra
Mężczyzna Offline
PostNapisane: 5 gru 2014, o 00:48 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
dobrze, to rozwiąż to samo ale ze zmienioną treścią:
x_1 + x_2 + \ldots + x_{10} = 31\\
x_3 \in \{2,3,5\}\\
x_5, x_6 > 4\\
x_8 \le 2
powodzenia w wypisywaniu, a funkcja generująca działa dokładnie tak samo :)
Góra
Mężczyzna Offline
PostNapisane: 5 gru 2014, o 11:59 
Użytkownik
Avatar użytkownika

Posty: 6326
@Gouranga,

Jak się często w takich dyskusjach zdarza problem znika jeśli ustali sie co dla oponentów jest przedmiotem sporu. Ja , i sądząc po Twoim pierwszym poscie także Ty, ustosunkowywałem sie do szybkości rozwiązywania tego konkretnego zadania.
Góra
Mężczyzna Offline
PostNapisane: 5 gru 2014, o 12:10 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
kerajs, no właśnie ja podałem sposób na ten typ zadań a nie na konkretny przykład
ale to normalne zważywszy na fakt, że jestem informatykiem, informatyk nigdy nie napisze programu Destroy Bagdad, napisze program Destroy City i poda Bagdad jako konkretny przykład
Góra
Mężczyzna Offline
PostNapisane: 5 gru 2014, o 13:50 
Użytkownik

Posty: 34
Lokalizacja: Elbląg
A czy poprawnym będzie rozwiązanie {15 \choose 3}  - 4 *  {10 \choose 3} ?
Góra
Mężczyzna Offline
PostNapisane: 5 gru 2014, o 17:35 
Użytkownik
Avatar użytkownika

Posty: 6326
Odpowiedź już padła : 125

{15 \choose 3}  - 4 *  {10 \choose 3}=455-4 \cdot 120=-15
Góra
Mężczyzna Offline
PostNapisane: 6 gru 2014, o 00:08 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
mdcbnmw2000 napisał(a):
A czy poprawnym będzie rozwiązanie {15 \choose 3}  - 4 *  {10 \choose 3} ?

Mało brakowało, abyś napisał najprostsze rozwiązanie w tym temacie.

\binom{15}3-4\cdot\binom93+\binom42\cdot\binom33=455-336+6=125.

Rozwiązanie Kerajsa jest dość pracochłonne, a rozwiązanie Gourangi chyba niepełne (nie dopatrzyłem się metody znajdowania odpowiedniego wyrazu wielomianu).
Góra
Mężczyzna Offline
PostNapisane: 6 gru 2014, o 02:49 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
norwimaj, odpowiedni współczynnik znajdujemy rozwijając wyrażenie i porządkując je ale nie trzeba tego robić, wystarczy podanie odpowiedzi który współczynnik z jakiej funkcji
Góra
Mężczyzna Offline
PostNapisane: 6 gru 2014, o 16:20 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Gouranga napisał(a):
wystarczy podanie odpowiedzi który współczynnik z jakiej funkcji

A dlaczego nie wystarczy po prostu odpowiedź, że chodzi o liczbę całkowitoliczbowych, nieujemnych rozwiązań równania a + b + c + d = 12, gdzie a,b,c,d \le 5 ?
Góra
Mężczyzna Offline
PostNapisane: 6 gru 2014, o 19:11 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
norwimaj, bo nie wiemy ile ich jest natomiast wiemy jaki jest współczynnik przy z^{12} w tym wielomianie (wiemy = jesteśmy w stanie to obliczyć), nie trzeba przemnażać tego do konkretnej liczby ręcznie ale można się posłużyć odpowiednim do tego programem.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 15 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 ilość rozwiązań równania  prymas  3
 Ilosc rozwiazan rownania  Papkin  5
 Ilosc rozwiazan rownania - zadanie 2  kamil.jack  1
 Ilość rozwiązań równania - zadanie 4  piotrek20008  1
 ilość rozwiązań równania - zadanie 7  likent10  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl