Kombinatoryka Maciek: Ile jest liczb miedzy 0 a 999, których suma cyfr jest równa 20? Zrobiłem to metodą wypisywania kolejnych zbiorów tj. (9, 9, 2); (9, 8, 3), jednak nie wiem jaką metodą mógłbym to zrobić szybciej i bardziej uniwersalnie.

Blee: Na dobry sposob jest to najszybsza metoda.

PW: Liczba rozwiązań równania x₁+x₂+x₃ = 20, w którym x_k∊{2,3,..,9}.

Maciek: @PW: Takie mam założenia, ale jeśli chcę to zrobić metodą "rozmieszczania przedmiotów w szufladkach" to niestety nie mogę tam ograniczyć liczby przedmiotów w szufladce (albo nie wiem że istnieje taka możliwość).

Jerzy: Obawiam się,że "Twoja metoda" jest najszybsza: = 4*3! + 4*3 = 36

PW: (x₁−2)+(x₂−2)+(x₃−2) = 14 u₁+u₂+u₃ = 14, 0≤u_k≤7 − już trochę lepiej?

Maciek: @PW: Również to zastosowałem, ale to nic nie zmienia. Możemy mieć pudełko, w którym jest 14 elementów, a kolejne będą miały po 0. Nawet jeśli założymy, że pudełka mają być niepuste to jedno może mieć 12 elementów. @Jerzy A jeśli miałbym to zrobić najbardziej uniwersalnie to co byś zaproponował?

Jerzy: Skoro najmniejsza cyfrą musi być 2 , to do każdej z trzech szuflad wkładamy dwie kule, a pozostałe 14 kul rozmieszczamy bez żadnych ograniczeń.

Blee: Jerzy ... sa ograniczena ... do jednej szuflady nie mozesz wlozyc wiecej jak 7 kolejnych kul

Jerzy: Bzdura

Jerzy: No właśnie

Blee: Metoda szuflad nie mozna tego zrobic

Jerzy: Można, tylko to co napisałem trzeba skorygować: (2,2,2) i teraz rozmieszczamy 7 kul w trzch szufladach w dowolny sposób.

Jerzy: Dalej źle

Blee: Albo nie ... mozna. Do kazdej wkladamy po 1 kuli. Pozostale 16 ustawiamy w rzedzie i mamy dwie przegrody do wstawienia. Jedna wstawiamy na jedna z 8 miejsc patrzac od lewej (8 mozliwosci) i umiejscowienie to oznaczamy jako x. Druga wstawiamy od prawej w miejscach od 8 do x. (Srednia ilosc mozliwosci to 8−4 = 4) Stad mamy 8*4 = 32 mozliwosci.

Blee: Teraz rozpiszmy 9,9,2 *3 9,8,3 *6 9,7,4 *6 9,6,5 *6 8,8,4 *3 8,7,5 *6 8,6,6 *3 7,7,6 *3 W sumie 36 Mam blad winno byc 8 * 4.5 = 36

Maciek: No właśnie. Nie możemy zakładać, że w każdej szufladzie są conajmniej 2 kule. Czy w takim razie jest to możliwe metodą szufladkową? Kolega proponował mi metodę włączeń i wyłączeń, czy ma to sens?

Blee:

	8+1
4.5 =		−−− kazdy zakres ma rowne prawdopodobienstwo wystapienia, wiec srednia
	2

arytmetyczna daje nam srednia dlugosc drugiego zakresu (zaleznego od pierwszego)

Maciek: Wygląda sensownie. A w takim zadaniu znalazłoby to zastosowanie? Rzucamy dwiema kostkami do gry. Ile istnieje wyników rzutów, w których suma oczek jest większa od dziesięciu?

Jerzy: Musimy założyć minimum dwie kule, bo inaczej nie uzyskasz sumy 20: 9 + 9 + 1 = 19

Blee: Maciek ... ale to co ja napisalem de facto takze zaklada ze w szufladzie musza byc minimum 2 kule i nie wiecej jak 9. Pisze z komorki wiec nie moge zrobic rysunkow aby to zobrazowac. Tak czy siak, mozna metoda szuflad to zrobic, ale trzeba chwile sie zastanowic nad tym rozwiazaniem, a gdyby to byly liczby 4cyfrowe to juz metoda szufladowa bylaby mocno problematyczna.

Jerzy: Tutaj się już drzwi nie wyważa: (5,6) (6,6) lub (5,6)(6,5)(6,6) przy dwóch kolejnycj rzutach

Maciek: @Jerzy Prawda, ale zakładamy x₁ ≥ 2 ∪ x₂ ≥ 2 ∪ x₃ ≥ 2, a nie x₁ ≥ 2 ∩ x₂ ≥ 2 ∩ x₃ ≥ 2.

Jerzy: Masz rację Blee już od czterech szuflad zaczynają się schody.

Blee: Oczywidcie ze drugie zalozenie robisz Pierwsze nic Ci nie daje bo umozliwia takie liczby jak np 201.

