Bundeswettbewerb Mathematik 1997

02.11.2008, 18:41

studiersti

Auf diesen Beitrag antworten »

Bundeswettbewerb Mathematik 1997

"Kann man aus 100 beliebig gegebenen ganzen Zahlen stets 15 Zahlen derart auswählen, dass die Differenz zweier beliebiger dieser 15 Zahlen durch 7 teilbar ist? (Beweis)"

Hallo!

Diese Aufgabe stammt vom oben genannten Wettbewerb.

Erstens ist mir nicht ganz klar, ob diese "beliebig" gegebenen Zahlen "am Stück" sind oder wirklich x-beliebig.

Also, für x-beliebige Zahlen wäre das doch unmöglich...zumindest wäre der Beweis unmöglich, oder?
Realistischer erscheint es mir da für 100 beliebige Zahlen am Stück.

1-100 z.B.

Und wie wäre da der Ansatz?
In einem anderen Forum habe ich gelesen, dass man mit mod 7 arbeiten muss.

02.11.2008, 18:54

kiste

Auf diesen Beitrag antworten »

Hallo,

ein paar Überlegungen(ich löse normalerweise keine Wettbewerbsaufgaben deshalb mit Vorsicht zu geniesen):
-Hast du die Differenz $\begin{eqnarray*} x-y \equiv r_1 \mod 7 \end{eqnarray*}$ und $\begin{eqnarray*} y-z \equiv r_2 \mod 7 \end{eqnarray*}$ so ist offensichtlich $\begin{eqnarray*} (x-y) + (y - z) = x - z \equiv r_1+r_2 \mod 7 \end{eqnarray*}$ .
-Zähle die Möglichkeiten verschiedene Differenzen zu bilden(Hast du beispielsweise die Zahlen 3,5,7 so ist 7-5 = 5-3. Diese fallen also zusammen). Wie viele der Differenzen sind also verschieden?

03.11.2008, 20:32

studiersti

Auf diesen Beitrag antworten »

Ich komme damit ehrlichgesagt nicht weiter. :/

03.11.2008, 20:35

AD

Auf diesen Beitrag antworten »

Ich sage nur: Schubfachprinzip

03.11.2008, 20:59

studiersti

Auf diesen Beitrag antworten »

Hallo!

Das Schubfachprinzip habe ich noch nie verwendet bzw. gelernt, habe mich jetzt aber gerade darüber informiert.

Es gibt 100 Objekte und 7 Kategorien, da die Zahlen den Rest 0, 1, 2, ...,6 haben können.

Wäre das soweit richtig?
Und wenn ja, wie geht es dann weiter?

Ich muss es schließlich für 15 beliebige Zahlen beweisen.

03.11.2008, 21:29

AD

Auf diesen Beitrag antworten »

Ich meine natürlich die erweiterte Fassung des Schubfachprinzips, wie die Wikipedia es nennt: Verschärfung.

Kann man sich auch selbst zusammenpuzzeln über einen indirekten Beweis.

Anzeige

03.11.2008, 21:41

studiersti

Auf diesen Beitrag antworten »

Danke für den Link. smile

smile

Gibt es denn bei meiner Aufgabe nicht mehr als "n" und "k"?

Also, Anzahl der Objekte und der Mengen.

n dürfte also 100 sein, da ich 100 beliebige Zahlen habe.

k ist dann die Anzahl der Mengen, in diesem Fall die Anzahl der möglichen 15-er Kombination aus 100 Zahlen?

03.11.2008, 21:43

AD

Auf diesen Beitrag antworten »

Da warst du aber schon mal weiter:

Zitat:

Original von studiersti
Es gibt 100 Objekte und 7 Kategorien, da die Zahlen den Rest 0, 1, 2, ...,6 haben können.

03.11.2008, 21:48

studiersti

Auf diesen Beitrag antworten »

Also ist k dann 7?

Nur weiß ich jetzt nicht, wie ich das mit diesen 15 beliebigen Zahlen dann noch unterbringen soll?!

04.11.2008, 07:46

AD

Auf diesen Beitrag antworten »

Also wirklich ... du bist fertig, und siehst es nicht! Finger1

Finger1

Das (verschärfte) Schubfachprinzip sagt nun, dass es mindestens eine Restklasse modulo 7 gibt, in der mindestens $\begin{eqnarray*} \left\lceil \frac{100}{7} \right\rceil = 15 \end{eqnarray*}$ Zahlen der 100 Zahlen liegen. Was kann man denn über die Differenz von zwei Zahlen aus derselben Restklasse sagen, also hinsichtlich der Teilbarkeit dieser Differenz durch 7 ???

04.11.2008, 15:28

studiersti

Auf diesen Beitrag antworten »

Ihre Differenz muss durch 7 teilbar sein?

04.11.2008, 15:57

AD

Auf diesen Beitrag antworten »

Genauso ist es. Augenzwinkern

Augenzwinkern

04.11.2008, 16:06

studiersti

Auf diesen Beitrag antworten »

Ok!

smile

Und das genügt als Beweis? Augenzwinkern

Augenzwinkern

Das ist doch irgendwie...naja - wenig. Augenzwinkern

Augenzwinkern

Wie könnte man das denn gut auformulieren?

04.11.2008, 16:44

AD

Auf diesen Beitrag antworten »

Wenn man's kann, ja. Aber die große Souveränität hast du ja nicht gerade ausgestrahlt, dass du dir diese Bemerkung erlauben darfst. Augenzwinkern

Augenzwinkern

Außerdem nehme ich an, dass es nur eine Aufgabe der 1.Runde war. In der 2.Runde sollte es schon deutlich härter sein.

04.11.2008, 18:14

studiersti

Auf diesen Beitrag antworten »

So war das auch absolut nicht gemeint. smile

smile

Aber mir ging es nur noch darum, diesn gesamtem Vorgang noch auszuformulieren...ohne Worte sieht das schon nach recht wenig aus und ich wüsste auch nicht, wie ich die gesamte Beweisführung in Formeln o.ä. fassen könnte.

Ich würde das noch einmal gerne zusammenfassen:

Wir haben 100 beliebige Zahlen, also 100 Objekte n (Element der ganzen Zahlen).

Da man die Differenz zweier beliebiger Zahlen durch 7 teilen will, teilt man die Zahlen in 7 Kategorien ein, weil die Zahlen nur den Rest 0, 1, 2, 3, 4, 5 oder 6 haben können.

Durch das Schubfachprinzip kommt man jetzt auf: 100/7=15, was zeigt, dass es mindestens eine Restklasse modulo 7 mit mindestens 15 Zahlen gibt.
Und die Differenz von zwei Zahlen aus derselben Restklasse muss durch 7 teilbar sein.

Ist das so in Ordnung?

04.11.2008, 18:56

AD

Auf diesen Beitrag antworten »

Das "100/7=15" kann man natürlich nicht so stehen lassen, da es falsch ist - besser korrekt mit der Aufrundungsfunktion formulieren: $\begin{eqnarray*} \left\lceil \frac{100}{7} \right\rceil = 15 \end{eqnarray*}$

Ansonsten ist die Argumentation soweit Ok.

05.11.2008, 20:33

schmouk

Auf diesen Beitrag antworten »

Ui, da ist einer bei Prof. Baur in Algebra I. Nabend Leidensgenosse.

Also die Aufgabenstellung lautet ja nun: Kann man aus 100 beliebig gegebenen ganzen Zahlen... etc.pp.

Als wenn jetzt 100 Zahlen beliebig gewählt werden, die aber wie folgt aussehen: {2,4,2,4,2,4,2,4...2,4}

Also nur aus z.B. nur aus zweien und vieren bestehen. dann kann ich mir ja 15 auswählen wie ich will, und ich werden auch 2 Paar finden: nämlich 7 teilt 2-2=0 und 7 teilt 4-4=0 aber ich werde auf jeden fall innerhalbe der 15 ausgewählten aus die Differenz von 2 und 4 bilden können und 7 teilt eben nicht 2-4=-2.

Ist das nicht ein Gegenbeweis?

Ich meine gut, man könnte auch einwänden: jaaa, aber ich kann ja trotzdem aus den 100 Zahlen 15 Vieren auswählen und innerhalb dieser 15 teilt 7 immer die Differenz zweier beliebiger Zahlen aus den 15.

So? Oder nicht so?

05.11.2008, 20:36

studiersti

Auf diesen Beitrag antworten »

welche ü-gruppe? Augenzwinkern

Augenzwinkern

05.11.2008, 21:10

schmouk

Auf diesen Beitrag antworten »

Dutzig

Augenzwinkern

Ich will nochmal versuchen, zu artikulieren was da passiert:

In 100 beliebigen Zahlen finde ich für (mod 7) immer eine Gruppe mit 15 Elementen.
Begründung: Eine Zahl der 100 muss für mod 7 einen Rest mit 0<=x<=6 haben.
Daraus folgt: Es gibt maximal 7 Gruppen.

Sind die Zahlen möglichst gleichmäßig auf die Gruppen verteilt, so müssen die Gruppen aus mindestens 14 Elementen bestehen. 7*14=98 rest 2 => 7 14er Gruppen gibt es bereits und 2 weitere Zahlen die aber je mit mod 7 "behandelt" wieder ein Restwert von 0-6 haben müssen und somit wieder einer 14er Gruppe zugeordnet werden können.

Das bedeutet, dass es bei möglichst gleichmäßiger Verteilung mindesten zwei 15er Gruppen mit jeweils dem gleichen Restwert für mod 7.

Sollte der Fall eintreten, dass eine "modulogruppe" nicht existiert: also z.B. die für Rest 5. Es gibt also innerhalb der 100 Zahlen keine Zahl, die geteilt durch 7 den Restwert 5 hat, so ist das nicht schlimm, da dadurch die weiteren Modulogruppen größer werden und so auf jeden Fall mindestens 15 Elemente fassen.

Kann ich jetzt innerhalb dieser 15er Gruppe 2 belieb gewählte Zahlen durch 7 mit Rest 0 teilen?

Ja, weil die Differenz zweier Zahlen mit dem selben Restwert für mod 7, für mod 7 den Restwert 0 haben muss:

Beweis

p,s aus Z

a=p*7+r
b=s*7+r

a-b=(p*7+r)-(s*7+r)
=p7+r-s7-r
=p7-s7=7(p-s)

7 teilt 7(p-s) rest 0

haha, na was sagt Ihr. Hab ich das verstanden? Gut oder gut?

schmouk

05.11.2008, 21:12

studiersti

Auf diesen Beitrag antworten »

ah, ok. Die kenne ich nicht.

hast du ein messenger Programm? Augenzwinkern

Augenzwinkern

05.11.2008, 21:13

AD

Auf diesen Beitrag antworten »

Zitat:

Original von schmouk
Hab ich das verstanden? Gut oder gut?

Nein, eher schlecht: Es gibt keineswegs immer "mindestens zwei 15er Gruppen" - Gegenbeispiel: Die 100 Zahlen

7, 14, 21, ... , 693, 700

Da liegen alle 100 Zahlen in derselben Restklasse 0 mod 7. Augenzwinkern

Augenzwinkern

05.11.2008, 21:45

schmouk

Auf diesen Beitrag antworten »

Dann hast du nicht richtig gelesen mein Junge,

ich schrieb:

code:
1:	Das bedeutet, dass es bei >>möglichst gleichmäßiger Verteilung<< mindesten zwei 15er Gruppen mit jeweils dem gleichen Restwert für mod 7.

Klar, wenn ich nur eine Modulogruppe für mod 7 = 0 habe, stimmt das, dann habe ich nur eine Gruppe mit min 15.

Weitere Fehler?

05.11.2008, 21:55

AD

Auf diesen Beitrag antworten »

Zitat:

Original von schmouk
Dann hast du nicht richtig gelesen mein Junge,

Oh, na dann vielen Dank für deine Belehrung. smile

smile

Ich bin in Zukunft gespannt, ob dein mathematisches Können mit deinem unverschämten Selbstbewusstsein schritt halten kann. In diesem Thread hast du mich davon noch nicht überzeugt, deine Überlegungen sind angesichts der bereits vorhandenen wasserdichten Lösung "völlig zweckfrei" (Zitat Loriot) ... Big Laugh

Big Laugh

EDIT: Sorry, Schmouk, ich hatte mich die ganze Zeit gefragt, warum du oben überhaupt gepostet hast. Aber jetzt verstehe ich, da ich gerade eben dein Profil gelesen habe: Als Philosoph fühlst du dich dazu verpflichtet, auch bei völlig geklärtem Sachverhalt noch lang und breit darüber zu labern ... verzeih, zu philosophieren.

Ich leg jetzt erstmal die EAV-Scheibe "Nie wieder Kunst" in meinen CD-Player:

"Philosophen - meistens g'soffen
wozu seid ihr da?"

smile

smile

07.11.2008, 16:27

schmouk

Auf diesen Beitrag antworten »

ROFL

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »