Indukcja hubik: Hej, zrobiłem zadanie z indukcji, ale nie jestem pewien czy dobrze. Proszę więc o ośmieszenie mnie teraz aby nie zrobił tego wykładowca Firma kateringowa pakuje kanapki wyłącznie w pudełka po 3 lub 5 sztuk. Udowodnij że każdą liczącą co najmniej 8 sztuk liczbę kanapek można zapakować w takie pudełka tak aby wszystkie pudełka były pełne Niech X⊂N takim, że: −8 ∊ X − Dla każdego n∊N i n≥8, jeśli n∊X to (n+1)∊X Wtedy każde n∊N, n≥8 n∊X X = {n∊N, n≥8 | n=3a + 5b} gdzie a,b∊Z Podstawa indukcji: n=8 8=3*1+5*1 => 8∊X Krok indukcyjny: Załóżmy że dla dowolnego n∊N, n≥8, n∊X więc (n+1)∊X n = 3a+5b (n+1) = 3a' + 5b' 3a+5b = 3a + (3+2)b = 3a+3b+2b = 3(a+b) + 2b Każdą liczbę parzystą można zapisać jako: 2b Każdą liczbę nieparzystą większą równą 8, można zapisać jako: 2b + 3x = 2b + 3(a + b) Jeśli (n+1) jest liczbą parzystą, to: (n+1) = 2b' = 2b' + 3*0 = 2b' + 3(a' + b') => (n+1) ∊X Jeśli (n+1) jest liczbą nieparzystą, to: (n+1) = 2b' + 3x = 2b' + 3(a' + b') => (n+1) ∊ X Co oznacza że... Wydaję mi się że dobrze, ale nie wiem czy muszę udowadniać że liczbę nieparzystą można zapisać jako 2b = 3x i czy to wystarczy, czy gdzieś jest błąd logiczny. Pomożecie?

wredulus_pospolitus: Yyyyy ... absolutnie nie pokazałeś, że można zapakować w opakowania po 2 lub 3 sztuk i tyle a nie, że po 5 lub 3 sztuk 1) n = 8 −−−> 8 = 1*3 + 1*5 n = 9 −−−> 9 = 3*3 + 0*5 n = 10 −−−> 10 = 0*3 + 2*5 2) n = k −−−− da się zapakować 3) n = k+3 wtedy da się zapakować, bo dokładamy jedno opakowanie '3'

wredulus_pospolitus: Pamiętaj −−− w podstawie indukcyjnej NIE MUSIMY odnosić się tylko do jednego (najczęściej najmniejszego) elementu

wredulus_pospolitus: Inna możliwość 1) n = 9 −−−> 9 = 3*3 + 0*5 2) n = 3k można zapakować (same '3' w końcu) (pamiętajmy, że k≥3) 3) n = 3k−1 = 3(k−2) + 6 − 1 = 3(k−2) + 5 (można zapakować) n = 3k + 1 = 3(k−3) + 9 + 1 = 3(k−3) + 2*5 (można zapakować) Zauważ, że w tej wersji rozwiązania w podstawie indukcji nie sprawdzamy n=8, dopiero w (3) kroku wykazujemy, że skoro można zapakować n=9 sztuk, to także można zapakować n=8 (oraz n=10) sztuk

jc: Krok indukcyjny: Załóżmy że dla dowolnego n∊N, n≥8, n∊X więc (n+1)∊X n = 3a+5b (n+1) = 3a' + 5b' Trochę bez sensu. Można tak: 8=8, 9=3+3+3, 10=5+5 Zatem twierdzenie jest prawdziwe dla n ∊{8,9,10} Załóżmy, że twierdzenie jest prawdziwe dla n ∊ {8, 9, 10, ..., n}, n≥ 10 Weźmy n+1. Usuńmy 3 kanapki. (n+1)−3=n−2 ∊ {8, 9, 10, ..., n} bo n−2 ≥ 8. Pakujemy n−2 kanapek i dodajemy pudełko z 3 kanapkami. Zatem twierdzenie jest prawdziwe dla n ∊ {8, 9, 10, ..., n+1}. Z godnie z zasadą indukcji, twierdzenie jest prawdziwe dla każdego n≥8.