Jerzy: Nie , zakładamy drugi wariant ( koniunkcja)

Maciek: Może faktycznie "wyważam drzwi". Po prostu nie wiem na ile wykładowca akceptuje nieformalne zapisy, a na ile chce mieć to poparte wzorami i twierdzeniami, dlatego staram się wszystko sprowadzić do jak najbardziej uniwersalnej formy.

Maciek: Mój błąd. Faktycznie koniunkcja. Zaczynamy od (2, 2, 2).

Jerzy: Co to znaczy "nieformalne zapisy" ?

Maciek: Np. rozpisywanie kolejnych przypadków (9, 9, 2) etc., zamiast znalezienie jakiegoś wzoru ogólnego.

Blee: Nie wazna metoda. Wazne ze dobrze

3Silnia&6: Mozna tez tak: (9−x; 9−y; 2+x+y) rozwiazan jest tyle co rozwiazan nierownosci x+y ≤ 7 (zakladajac, ze (x,y) = (1,2) i (2,1) to dwa rozne rozwiazania ) Ale nie jest to szybsza metoda niz ta wypisywanie (x,y,z)

Maciek: Niby racja, ale że jest to matematyka dyskretna na informatyce to liczy się również optymalizacja i szersze spojrzenie na problem. Wielkie dzięki @Blee i @Jerzy za pomoc. Dobrego dnia życzę.

Jerzy: Masz ich raptem 8 , więc w czym problem ? Jeśli w zadaniu masz 100 możliwości , to jest to z pewnością zadanie, dla którego można zastosować pewne wzory.

PW: Więcej Maćkowi nie będę pomagał, bo wszystko mu się nie podoba, a na szersze spojrzenie na problem mnie nie stać. Opowiem to samo co 3Silnia&6 trochę inaczej. Mamy pudełko z dwiema przegródkami. Ustawienie przegródek •••••••••|••|••••••••• to odpowiednik rozwiązania 9+2+9=20. Przesuwając przegródki w prawo lub lewo otrzymujemy inne rozwiązania − przesunięcie w lewo zmniejsza pierwszą liczbę, przesunięcie w prawo zmniejsza trzecią. Przesunięć w lewo lub w prawo może być maksymalnie 7, przy czym suma liczby przesunięć w prawo i w lewo nie może przekraczać 7 (środkowy składnik nie może być większy niż 9). Rozwiązań jest więc tyle, ile rozwiązań nierówności m+n≤7, 0≤m,n≤7. Zredukowaliśmy problem dotyczący trzech składników do szukania rozwiązania dla dwóch składników. Może nie trzeba wypisywać, ale rozwiązań jest 36: (0,0) (0,1) i (1,0) (0,2) i (2,0) (0,3) i (3,0) (0,4) i (4,0) (0,5) i (5,0) (0,6) i (6,0) (0,7) i (7,0) (1,1) (1,2) i (2,1) (1,3) i (3,1) (1,4) i (4,1) (1,5) i (5,1) (1,6) i (6,1) (2,2) (2,3) i (3,2) (2,4) i (4,2) (2,5) i (5,2) ((3,3) (3,4) i (4,3)

Mila: (1) x₁+x₂+x₃=20 ograniczenia: 2≤x_i≤9 Ograniczenie 1 : x_i≥2 y₁+y₂+y₃=14

14+3−1 3−1		12 2
	=		=120

wśród rozwiązań są takie trójki w których y_i≥10 Ograniczenie 2: A₁: y₁+y₂+y₃=14−8 y₁+y₂+y₃=6

6+3−1 3−1		8 2
	=		=28

|A₁|=|A₂|=A₃|=28 A_i∩A_j=Φ i A₁ ∩A₂ ∩ A₃=Φ Liczba rozwiązań (1): 120−3*28=120−84=36 ================

PW: No, i jest zasada włączania i wyłączania , ale Michał już chyba stwierdził, że nie ma tu zdolnych do optymalizacji i szerszego spojrzenia.

PW: Maciek, nie Michał. Przepraszam.

Mila: Może spojrzy.

Maciek: @PW Przepraszam jeśli poczułeś się urażony. Wielokrotnie uzyskałem tutaj pomysł, w tym od ciebie, od Mili, Jerzego, 5−latka oraz masy innych osób, które pomogły mi się rozwinąć. Nie miałem na celu nikogo obrazić, po prostu próbowałem się dopytać czy można zrobić to w inny sposób, tak żeby mieć większy wachlarz możliwości czy sprawdzenia potem poprawności wyniku. Widocznie nieuważnie dobierałem słowa za co przepraszam i bardzo dziękuję za rozpisanie twojego sposobu. Dobrej nocy życzę. @Mila Bardzo dziękuję. Na pewno mi się to przyda. Również życzę dobrej nocy lub dobrego dnia, zależnie kiedy to czytasz.

Mila: Dobranoc Jak widzisz tutaj szybciej jest metodą wypisania.