szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 kwi 2018, o 11:19 
Użytkownik

Posty: 13
Lokalizacja: Warszawa
Mam problem z takim zadankiem i prosiłbym o sprawdzenie mojego toku myślenia.

Ile jest rozwiązań w liczbach całkowitych równania postaci: x_{1} + x_{2} + x_{3} + x_{4} = 12, jeśli:

a) x_{1}  \ge 0, i = 1,2,3,4
b) x_{1}  > 0, i = 1,2,3,4

Rozw. (Zadanie robiliśmy na ćwiczeniach, ale nie wszystko zrozumiałem).
a) Po przemyśleniach: Kolejność liczb jest nie istotna, ponieważ z odpowiednich aksjomatów wiemy, że dodawanie jest przemienne. Liczby mogą się powtarzać, np. może wystąpić sytuacja x_{1} = 10 , x_{2}  = 1, x_{3} = 1, x_{4} = 0. W takim razie słusznym pomysłem wydaje się użycie wzorku na kombinacje z powtórzeniami. Liczba k-elementowych kombinacji z powtórzeniami zbioru n-elementowego wygląda następująco:

{n+k-1 \choose k}

Wynik na ćwiczeniach otrzymaliśmy taki:

{4+12- 1 \choose 12} =  {15 \choose 12}

A moim zdaniem powinno być tak:

{4+13- 1 \choose 12} =  {16 \choose 13}

Spieszę z wyjaśnieniem. n=4, ponieważ naszym n-elementowym zbiorem będą tutaj niewiadome, z których "tworzymy" sumę równą 12. Jednak, czy tutaj k=13 ? Myślałem, że liczba k-elementowych kombinacji będzie właśnie 13, ponieważ uwzględniamy liczby z przedziału \{0, ... , 12 \}. Jeśli jestem w błędzie to najwidoczniej nadal mam problemy ze zrozumieniem definicji kombinacji z powtórzeniami i prosiłbym o sprostowanie.

Przykład b) chyba jest dla mnie zrozumiały, względem wyniku uzyskanego na ćwiczeniach.. Uwzględniam "skrajny" przypadek, czyli np. x_{1} = 9 , x_{2}  = 1, x_{3} = 1, x_{4} = 1. Dlaczego tak? Każda liczba musi być większa od zera, dlatego minimalną wartością dla każdej z trzech liczb będzie "1". Aby suma była równa 12, musimy dodać 9. W tym przypadku otrzymalibyśmy nadal n=4 i k=8, bo mamy liczby z przedziału \{1,....,8\}. Zatem otrzymujemy:

{4 + 8 - 1 \choose 8} =  {11 \choose 8}
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 2 kwi 2018, o 18:49 
Użytkownik
Avatar użytkownika

Posty: 237
Lokalizacja: Płock
Najlepiej zadania tego typu rozrysować sobie graficznie - "metodą kropek i kresek".

Na przykład tak: |\cdot \cdot \cdot | \cdot \cdot \cdot \cdot | \cdot \cdot | \cdot \cdot \cdot|.

W powyższym schemacie kreski tworzą nam cztery przegródki z kropkami, których ilości odpowiadają wartościom niewiadomych x_1, x_2, x_3, x_4. Wszystkich kropek mamy 12. Łatwo zatem zauważyć, że ten schemat przedstawia czwórkę liczb (x_1,x_2,x_3,x_4)=(3,4,2,3). Aby wyznaczyć liczbę wszystkich rozwiązań w liczbach naturalnych, należy obliczyć na ile sposobów możemy te kreski poprzestawiać. Załóżmy, że manipulujemy tylko trzema kreskami (te skrajne zostawiamy w spokoju). Generalnie kropek i kresek, które przestawiamy, jest razem 12+3=15 (zajmują one jakby 15 miejsc). Spośród tych 15 miejsc wybieramy 3, na których mają stać te kreski. Zatem możliwości wyboru jest {15 \choose 3}, co jest oczywiście równe {15 \choose 12}, czyli tyle ile uzyskaliście na ćwiczeniach.

Moim zdaniem w taki sposób jest lepiej podchodzić do takich problemów niż zapamiętywać na siłę różne wzory. Mam nadzieję, że w miarę jasno to wytłumaczyłem. Gdyby coś tu było nie do końca zrozumiałe, to pytaj dalej :).

Analogicznie możesz wyznaczyć wzór na liczbę rozwiązań równania x_1+x_2+x_3+...+x_k=n w liczbach naturalnych (nieujemnych). Nietrudno się przekonać, że rozwiązań tych jest {n+k-1 \choose k-1}, czy też jak wolisz {n+k-1 \choose n}.

Można powiedzieć, że obliczasz ile jest dwunastoelementowych kombinacji z powtórzeniami zbioru czteroelementowego. Kropek (czyli elementów każdej kombinacji) jest 12, a przegródki są 4. Założenie o tej trzynastce było błędne, bo kropek w sumie zawsze będzie dwanaście, a nie trzynaście.

Z kolei gdybyś miał wyznaczyć liczbę rozwiązań takiego równania w liczbach naturalnych dodatnich, to troszeczkę inaczej będzie. Wtedy proponowałbym podstawić do tego równania y_i=x_i-1 (oczywiście 1\leq i \leq n\k), a potem zastosować powyższą metodę dla zmiennych y_i (sprowadzamy zagadnienie do poprzednio rozwiązanego problemu :) ).
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest dzielnikow liczby  Anonymous  6
 nierownosc z 5 zmiennymi - ile rozwiazan w l. naturalnych?  Anonymous  25
 ile jest liczb 2cyfr/3cyfr, 5cyfr o pocz 12, bez cyfr 4 i 5?  Anonymous  1
 permutacje/ile jest sposobow ustawien/ -prosba o sprawdzenie  alamakota  3
 ile jest liczb trzycyfrowych, mniejszych od 555  Anonymous  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl