Induktionsbeweis von Mengen

28.06.2010, 17:48

Snoopy88

Induktionsbeweis von Mengen

Meine Frage:
Hallo,
ich versuche folgende Aufgabe zu lösen:
Unter je 6 natürlichen Zahlen gibt es stets zwei, deren Differenz durch 5 teilbar ist.

Meine Ideen:
Ich denke, vollständige Induktion ist der richtige Ansatz: Man muss irgendwie alle Differenzen zwischen 2 Zahlen der Menge M(die 6 Zahlen) berechnen und prüfen, ob das Ergebnis durch 5 teilbar ist. Ich weiß nicht, wie man das aufschreiben und allgemein beweisen soll. Kann mir bitte jemand helfen?

28.06.2010, 18:17

Mystic

Auf diesen Beitrag antworten »

RE: Induktionsbeweis von Mengen
Die Tatsache, dass die Peanoalgebra $\begin{eqnarray*} (\mathbb N,0, ') \end{eqnarray*}$ keine eigentlichen Unteralgebren hat, nützt hier sowas von gar nichts...Du willst ja schließlich keine Aussage über alle natürlichen Zahlen beweisen... geschockt

Bilde stattdessen alle Differenzen zu einem festgehaltenem Element... Was kannst du folgern, wenn entweder

1. alle diese Differenzen mod 5 verschieden
2. zwei dieser Differenzen mod 5 gleich

sind?

28.06.2010, 19:49

Snoopy88

Auf diesen Beitrag antworten »

Hmm... komme leider nicht drauf. Ich habe z.B. 6 Zahlen a,b,c,d,e,f.
Jetzt überprüfe ich (a-b)mod5, (a-c)mod5, etc. Und woher weiß ich, dass bei einer Differenz die Aussage erfüllt ist? Wie gehe ich denn konkret vor bzw. wie schreibe ich es auf? Danke für die Hilfe!

28.06.2010, 20:19

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Snoopy88
Hmm... komme leider nicht drauf. Ich habe z.B. 6 Zahlen a,b,c,d,e,f.
Jetzt überprüfe ich (a-b)mod5, (a-c)mod5, etc. Und woher weiß ich, dass bei einer Differenz die Aussage erfüllt ist? Wie gehe ich denn konkret vor bzw. wie schreibe ich es auf? Danke für die Hilfe!

Zunächst einmal ist eine gute Bezeichnung die halbe Rechnung...Die Elemente mit a,b,c,d,e,f zu bezeichnen ist schon mal eine ganz schlechte Idee, stattdessen solltest du sie indizieren, also z.B. $\begin{eqnarray*} a_0,a_1,a_2,a_3,a_4,a_5 \end{eqnarray*}$ nennen... Des weiteren hast du von den beiden Möglichkeiten, eine Differenz zu bilden, gerade die falsche genommen...Ich weiß nicht, ob man meine Anweisung oben so mißverstehen kann, aber sie war so gemeint, dass die Differenzen z.B.

$\begin{eqnarray*} a_1-a_0,\ a_2-a_0,\ a_3-a_0,\ a_4-a_0,\ a_5-a_0 \mod 5 \end{eqnarray*}$

sind, d.h., es ist dies eine Sequenz von 5 Zahlen aus der Menge $\begin{eqnarray*} \{0,1,2,3,4\} \end{eqnarray*}$ , da wir ja mod 5 rechnen... Nun spiel die beiden Fälle, welche ich oben genannt habe, und von denen ja genau einer auftreten muss, einfach einmal durch....

Edit: Siehst du, wie genial die Bezeichnung gewählt ist? Wir haben aufgrund der Indizes jederzeit einen Überblick über die Anzahl unserer "Schäfchen", ohne sie erst abzählen zu müssen.. Augenzwinkern

28.06.2010, 21:32

Snoopy88

Auf diesen Beitrag antworten »

Ok, also ich halte zum subtrahieren nacheinander a1-a6 fest, also:
a1-a2
a1-a3
a1-a4
a1-a5
a1-a6

a2-a3
a2-a4
a2-a5
a2-a6

...

Alles als Betrag und anschließend mod5 rechnen.

Zu 1: Wenn alle Differenzen mod5 versch. sind, muss min. einmal die 0 dabei sein, d.h. die Bedingung ist erfüllt.
Zu 2: Kannst du mir hier nochmal einenTipp geben?

28.06.2010, 22:21

Mystic

Auf diesen Beitrag antworten »

Hm, warum ignorierst du einfach, was ich oben geschrieben habe? So macht das echt keinen Spaß... unglücklich

Ich habe oben geschrieben

$\begin{eqnarray*} a_1-a_0, \ a_2-a_0, \ a_3-a_0, \ a_4-a_0, \ a_5-a_0 \end{eqnarray*}$

du machst daraus

Zitat:

Original von Snoopy88
Ok, also ich halte zum subtrahieren nacheinander a1-a6 fest, also:
a1-a2
a1-a3
a1-a4
a1-a5
a1-a6

a2-a3
a2-a4
a2-a5
a2-a6

...

d.h., ich habe genau 5 Differenzen angeschrieben, bei dir sind es offenbar 5+4+3+2+1=21(!!!)...Wo zum Teufel kommen die alle her und wozu brauchst du die anderen nach den ersten 5??? Des weiteren steht bei mir das feste Element (nämlich $\begin{eqnarray*} a_0 \end{eqnarray*}$ ) hinten, bei dir steht es vorne... Das hatte ich aber schon oben bemängelt...Obwohl es im Prinzip auch so gehen würde, machte es alles nur unnötigt kompliziert...

Bevor wir also zu Punkt 2 schreiten können (Punkt 1 ist noch lange nicht abgehakt!), solltest vorher diese Dinge alle berichtigen...

28.06.2010, 22:29

Snoopy88

Auf diesen Beitrag antworten »

Ich kann doch nicht nur die 5 Differenzen bilden?!
Beispiel: 6 Zahlen: 2 3 3 9 4 1
Jetzt mach ich es, wie du es vorschlägst:
a0 ist jetzt die 1
2-1=1
3-1=2
3-1=2
9-1=8
4-1=3
Keines dieser Ergebnisse erfüllt die Bedingung mod5=0
Wenn ich aber 9-4 rechne, erhalte ich 5 und 5mod5 ist 0. Dann ist die Bedingung erfüllt. Daher verstehe ich dein Konzept nicht ganz...

28.06.2010, 22:44

Mystic

Auf diesen Beitrag antworten »

Du rechnest zunächst einmal falsch. die Rechnung mit 2,3,3,9,4,1 geht in Wirklichkeit so:

$\begin{eqnarray*} 2-1 \equiv 1 \mod 5 \end{eqnarray*}$
$\begin{eqnarray*} 3-1 \equiv 2 \mod 5 \end{eqnarray*}$
$\begin{eqnarray*} 3-1 \equiv 2 \mod 5 \end{eqnarray*}$
$\begin{eqnarray*} 9-1 \equiv 3 \mod 5 \end{eqnarray*}$
$\begin{eqnarray*} 4-1 \equiv 3 \mod 5 \end{eqnarray*}$

d.h., die 5 Zahlen Zahlen in {0,1,2,3,4}, von denen oben die Rede war, sind also 1,2,2,3,3 und damit nicht alle verschieden, womit Bedingung 1 nicht erfüllt ist, aber dafür dann Bedingung 2... Du hast also in meiner Schreibweise dann z.B.

$\begin{eqnarray*} a_2-a_0 \equiv 2 \end{eqnarray*}$
$\begin{eqnarray*} a_3-a_0 \equiv 2 \end{eqnarray*}$

Bringt dich denn das auf gar keine Idee, wie man daraus eine Differenz "basteln" könnte, welche dann 0 mod 5 wird?

28.06.2010, 23:01

Snoopy88

Auf diesen Beitrag antworten »

Ja, ich hatte das schon verstanden mit dem Modulus, hatte ihn nur noch nicht auf meine Ergebnisse angewandt. Ich hatte nur geguckt, ob irgendwo 0 rauskommt.

Ok, ich denke/hoffe ich habe jetzt verstanden, was du meinst:

Fall1: Bei den mod5-Resten (0,1,2,3,4) muss bei 5 Differenzen einmal die 0 vorkommen, wenn alle Differenzen verschieden sind

Fall2: Es gibt min. 2 gleiche mod5-Reste, d.h. die Differenz der beiden Ergebnisse ist 0 und ich erhalte 0 mod 5. Im Bsp. rechne ich also a2-a3.

Stimmt es jetzt so? Wie würde ich den Beweis korrekt aufschreiben?

28.06.2010, 23:21

Snoopy88

Auf diesen Beitrag antworten »

Ok, danke für deine Bemühungen, habe es jetzt verstanden. Danke!

29.06.2010, 07:56

Mystic

Auf diesen Beitrag antworten »

Wow, also ist es doch noch was geworden... Freude

Ehrlich, als du zwischendurch plötzlich mit 21 Differenzen statt 5 daherkamst, noch dazu verkehrtherum angeschrieben, sah ich die Chancen darauf schon gegen 0 konvergieren...Aber auch im Fußball soll man ja erst nach 90 Minuten aufgeben... Augenzwinkern

Edit: Sorry, ich hab dir Unrecht getan, es waren nicht 21, sondern nur 15...Kopfrechnen müßte man halt können... unglücklich

29.06.2010, 11:08

Snoopy88

Auf diesen Beitrag antworten »

Hehe. Ja, bei mir war die ganze Zeit die Idee im Kopf, dass ich ja alle möglichen Differenzen bilden muss, um zu gucken, ob eine dieser Differenzen mod5=0 ergibt.
Aber es ist natürlich logisch, dass man nur die 5 braucht. Also vielen Danke nochmal!

Neue Frage »

Antworten »

Induktionsbeweis von Mengen

Verwandte Themen