kombinatoryka waski: Jeżeli każdego dnia idziemy do piekarni i kupujemy chleb za 2zł lub ciasto za 1zł, przy czym ciasto możemy wybrać spośród czterech rodzajów, a chleb to chleb, tylko jeden rodzaj. Na ile sposobów możemy wydać pieniądze mając "n zł" ?

daras: ja bym wolał wydac na

wredulus_pospolitus: Jeżeli jest to zadanie 'standardowe' to wybacz, ale nauczyciel musiał się pomylić ... bo to jest naprawdę nie takie proste zadanie dla licealisty. Jeżeli jest to zadanie konkursowe ... to wybacz, ale nie jesteśmy od tego −−− sam musisz wpaść na rozwiązanie.

Piotr 10: daras haha, mi to już starczy

waski: to nie jest zadanie konkursowe, to zadanie z gwiazdką i nie wiem jak to dokładnie zapisać, ponieważ: n = 1zł to mamy 4 możliwości n = 2zł to mamy 16 możliwości lub 2 n = 3zł to (1 możliwość + 4 możliwości) lub (4³ = 64 możliwości) tylko nie wiem co dalej, jak to zapisać prawidłowo

waski: może ktoś pomóc ?

waski:

waski: nikt nie pomoże ?

waski: nikt nie wie ?

Trivial: To zadanie nie jest wcale trywialne. Spróbuję za jakiś czas je rozwalić.

sushi_ gg6397228: rozpisuj po kolei ile mozesz kupic za dana kwotę towaru kazdego rodzaju 1zł = 0 chleba , 1 ciastko 2zł = 1 chleb, 0 ciastek + 0 chleba , 2 ciastka 3zł= 1 chleb , 1 ciastko + 0 chleba, 3 ciastka 4zł= 2 chleby, 0 ciastka + 1 chleb , 2 ciastka + 0 chleba , 4 ciastka ....

Trivial: sushi widzę rozwalił.

waski: ale to praktycznie to samo co ja napisał, a tutaj chyba trzeba to jakoś od n uzależnić i na to nie mam pomysłu

waski: nie bardzo rozumiem zapis sushi dla 4zł 5zł = 2 chleby + 1 ciastko, 1 chleb + 3 ciastka, 5 ciastek 4zł = 2 chleby, 1 chleb + 2 ciastka, 4 ciastka

Trivial: Niech f(n) oznacza liczbę kombinacji dla n zł. Mamy: f(0) = 1 (jeden sposób żeby wydać 0 zł − nic nie kupić) f(1) = 4¹ f(2) = 4⁰ + 4² f(3) = 4¹ + 4³ f(4) = 4⁰ + 4² + 4⁴ f(5) = 4¹ + 4³ + 4⁵ Zauważmy, że f(2k+1) = 4*f(2k) oraz

	(42)k+1−1		1
f(2k) = 40 + 42 + 44 + ... + 42k =		=		(42k+2−1) =
	42−1		15

	1
=		(4n+2 − 1).
	15

f(2k+1) = 4*f(2k).

waski: prawie rozumiem, lecz dlaczego zapisujemy f(2k+1) = 4*f(2k)?

Trivial: Po prostu taka obserwacja. f(n) = 4*f(n−1) dla n nieparzystego.

waski: ok, a masz może pomysł dla takiego zadania: Określ liczbę podzbiorów A , gdzie nie znajdują się kolejne 2 liczby. A − zbior o n−elementach w liczbach naturalnych (kolejnych).

