udowodnić indukcyjnie

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
olcia446
Użytkownik
Użytkownik
Posty: 46
Rejestracja: 2 cze 2011, o 22:26
Płeć: Kobieta
Lokalizacja: Lublin
Podziękował: 9 razy

udowodnić indukcyjnie

Post autor: olcia446 » 24 sie 2011, o 14:45

Udowodnić indukcyjnie, że każdą co najmniej ośmiozłotową opłatę skarbową można uiścić mając do dyspozycji tylko znaczki skarbowe o nominałach \(\displaystyle{ 3}\)zł i \(\displaystyle{ 5}\)zł.

mateuszek89
Użytkownik
Użytkownik
Posty: 1106
Rejestracja: 1 lip 2010, o 15:27
Płeć: Mężczyzna
Lokalizacja: toruń
Pomógł: 153 razy

udowodnić indukcyjnie

Post autor: mateuszek89 » 24 sie 2011, o 15:30

1. Sprawdzamy dla \(\displaystyle{ n=8}\) czy istnieją takie \(\displaystyle{ x,y \in \mathbb{N}_{0}}\), że \(\displaystyle{ 3x+5y=8}\). Oczywiście \(\displaystyle{ 3 \cdot 1 + 5 \cdot 1=8}\) więc ok.
2. Założenie. Istnieją takie \(\displaystyle{ x,y \in \mathbb{N}_{0}}\), że \(\displaystyle{ 3x+5y=n}\) dla jakiegoś \(\displaystyle{ n \ge 8}\). Oczywiście \(\displaystyle{ n \in \mathbb{N}}\).
3. Teza. Istnieją \(\displaystyle{ k,l \in \mathbb{N}_{0}}\) takie, że \(\displaystyle{ 3k+5l=n+1}\)
4. Dowód.
a) Jeśli \(\displaystyle{ 3|n}\) to \(\displaystyle{ n=3 \cdot b}\) gdzie \(\displaystyle{ b \ge 3}\) (bo \(\displaystyle{ n \ge 9}\)). Szukamy takich \(\displaystyle{ k,l}\), że:
\(\displaystyle{ 3k+5l=n+1}\)
Zauważmy, że:
\(\displaystyle{ n+1=3x+5y+1=3(x-3)+5(y+2)}\).
Stąd biorąc \(\displaystyle{ k:=x-3}\) oraz \(\displaystyle{ l:=y+2}\) otrzymujemy żądany rozkład. \(\displaystyle{ k,l \in \mathbb{N}_{0}}\), bo \(\displaystyle{ y \in \mathbb{N}_{0}}\) oraz \(\displaystyle{ x \ge 3}\) i \(\displaystyle{ x \in \mathbb{N}_{0}}\).
b) \(\displaystyle{ n}\) nie jest podzielne przez \(\displaystyle{ 3}\). Wtedy z równania \(\displaystyle{ 3x+5y=n}\) możemy wywnioskować, że \(\displaystyle{ y \ge 1}\). Szukamy takich \(\displaystyle{ k,l \in \mathbb{N}_{0}}\), że:
\(\displaystyle{ 3k+5l=n+1}\)
Zauważmy, że:
\(\displaystyle{ n+1=3x+5y+1=3(x+2)+5(y-1)}\).
Stąd biorąc \(\displaystyle{ k:=x+2}\) i \(\displaystyle{ l:=y-1}\) otrzymujemy żądany rozkład. Oczywiście \(\displaystyle{ k,l \in \mathbb{N}_{0}}\).

Pozdrawiam!

MichalKulis
Użytkownik
Użytkownik
Posty: 47
Rejestracja: 19 sty 2011, o 08:15
Płeć: Mężczyzna
Lokalizacja: Wrocław

udowodnić indukcyjnie

Post autor: MichalKulis » 21 wrz 2011, o 12:29

Jest mały błąd w podpunkcie a) dowodu. Niekoniecznie \(\displaystyle{ x \ge 3}\).
Weźmy np. \(\displaystyle{ 11 = 3 \cdot 2 + 5 \cdot 1}\) czyli \(\displaystyle{ x=2, y=1}\).
I z tego wnioskujemy, że można przedstawić 12 w następującej formie: \(\displaystyle{ 12 = 3 \cdot k + 5 \cdot l}\) gdzie \(\displaystyle{ k=x-3=-1, l=y+2=3}\). Czyli dostajemy \(\displaystyle{ k<0}\). Błąd.

ODPOWIEDZ