Matematyka dyskretna - rekurencja

[Paylinka07]

Czy ktoś mógłby mi pomóc w tych dwóch zadaniach? Nie wiem jak mam się do tego zabrać:(

1)Każdy chory człowiek zaraża dziennie dwie nowe osoby, po czym po \(\displaystyle{ 3}\) dniach zdrowieje, w chwili "zero" jest jeden chory człowiek. Niech \(\displaystyle{ C(n)}\) oznacza liczbę chorych ludzi po \(\displaystyle{ n}\) dniach. Podać rekurencyjna definicję ciągu \(\displaystyle{ C(n).}\)

2)Mamy gruby krążek sera i wykonujemy \(\displaystyle{ n}\) \(\displaystyle{ (n \ge 0)}\) cięć ( różnym cięciom odpowiadają różne płaszczyzny w przestrzenie) chcemy otrzymać w ten sposób jak najwięcej kawałków sera.
a) czy opłaca się nam kroić równolegle?
b)Na ile maksymalnie kawałków rozpadnie się ser przy \(\displaystyle{ 4}\) cięciach?
c) wyznacz \(\displaystyle{ P(n)-}\)maksymalną liczbę kawałków, powstających po \(\displaystyle{ n}\) cięciach?

[octahedron]

\(\displaystyle{ 1)\\
C_1=3\\
C_2=9\\
C_3=26\\
C_n=3C_{n-1}-C_{n-3}\\}\)

[sympatia17]

jak wyznaczyć \(\displaystyle{ P_{n}}\) w 2c?

[adambak]

\(\displaystyle{ P_0=1; \ P_1=2; \ P_2=4; \ P_3=7;}\) widać, że \(\displaystyle{ P_n=P_{n-1}+n \Rightarrow P_n=1+\frac{n(n+1)}{2}}\) i ma to swoje kombinatoryczne uzasadnienie. Aby zmaksymalizować liczbę obszarów każdą nową prostą prowadzimy tak aby przecinała każdą już istniejącą prostą w punkcie który jeszcze nie jest punktem przecięcia żadnych prostych (stąd dodanie \(\displaystyle{ n}\)-tej prostej powoduje zwiększenie liczby obszarów o \(\displaystyle{ n}\)).

[alekksis]

A co z zadaniem nr 2? Ma ktoś jakiś pomysł?

[norwimaj]

\(\displaystyle{ C_n=3C_{n-1}-C_{n-3}\\}\)

Czy masz jakieś uzasadnienie dla tej rekurencji? Moim zdaniem jest fałszywa, bo po śmierci pierwszego chorego liczba chorych powinna być zawsze parzysta, a wg Twojego wzoru \(\displaystyle{ C_4}\) nie jest. Przypomina mi się podobny błąd: 248134.htm#p932289

A co z zadaniem nr 2? Ma ktoś jakiś pomysł?

adambak już prawie wyczerpał temat, tylko że rozważył przypadek płaski. Jak dobrze to zrozumiesz, to uogólnisz na przypadek sera ciętego płaszczyznami.

[octahedron]

Czy masz jakieś uzasadnienie dla tej rekurencji?

Każdy chory zaraża trzech następnych, a zarażeni trzy dni wcześniej zdrowieją. Dlaczego uważasz, że liczba chorych musi być parzysta?

[norwimaj]

\(\displaystyle{ C_{n-3}}\) nie jest liczbą tych, którzy się zarazili trzy dni wcześniej, tylko liczbą wszystkich, którzy trzy dni wcześniej byli chorzy.

Nie licząc pierwszego chorego, wszyscy kolejni występują w parach. W parach się zarażają i w tych samych parach zdrowieją (wcześniej błędnie napisałem że umierają). Dlatego począwszy od \(\displaystyle{ C_3}\), wszystkie kolejne wyrazy powinny być parzyste.

[octahedron]

\(\displaystyle{ C_{n-3}}\) nie jest liczbą tych, którzy się zarazili trzy dni wcześniej, tylko liczbą wszystkich, którzy trzy dni wcześniej byli chorzy

Racja, powinno być:

\(\displaystyle{ C_n=3C_{n-1}-(C_{n-3}-C_{n-4})}\)

Poza tym oczywiście każdy zaraża dwóch, a nie trzech nowych, jak napisałem wyżej, i wtedy faktycznie można ich połączyć w pary.

[norwimaj]

\(\displaystyle{ C_{n-3}-C_{n-4}}\) też nie jest liczbą tych, którzy się zarazili trzy dni wcześniej. Jest to liczba tych, którzy się zarazili trzy dni wcześniej, pomniejszona o liczbę tych, którzy wtedy wyzdrowieli.

-- 11 maja 2012, o 23:08 --

Co powiesz na taką zależność?

\(\displaystyle{ C_n=2(C_{n-1}+C_{n-2}+C_{n-3})}\) dla \(\displaystyle{ n\ge3}\).

[octahedron]

Oj, w kółko robię ten sam błąd. A wzór pasuje. Po trzech dniach pozostaną tylko ci chorzy, którzy zarazili się w ciągu tych trzech dni.

[norwimaj]

A ktoś potrafi udowodnić bezpośrednio wzór, który napisałem? Ja potrafię tylko w taki sposób, że wprowadzam drugi ciąg \(\displaystyle{ B_n}\) - liczba tych, którzy zachorowali w chwili \(\displaystyle{ n}\). Wtedy \(\displaystyle{ B_n=2(B_{n-1}+B_{n-2}+B_{n-3})}\) dla \(\displaystyle{ n\ge1}\). Po dodaniu trzech takich równości otrzymujemy szukany wzór.

[octahedron]

A tak jak ja piszę jest źle? Bo myślę tak: wszyscy, którzy są chorzy w dniu \(\displaystyle{ n}\), w \(\displaystyle{ n+3}\) będą już zdrowi. Pozostaną tylko nowo zarażeni w ciągu tych \(\displaystyle{ 3}\) dni, a każdego dnia przybywa ich dwa razy tyle, ile było chorych dnia poprzedniego.

[norwimaj]

Może tak być. Dla mnie to było za trudne do wymyślenia.