Vollständige Induktion Rätsel
Stefan B.
ich hab als Haufaufgabe ein Rätsel bekommen dass wir durch V.I. lösen
sollen.
Und zwar sollen wir beweisen, dass alle Beträge größer/gleich 8 Rubel mit 5-
und 3-Rubel-Stücken ohne Wechselgeld zahlbar sind.
Ich habe keine Idee, wie ich das machen soll. Will mir jemand helfen? :-)
Rainer Rosenthal
Stefan B. wrote
> Und zwar sollen wir beweisen, dass alle Beträge
> größer/gleich 8 Rubel mit 5- und 3-Rubel-Stücken
> ohne Wechselgeld zahlbar sind.
>
Ein bisschen "Induktionsverankerung" muss schon sein,
d.h. ausser 8=3+5 solltest Du noch nachrechnen, dass
gilt: 9=3+3+3 und 10=5+5.
Schon ab n=11 gibt es nun kein Problem mehr, eine
Wechselgeld-Darstellung zu finden. Ziehe 3 ab von
dem zu wechselnden Betrag B. Diese Zahl B-3 ist sicher
nicht kleiner als 8. Und wenn alle bisherigen Zahlen
eine gute Wechselgeld-Darstellung haben, dann hat also
B-3 auch eine solche: B-3 = a+b+...+k.
Und schon haben wir auch eine für B, nämlich
B = 3+a+b+...+k.
Rainer Rosenthal
r.ros...@web.de
Christoph Sorge
Ja.
Induktionsanfang: Die Aussage stimmt für eine bestimmte Zahl bzw.
einen bestimmten Betrag. Wo Du anfängst, sollte relativ leicht zu
finden sein - und daß die Aussage für diesen Betrag stimmt, sieht man
auch leicht.
Dann zeigst Du: Wenn die Aussage für einen Betrag x gilt, gilt sie
auch für den Betrag x + 1.
Nun würde ich zwei Fälle unterscheiden:
1. Fall: Um auf den Betrag x zu kommen, hattest Du wenigstens ein
5-Euro-Stück. Was mußt Du dann wohl machen, um auf x+1 zu kommen?
2. Fall: Du hattest kein 5-Euro-Stück.
Mehr verrate ich nicht. Variationen der Lösung sollten möglich sein.
Christoph
--
[Volksentscheide]
> Ihre Ergebnisse dürfen allerdings ignoriert werden :-(
Is doch richtig so, wenn das Volk so doof ist *eg*
Tobias Erle in <833vx...@cornholio.kholdan.de>
Juergen Ilse
Kannst du das fuer die Betraege zwischen 8 und 15 Rubel beweisen?
Das waere doch schon ein Anfang, wenn du du dann noch bedenkst,
dass z.B. 16=8+8, 17=8+9, ... 23=8+15, 24=8+8+8, ... ist, bist du
doch schon annaehernd fertig, oder siehst du das noch nicht?
Tschuess,
Juergen Ilse (il...@usenet-verwaltung.org)
--
Das Netz ist Freude. Es ist Ekstase, die jeden einzelnen Nerv erglühen
läßt. Es ist Duft, den man fühlt. Es ist ein Bild, das man riecht.
Es ist Erfüllung - ein Geschmack, neben dem alles andere schal ist.
("Netzreiter-Preisung" aus dem Buch "Der Netzparasit" von Andreas Brandhorst)
Markus Wamser
Wieviele Rubel springen denn raus, wenn ich deine Hausaufgabe mache?
Tipp: 8 = 5+3
n = a*5+b*3 (n,a,b aus N)
Induktion über N. Hinweis: 5+1=6=2*3
Das sollte reichen.
/markus
--
(>"<) (>"<)
('o') offizielle Sig unter o", )
(¥(,) http://www.kleine-prinzen.de/sig.html (¥(,)
¿.¿.| ¿.¿.|
Rainer Rosenthal
Markus Wamser
> Stefan B. schrobte:
> > Und zwar sollen wir beweisen, dass alle Beträge größer/gleich 8 Rubel
> > mit 5- und 3-Rubel-Stücken ohne Wechselgeld zahlbar sind.
>
> n = a*5+b*3 (n,a,b aus N)
> Induktion über N. Hinweis: 5+1=6=2*3
>
> Das sollte reichen.
>
Sehe ich nicht.
Ich denke, dass die Induktion erst dann richtig los-nudeln kann,
wenn auch noch 9=3+3+3 und 10=5+5 festgestellt worden sind.
Denn dann kann - wie ich schon gepostet hatte - mit n-3 immer
auf eine schon zerlegte Zahl zurückgegriffen werden ab n=11.
Kurz gesagt: Dein Ansatz bringt keinen Beweis für n=9. Den muss man
eben erst mal zu Fuss ausführen. Ein interessantes Beispiel einer
Nicht-Nullachtfuffzehn-Induktionsverankerung.
Rainer Rosenthal
r.ros...@web.de
Torsten Metzner
>Markus Wamser
>> Stefan B. schrobte:
>> > Und zwar sollen wir beweisen, dass alle Beträge größer/gleich 8 Rubel
>> > mit 5- und 3-Rubel-Stücken ohne Wechselgeld zahlbar sind.
>>
>> Tipp: 8 = 5+3
>> n = a*5+b*3 (n,a,b aus N)
>> Induktion über N. Hinweis: 5+1=6=2*3
>>
>> Das sollte reichen.
>Sehe ich nicht.
Warum denn nicht, er muss hier doch nicht den ganzen Beweis
posten. Man überlege sich einfach noch das folgende:
Wenn eine natürliche Zahl n >= 8 in der Form n = a*5+b*3 mit a=0
dargestellt ist, was dann für b gelten muss.
>Ich denke, dass die Induktion erst dann richtig los-nudeln kann,
>wenn auch noch 9=3+3+3 und 10=5+5 festgestellt worden sind.
Das kann man so machen, muss man aber nicht (siehe oben).
>Ein interessantes Beispiel einer
>Nicht-Nullachtfuffzehn-Induktionsverankerung.
Die wie gesagt nicht nötig ist. Dein Beweis zeigt uns lediglich
sofort ohne groß nachzudenken, dass man immer eine Zerlegung
n = a*5+b*3 mit a <= 2 hinbekommt. Das sieht man beim anderen
Beweis zwar auch, aber m.M. nicht so direkt wie bei Dir.
Gruss,
ToM
Juergen Ilse
>>Sehe ich nicht.
Irgendwie hatte ich zuerst den Begriff "vollstaendige Induktion" ueberlesen
gehabt, und ich wuerde normalerweise auch niocht versuchen, die Aufgabe
mittels vollstaendiger Induktion zu loesen. Die einfachste Loesung scheint
mir die folgende zu sein (die benutzt aber keine vollstaendige Induktion):
Man berechne passende Darstellungen der Zahlen 8, 9, ... 15 der Form
a*3+b*5. Damit ist die Behauptung fuer diese Zahlen gezeigt. Jede ganze
Zahl >=16 laesst sich nun als Summe eienr dieser Zahlen und einem ganz-
zahligen Vielfachen der Zahl 8 darstellen. Da es sowohl fuer dies ganz-
zahlige Vielfache der Zahl 8 als auch fuer den Rest (eine Zahl aus der
Menge { 8, 9, ... 15 }) jeweils eine Darstellung als Summe von Vielfachen
der Zahlen 3 und 5 gibt, trifft das auch fuer die Summe zu. q.e.d.
Helmut Richter
> Man berechne passende Darstellungen der Zahlen 8, 9, ... 15 der Form
> a*3+b*5. Damit ist die Behauptung fuer diese Zahlen gezeigt. Jede ganze
> Zahl >=16 laesst sich nun als Summe eienr dieser Zahlen und einem ganz-
> zahligen Vielfachen der Zahl 8 darstellen. Da es sowohl fuer dies ganz-
> zahlige Vielfache der Zahl 8 als auch fuer den Rest (eine Zahl aus der
> Menge { 8, 9, ... 15 }) jeweils eine Darstellung als Summe von Vielfachen
> der Zahlen 3 und 5 gibt, trifft das auch fuer die Summe zu. q.e.d.
Der Anfangsschritt ist hässlich. Wie würde er aussehen, wenn du zeigen
willst, dass alle Beträge ab 4707200 Rubel mit 1601-Rubel-Stücken und
2943-Rubel-Stücken bezahlt werden können?
Deswegen hier noch eine Idee:
Ich habe p-Rubel-Stücke und q-Rubel-Stücke mit teilerfremden ganzzahligen p
und q, die beide größer als 1 sind. Im Folgenden sei immer alles ganzzahlig,
ohne dass es immer wieder hingeschrieben werden muss.
Der kleinste Betrag, von dem an alle Beträge nur mit p-Rubel-Stücken und
q-Rubel-Stücken bezahlt werden können, ist (p-1)(q-1). Das wird durch die
folgenden drei Sätze bewiesen:
Satz 1: Jeder Betrag lässt sich (mit Wechselgeld!) bezahlen, indem nur
p-Rubel-Stücke und q-Rubel-Stücke verwendet werden. Das heißt:
Für beliebiges n gibt es x und y, so dass n = px + qy.
Beweis:
Es sei L = {px + qy > 0 : x, y ganz}
L enthält mindestens p und q und ist daher nicht leer. Sei weiter g das
Minimum dieser Menge.
p ist in L, damit muss g<=p sein. Sei also p=gz+r mit 0<=r<g (Division mit
Rest). Damit ist, falls r>0, r=p-gz auch in L im Widerspruch zur
Minimalität von g. Also ist r=0, d.h. g ist Teiler von p. Analog ist g
Teiler von q, also gemeinsamer Teiler von p und q. Damit ist g<=ggT(p,q).
p ist Vielfaches von ggT(p,q), q ebenfalls. Damit sind auch alle
Linearkombinationen Vielfache von ggT(p,q), insbesondere g. Also
g>=ggT(p,q).
Daraus ergibt sich g=ggT(p,q).
Hier war aber p und q teilerfremd, d.h. ggT(p,q)=1. Es gibt mithin x und y,
so dass px + qy = 1. Alle n sind aber Vielfache von 1. (q.e.d.)
Satz 2: Jeder Betrag ab (p-1)(q-1) lässt sich ohne Wechselgeld bezahlen,
indem nur p-Rubel-Stücke und q-Rubel-Stücke verwendet werden. Das heißt:
Wenn n >= (p-1)(q-1), dann gibt es x, y >= 0, so dass n = px + qy.
Beweis:
Es gibt ganzzahlige x und y nach dem vorigen Satz, so dass n = px + qy. Sind
px und qy beide nicht negativ, so sind wir fertig. Sonst sei o.B.d.A. (ohne
Beschränkung der Allgemeinheit) px > 0 und qy < 0.
(o.B.d.A. ist hier erlaubt: wäre es andersherum, könnte man die Namen p und
q einfach vertauschen.)
qy ist Vielfaches von q, also qy <= -q
pq - p - q + 1 = (p-1)(q-1) <= n = px + qy <= px - q
pq - p + 1 <= px
pq - p < px
x > q-1
x >= q
Wir können also den Betrag pq aus dem Anteil px herausnehmen und in den
Anteil qy stecken, d.h. wir haben neue x'=x-q und y'=y+p, die ebenfalls eine
Lösung sind, und zwar ist px' nach wie vor nicht negativ. Das wiederholen
wir solange, bis qy nicht mehr negativ ist. (q.e.d.)
Satz 3: Der Betrag n = (p-1)(q-1) - 1 lässt sich nicht ohne Wechselgeld
bezahlen, indem nur p-Rubel-Stücke und q-Rubel-Stücke verwendet werden. Das
heißt:
Wenn n = (p-1)(q-1) - 1, dann gibt es keine x, y >= 0, so dass n = px + qy.
Beweisidee:
Man überlegt sich leicht, dass kein n' < pq auf mehr als eine Weise als
n' = px + qy mit x, y >= 0 dargestellt werden kann und dass pq nur
Darstellungen hat, bei denen x oder y verschwindet. Gäbe es nun eine
Darstellung für n = (p-1)(q-1) - 1 = px + qy, so wäre p(x+1) + q(y+1) eine
Darstellung von pq, für die weder x noch y verschwindet. (q.e.d.)
Helmut Richter
Juergen Ilse
Helmut Richter <a28...@mail.lrz-muenchen.de> wrote:
> In article <3dd9fdb1$0$833$a5ec...@news.ilse.asys-h.de>, Juergen Ilse wrote:
>> Man berechne passende Darstellungen der Zahlen 8, 9, ... 15 der Form
>> a*3+b*5. Damit ist die Behauptung fuer diese Zahlen gezeigt. Jede ganze
>> Zahl >=16 laesst sich nun als Summe eienr dieser Zahlen und einem ganz-
>> zahligen Vielfachen der Zahl 8 darstellen. Da es sowohl fuer dies ganz-
>> zahlige Vielfache der Zahl 8 als auch fuer den Rest (eine Zahl aus der
>> Menge { 8, 9, ... 15 }) jeweils eine Darstellung als Summe von Vielfachen
>> der Zahlen 3 und 5 gibt, trifft das auch fuer die Summe zu. q.e.d.
> Der Anfangsschritt ist hässlich. Wie würde er aussehen, wenn du zeigen
> willst, dass alle Beträge ab 4707200 Rubel mit 1601-Rubel-Stücken und
> 2943-Rubel-Stücken bezahlt werden können?
Der Anfangsschritt bei der Loesung ist haesslich, zugegeben, aber nicht
wirklich schwierig. Und der Rest ist dafuer sehr einfach. Wie ich deine
Frage beantworten wuerde stand bei der urspruenglichen Frage nicht zur
Debatte, da sie eine andere als die urspruengliche Aufgabenstellung ist.
Die zu loesende Aufgabe laesst sich mit meinem Loesungsansatz problemlos
und ohne allzu grossen Aufwand loesen, ob sich deine veraenderte Aufgaben-
stellung so loesen laesst stand nicht zur Debatte.
> Deswegen hier noch eine Idee:
[ Beweis fuer allgemeineren Fall gesnipped ]
Nett. Nun betrachte noch einmal deinen (allgemeinerten) Beweis und meine
nur fuer den Spezialfall gueltige Beweisskizze. Dir sollte auffallen, dass
ich fuer den Spezialfall mit erheblich weniger Aufwand ausgekommen bin.
Wenn ich nur einen Spezialfall zu loesen brauche, ist ein allgemeinerer
Beweise IMHO nur dann vorzuziehen, wenn ich von dem allgemeineren Beweis
Vorteile habe (z.B. wenn ich kann die Ergebnisse besser weiterverwenden
kann, wofuer ich aber eine Notwendigkeit haben muesste) oder wenn der
allgemeinere Fall nicht wesentlich mehr aufwand bedeutet ...
Ich wuerde in diesem Fall noch immer die "spezialisierte Loesung" vor-
ziehen, weil dein (uebrigens sher schoener) allgemeiner Beweis schlicht
fuer das was ich zu beweisen denke IMHO irgendwie "overkill" ist.