teofrast: Spróbowałem « zapomnieć », że to ma być zadanie z kombinatoryki... Niech x oznacza liczbę bochenków chleba, a y − liczbę ciastek. Mamy zatem równanie 2x + y = n. Pytanie w zadaniu można przetłumaczyć następująco: Ile jest par (x, y ) rozwiązujących to równanie diofantyczne? ( zakładamy, że (i) wydajemy całośc sumy, oraz (ii) nie można kupić ani pół, ani ćwierci bochenka, co zgodne jest z narzuconym nam przez obcych kapitalistów trybem zakupów w supermarketach...). Równanie to jest « dobrze okreslone », gdyż NWD(2, 1)=1, zatem spełnione jest kryterium Bézouta rozwiązalności tego równanie w liczbach całkowitych. Rozwiązaniem rzeczonego równania jest każda para (x, y)=(t, n−2t) gdzie t ∊ ℤ. Kładąc x > 0 i y>0 dostajemy warunek na t: 0 < t < n/2 & t ∊ ℤ. Liczbą sposobów rozkładu sumy pieniędzy będzie maksymalna wartość na t równa ENT(n/2)

Trivial: Niech A_n = { 1, 2, 3, 4, 5, ..., n } oraz a_n oznacza liczbę podzbiorów A_n, gdzie nie znajdują się dwie kolejne liczby. Mamy: a₀ = 1 // ∅ → ∅ a₁ = 2 // { 1 } → ∅, {1} a₂ = 3 // { 1, 2 } → ∅, {1}, {2} a_n uzyskamy postępując w taki sposób: Wybieramy 1 i podzbiór z { 3, 4, ..., n } Wybieramy 2 i podzbiór z { 4, 5, ..., n } Wybieramy 3 i podzbiór z { 5, 6, ..., n } ... Wybieramy n−1 i podzbiór z ∅. Lub wybieramy po prostu zbiór pusty. a_n = 1 + ∑_k=2..n a_n−k = 1 + ∑_k=0..n−2 a_k Mamy: a_n+1 − a_n = 1 + ∑_k=0..n−1 a_k − 1 − ∑_k=0..n−2 a_k = a_n−1 a_n = a_n−1 + a_n−2 Rozpoznajemy liczby Fibonacciego. Zaczynamy od a₀ = 1, a₁ = 2 zatem: a_n = fib(n+2).

Trivial: teofrast, nie można tak zrobić gdyż są 4 ciastka do wyboru, a u Ciebie jest tylko jedno y.

waski: Bardzo dziekuje za odpowiedz, lecz Trivial moglbys napisac skad otrzymales: a_n=1+∑_k=2,...n a_n−k = 1 + ∑_{k=0,...,n−2} a_k

waski: i dlaczego a_n = fib(n+2)

Trivial: a_n = fib(n+2), bo a_n spełnia równanie rekurencyjne Fibonacciego oraz a₀ = 1, a₁ = 2 (zaczynamy po prostu trochę dalej: fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2)

Trivial: A skąd otrzymałem tę sumę wyjaśniłem w oryginalnym poście. Możemy wybrać podzbiór (spełniający warunki zadania) w taki sposób: Może być to ∅. Jest jeden taki zbiór. Wybieramy 1 i podzbiór z { 3, 4, ..., n }. Jest a_n−2 takich podzbiorów. Wybieramy 2 i podzbiór z { 4, 5, ..., n }. Jest a_n−3 takich podzbiorów. Wybieramy 3 i podzbiór z { 5, 6, ..., n }. Jest a_n−4 takich podzbiorów. ... Wybieramy n−2 i podzbiór z { n }. Jest a₁ takich podzbiorów. Wybieramy n−1 i podzbiór z ∅. Jest a₀ takich podzbiorów. Wybieramy n i podzbiór z ∅. Jest a₀ takich podzbiorów. ← wcześniej miałem tutaj błąd. Zatem a_n = 1 + a_n−2 + a_n−3 + ... + a₀ + a₀ =^a₀=1= 2 + ∑_k=0..n−2 a_k. I dalej tak samo jak wcześniej. Wynik końcowy nie zmienia się.

Trivial: A jeśli chodziło Ci tylko o samą sumę, to zamieniłem po prostu indeks: k' = n−k k = 2, 3, 4, ..., n ⇒ k' = n−2, n−3, n−4, ..., 1, 0 = 0,1,2,...,n−2.