krok indukcyjy - problem Flawiusza

Ze względu na specyfikę metody - osobny dział.
Lukaszjuly

krok indukcyjy - problem Flawiusza

Post autor: Lukaszjuly »

Mam problem ze zrozumieniem zagadnienia Flawiusza w sposób w jaki zostało to przedstawione w podręczniku "Matematyka konkretna" Grahama...
Problem jest zmodyfikowana- co druga osoba umiera.
Rekurencyjnie problem przedstawiono tak:

\(\displaystyle{ J(1)=1;\\
J(2n)=2J(n)-1, \ dla \ n \ge 1,;\\
J(2n+1)=2J(n)+ 1, \ dla \ n \ge 1}\)


Wzór ogólny to:
\(\displaystyle{ J(2 ^{m}+l)=2l+1 }\)

dowód indukcyjny dla liczb parzystych:
\(\displaystyle{ J(2 ^{m} +l)=2J(2 ^{m-1}+l/2)-1=2(2l/2+1)-1=2l+1 }\)
i tego dowodu nie rozumiem- kroku 2 i przede wszystkim 3.
Ostatnio zmieniony 20 wrz 2020, o 16:57 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: parzystych.
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: krok indukcyjy - problem Flawiusza

Post autor: Jan Kraszewski »

Dobrym zwyczajem jest podawanie treści zadania, o którym mówisz. Nie każdy musi wiedzieć, co to jest "zagadnienia Flawiusza w sposób w jaki zostało to przedstawione w podręczniku "Matematyka konkretna" Grahama".

JK
Lukaszjuly

Re: krok indukcyjy - problem Flawiusza

Post autor: Lukaszjuly »

Zacznę ponownie Treść zadania. Mamy n ludzi ponumerowanych od 1 do n siedzących po okręgu. Co druga osoba jest eliminowana. Pytanie znając n gdzie należy usiąść aby nie zostać wyeliminowanym?
Podać wzór rekurencyjny rozwiązania, wzór ogólny i udowodnić indukcyjnie wzór ogólny. W moim przykładzie wzory zostały podane. Nie rozumiem natomiast dowodu indukcyjnego tam przeprowadzonego. Ale po kolei.


Tutaj dodam, że w książce autor dokonał kilku manewrów w numerowaniem osób w okręgu, jest kilka ilustracji okręgów, których w latex nie potrafię zrobić.

Autor zaczął z \(\displaystyle{ 2n}\) osobami przy stole i po pierwszej rundzie eliminacyjnej przy "stole" pozostały osoby \(\displaystyle{ 1,\ 3,\ ...,\ 2n-3,\ 2n-1}\)

stąd wywnioskowano, że \(\displaystyle{ J(5\cdot 2^{m})=2^{m+1}+1}\).

W przypadku nieparzystą liczbą \(\displaystyle{ 2n+1}\) osób przy stole po pierwszej rundzie eliminacyjnej pozostało \(\displaystyle{ 3,\ 5,\ 7,\ ...,\ 2n-1,\ 2n+1}\)

Ponieważ przeprowadzono kilka przykładów eliminacji osób spośród liczby parzystej i nieparzystej ich przy stole, określono wzór rekurencyjny:
\(\displaystyle{ J(1)=1;\\ J(2n)=2J(n)-1;\\ j(2n+1)=2J(n)+1}\) w dwu ostatnich przypadkach dla \(\displaystyle{ n \ge 1}\)

Stad wzór ogólny
\(\displaystyle{ J(2^{m}+l)=2l+1,\ dla \ m \ge 0 \ oraz \ 0 \le l \le 2^{m}}\)

Gdzie \(\displaystyle{ n}\) to ilość miejsc i \(\displaystyle{ n=2^{m}+l}\), \(\displaystyle{ 2^{m}}\) to największa potęga 2 nie przekraczająca \(\displaystyle{ n}\), a \(\displaystyle{ l}\) jest tym co pozostaje.
Uwaga dodatkowa. Jeżeli \(\displaystyle{ 2^{m} \le n<2^{m+1}}\) to reszta \(\displaystyle{ l=n-2^{m}}\) spełnia zależność \(\displaystyle{ 0 \le l<2^{m+1}-2^{m}=2^{m}}\)

W podręczniku udowodniono ten wzór następująco.
W dowodzie użyto indukcji ze względu na m.
Gdy \(\displaystyle{ m=0}\) to \(\displaystyle{ l=0}\) i wtedy dla \(\displaystyle{ J(1)=1}\)
Dowód indukcyjny składa się z 2 cześć. Jeżeli\(\displaystyle{ m>0,}\) i przy tym \(\displaystyle{ 2^{m}+l=2n}\) to \(\displaystyle{ l}\) jest parzyste. I tutaj zaczyna się dowód wyżej wspomniany, gdzie nie rozumiem kroku 2 i 3.

W przypadku nieparzystym gdy \(\displaystyle{ 2^{m}+l=2n+1}\), dowód wygląda tak:

\(\displaystyle{ J(2n+1)-J(2n)=2}\) i tego też nie do końca rozumiem.

Wydaje mi się, że przepisałem to co najistotniejsze. Przed tymi dowodami było kilka ilustracji pokazujących jak siedzą ludzie i jak są numerowane ich pozycje.
Ostatnio zmieniony 20 wrz 2020, o 18:40 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
ODPOWIEDZ