wredulus_pospolitus: W drugiej wersji KLUCZOWE jest zapisanie, że k≥3

wredulus_pospolitus: @jc −−− chwila chwila I. zakładasz prawdziwość zdarzenia dla 'n' (OK) II. badasz prawdziwość zdarzenia dla 'n+1' (OK) III. ale badasz to na zasadzie −−−> wyjmujemy 3 sztuki ... mamy 'n−2' sztuki które możemy zapakować (niby skąd to wiemy? gdzie to wykazałeś), więc dokładamy opakowanie na 3 sztuki i możemy zapakować 'n+1' sztuk Nooooo ... chyba jednak to nie jest dowód tego, że 'n+1' sztuk można zapakować

hubik: A no tak XDDDD Czyli jak udowodnimy dla 8, 9 i 10, to n+1 można przedstawić jako dodawanie opakowania 3szt do 8, 9 lub 10, wtedy zawsze wyjdzie dobrze?

wredulus_pospolitus: nie ... jeżeli udowodnisz dla 8,9,10 to 'n+3' można przedstawić jako zapakowanie 'n' i dołożenie opakowania na 3szt. (więc z 8 mamy 11, a z niej 14, a z niej 17, itd.) (więc z 9 mamy 12, a z niej 15, a z niej 18, itd.) (więc z 10 mamy 13, a z niej 16, a z niej 19, itd.)

wredulus_pospolitus: więc w (3) punkcie indukcji NIE ROZPATRUJEMY n+1 tylko n+3

hubik: Dobra, już chyba wszystko rozumiem. Ale dla pewności, zapiszę to w taki sposób: X⊂N takim że: 8∊X 9∊X 10∊X Dla każdego..., jeśli n∊X oraz (n+1)∊X oraz n+2∊X to n+3∊X Wtedy... X={n∊N, n≥8 | n=5a+3b} Podstawa... Krok indukcji: Zakładając że n∊X i... to n+3∊X ponieważ jeśli n∊X to n=5a+3b => n+3 = 5a+3b + 3 => 5a+3(b+1) => (n+3)∊X Tak?

wredulus_pospolitus: NIEEEEEE dla każdego n ∊ X −> (x+3) ∊ X tyle wystarczy

wredulus_pospolitus: zauważ, że nawet tylko dokładnie z tego korzystasz w trzecim punkcie indukcji

hubik: Czyli jak udowodniłem dla 8, 9, 10 to napiszę w kroku że n∊X ... to (n+3)∊X i nic więcej?

jc: wredulus Zakładamy tw. dla x ∊ {8,9,...,n}, przy czym n ≥ 10. x=n+1, (x+1)−3 = n−2 ∊ {8,9,...,n} bo n− 2≤n i n−2 ≥ 10−2=8 x−3 kanapek możemy zapakować. Możemy więc zapakować x kanapek, czyli n+1 Oznacza to, że twierdzenie jest słuszne dla x ∊{8,9, ..., n+1}. −−−−− Oczywiście można było nie używać takiego sformułowania zasady. Wystarczyło rozpatrzyć takie zdanie: Można zapakować n, n+1 oraz n+2 kanapek przy n ≥ 8. Dla n=1 mamy: 8=5+3, 9=3+3+3, 10=5+5 Krok indukcyjny. Załóżmy, że można zapakować n, n+1, n+2 kanapek. Weźmy n+3 kanapek. Tyle można zapakować, bo n można. Zatem można zapakować n+1, n+2, n+3 kanapek.

wredulus_pospolitus: @JC ... ok ... zakładasz prawdziwość dla wszystkich k ≤ n ... nie zauważyłem tego