Vorbereitung auf die Mathematik Olympiade - Seite 2

20.06.2008, 18:20

mathe760

Ja aber ich brauch so eine Art Stichwort, wie ich zeigen kann das es unendlich solcher Tribel gibt.

Oder soll ich einfach so beginnen:

$\begin{eqnarray*} x_1^3+y_1^3=x_2^3+y_2^3=z^4\Rightarrow x_1^3-x_2^3+(y_1^3-y_2^3)=z^4 \end{eqnarray*}$

Ich glaube nicht oder?

Bis denn mathe760 Wink

20.06.2008, 18:30

Auf diesen Beitrag antworten »

Du gibst einfach unendlich viele Tripel direkt an - das ist der einfachste Weg.

Löse doch erstmal das erste Problem $\begin{eqnarray*} x^3+y^3=9^4 \end{eqnarray*}$ , d.h., eigentlich musst du nur eine Lösung (x,y) davon angeben, nicht alle. Die ganz scharf angeschaut, vielleicht ein wenig auf die Potenzgesetze geschaut, sollte dich irgendwann auf eine Idee bringen.

Erinnert mich an folgende Aufgabe aus meiner aktiven Zeit:

Zitat:

Man untersuche, ob es keine, endlich viele oder unendlich viele 5-Tupel $\begin{eqnarray*} (x_1,x_2,x_3,x_4,x_5) \end{eqnarray*}$ von positiven ganzen Zahlen gibt, für die die folgende Gleichung erfüllt ist:

$\begin{eqnarray*} x_1^3+x_2^5+x_3^7+x_4^{11}=x_5^{13} \end{eqnarray*}$

Die sieht nur auf den ersten Blick abschreckender aus, kann aber mit ähnlichen Prinzipien wie die hier gelöst werden.

20.06.2008, 18:54

mathe760

Auf diesen Beitrag antworten »

Also ich habe jetzt die Lösung (x,y,z)=(9,18,9)

aber da sind x,y,z ja nicht paarweise verschieden und ich wüsste jetzt auch nur das:

$\begin{eqnarray*} x^3+y^3=z^4=z\cdot z^3=\sqrt[4]{x^3+y^3} \cdot \sqrt[4]{(x^3+y^3)^3} =(x^3+y^3)^{\frac{1}{4}} \cdot (x^3+y^3)^{\frac{3}{4}} \end{eqnarray*}$

Aber da drehe ich mich doch im Kreis!

Bis denn mathe760 Wink

20.06.2008, 18:58

Auf diesen Beitrag antworten »

Zitat:

Original von mathe760
aber da sind x,y,z ja nicht paarweise verschieden

Das wird bei der a) nicht gefordert.

Überleg doch mal, ob du aus dem bei a) genutzen $\begin{eqnarray*} 1^3+2^3=3^2 \end{eqnarray*}$ nicht noch mehr rausholen kannst, etwa indem du geeignete Ansätze für $\begin{eqnarray*} x,y,z \end{eqnarray*}$ wählst. Also für mich springt nach Teilaufgabe a) der Ansatz

$\begin{eqnarray*} x=3^s,y=2\cdot 3^s,z=3^t \end{eqnarray*}$

geradezu ins Auge.

20.06.2008, 19:13

mathe760

Auf diesen Beitrag antworten »

naja aber $\begin{eqnarray*} 1^3+2^3=3^2+ \end{eqnarray*}$ habe ich garnicht verwendet bei a)
Auf x=3^s bist du doch gekommen, damit die Basen x,y,z übereinstimmen oder? Wie kann man denn zeigen das alle Lösungen diese Form haben, das soll ich jetzt vermutlich zeigen oder?

Aber gut ich werde mir das heute Abend nochmal angucken und dann nochmal schreiben.

Schönen Abend wünsche ich dir noch smile

Bis denn mathe760 Wink

20.06.2008, 19:21

Auf diesen Beitrag antworten »

Zitat:

Original von mathe760
Wie kann man denn zeigen das alle Lösungen diese Form haben

Du hörst überhaupt nicht zu, oder?

Zitat:

Original von Arthur Dent
Dran denken: Es wird nur gefordert, bei $\begin{eqnarray*} x^3+y^3=z^4 \end{eqnarray*}$ unendlich viele Lösungen anzugeben. Wenn da stehen würde "alle Lösungen", wäre die Aufgabe um Größenordnungen schwerer.

20.06.2008, 19:23

mathe760

Auf diesen Beitrag antworten »

Stimmt daran habe ich nicht gedacht, naja dann verabschiede ich mich mal für Heute.

Schönen Abend noch smile

Bis denn mathe760 Wink

25.06.2008, 16:31

mathe760

Auf diesen Beitrag antworten »

Ich habe leider überhaupt keine Ahnung wie ich aus dieser einen Lösung heraus zeigen kann, dass es unendlich viele Lösungstripel (x,y,z) gibt. verwirrt

Bis denn mathe760 Wink

25.06.2008, 16:37

tmo

Auf diesen Beitrag antworten »

Ich zeige dir mal, wie man beweisen könnte, dass es unendlich viele pythagoräische Zahlentripel gibt:

Man geht von $\begin{eqnarray*} 3^2+4^2=5^2 \end{eqnarray*}$ aus und multipliziert mit $\begin{eqnarray*} n^2 \end{eqnarray*}$ :

$\begin{eqnarray*} (3n)^2+(4n)^2 = (5n)^2 \end{eqnarray*}$

Und schon hat man unendlich viele Tripel $\begin{eqnarray*} (3n,4n,5n) \end{eqnarray*}$ gefunden.

Ähnlich kannst du es hier auch machen. Geh von deiner einen Lösung aus und multipliziere geschickt.

PS: Sorry, falls ich mich hier eingemischt habe, aber man weiß ja nicht ob du online bist Arthur Dent smile

25.06.2008, 16:41

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Sorry, falls ich mich hier eingemischt habe, aber man weiß ja nicht ob du online bist Arthur Dent smile

Es gibt hier keine Privatthreads, also kein Grund für irgendwelche Entschuldigungen. Ich bin ganz im Gegenteil erleichtert, wenn sich hier mal paar Leute mehr äußern. Freude

Zitat:

Original von Arthur Dent
Also für mich springt nach Teilaufgabe a) der Ansatz

$\begin{eqnarray*} x=3^s,y=2\cdot 3^s,z=3^t \end{eqnarray*}$

geradezu ins Auge.

Den Ansatz einfach mal in die Gleichung eingesetzt ergibt links

$\begin{eqnarray*} x^3+y^3 = 3^{3s} + 8\cdot 3^{3s} = 9\cdot 3^{3s} = 3^{3s+2} \end{eqnarray*}$

und rechts einfach $\begin{eqnarray*} z^4 = 3^{4t} \end{eqnarray*}$ . D.h., der Ansatz führt dann und nur dann zu Lösungen, wenn die Exponenten übereinstimmen, also

$\begin{eqnarray*} 3s+2 = 4t\qquad (*) \end{eqnarray*}$ .

Damit hast sich das Problem auf die Frage reduziert, ob es unendlich viele Paare nichtnegativer ganzer Zahlen $\begin{eqnarray*} (s,t) \end{eqnarray*}$ mit Eigenschaft (*) gibt. Und das kann man selbst mit einfachen Kenntnissen der Zahlentheorie bejahen - am besten gibt man natürlich diese Paare ganz konkret an. Wie ich oben schon sagte, der Ansatz liefert keineswegs alle Lösungen der Gleichung, sondern "nur" unendlich viele - aber das reicht ja für die vorliegende Problemstellung aus.

25.06.2008, 17:01

mathe760

Auf diesen Beitrag antworten »

Gut Danke, ich denke das kann ich lösen, ich poste dann später.

Bis denn mathe760 Wink

26.06.2008, 19:23

mathe760

Auf diesen Beitrag antworten »

Geht es so:

$\begin{eqnarray*} 4t-3s=2 (*) \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow (4t-3s)\equiv 0 (mod2) \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow 4t\equiv 3s (mod2) \end{eqnarray*}$

Da nun gilt $\begin{eqnarray*} 4t=2\cdot 2t\equiv 0 (mod2) (**) \end{eqnarray*}$
folgt $\begin{eqnarray*} 3s\equiv 0 (mod2) (***) \end{eqnarray*}$

(**) hat unendlich viele Lösungen für t, nämlich alle natürlichen Zahlen.

(***) hat ebenfalls unendlich viele Lösungen für s, nämlich alle geraden, natürlichen Zahlen.

Damit ist gezeigt, dass es unendlich viele Lösungspaare (s,t) gibt für die (*) erfüllt ist. q.e.d.

Wie macht man nochmal das "ist äequivalent zu" Zeichen?
Bis denn mathe760 Wink

26.06.2008, 19:31

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von mathe760
$\begin{eqnarray*} 4t-3s=2 (*) \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow (4t-3s\equiv 0 (mod2) \end{eqnarray*}$

Diese Implikation stimmt, hilft dir aber nicht weiter. Denn die andere Richtung (die du bräuchtest) gilt nicht.

$\begin{eqnarray*} 3s+2=4t \end{eqnarray*}$ kann doch nur dann erfüllt sein, wenn $\begin{eqnarray*} 3s \equiv 2 \pmod 4 \end{eqnarray*}$ gilt.

Da 3 eine Primzahl ist, ist das genau dann der Fall, $\begin{eqnarray*} s \equiv 2 \pmod 4 \end{eqnarray*}$ gilt.

Nun hat Arthur Dent dir gesagt, du sollst die Lösungstupel am besten direkt angeben, sprich in der Form $\begin{eqnarray*} (s,t) = (s(n),t(n)) \end{eqnarray*}$ , sodass für jedes n eine Lösung geliefert wird.

Wie könnte $\begin{eqnarray*} s(n) \end{eqnarray*}$ aussehen wenn $\begin{eqnarray*} s \equiv 2 \pmod 4 \end{eqnarray*}$ gelten muss?

29.06.2008, 10:39

mathe760

Auf diesen Beitrag antworten »

Darauf hätte ich auch kommen müssen, dass mein Beweis nicht in beiden Richtungen gilt (was er ja müsste). Hammer

@tmo: könnte s(n) vielleicht so aussehen:

$\begin{eqnarray*} s(n)= 4\cdot n+2 \end{eqnarray*}$ mit $\begin{eqnarray*} n\in \mathbb N \end{eqnarray*}$ ?

Dann müsste $\begin{eqnarray*} t(n)=3\cdot n+2 \end{eqnarray*}$ sein oder?

Ich denke damit wäre der Beweis abgeschlossen?! q.e.d.

Bis denn mathe760 Wink

30.06.2008, 13:09

Auf diesen Beitrag antworten »

Strenggenommen muss man noch zeigen, dass die Zahlen

$\begin{eqnarray*} x=3^{4n+2},\quad y=2\cdot 3^{4n+2},\quad z=3^{3n+2} \end{eqnarray*}$

auch tatsächlich paarweise verschieden sind. Für $\begin{eqnarray*} n=0 \end{eqnarray*}$ sind sie das nicht (siehe Aufgabe a)), aber für $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ schon, was leicht aus $\begin{eqnarray*} 4n+2>3n+2 \end{eqnarray*}$ für diese $\begin{eqnarray*} n \end{eqnarray*}$ folgt.

30.06.2008, 19:21

mathe760

Auf diesen Beitrag antworten »

Gut also wo kann ich bei Aufgabe a) denn sehen das n=0 nicht dazugehört? Gut es ist trivial aber wo hast du das bei a) gesehen?

Für $\begin{eqnarray*} n\geq1 \end{eqnarray*}$ ist es doch auch trivial, oder irre ich da?

Kann ich das dann einfach so hinschreiben, das die beiden Fälle trivial sind, hauptsache ich gebe sie an?

Ich habe da noch sehr viele Aufgaben, aber erstmal die hier:

"Es stehen sechs gleich große (ungefärbte) Holzwürfel und drei verschiedene Farben zur Verfügung. Auf jedem der Würfel sollen genau drei Seitenflächen mit je einer Farbe vollständig bemalt werden. Dabei sollen auf jedem Würfel alle drei Farben verwendet werden. Ist es möglich, die sechs Würfel auf die vereinbarte Art so zu bemalen, dass danach jeder Würfel von jedem anderen unterscheidbar ist?

Hinweis: Zwei gefärbte Würfel heißen dabei nicht unterscheidbar, wenn man sie durch Drehung und/oder Verschiebung so ineinander überführt denken kann, dass gleich gefärbte Seitenflächen aufeinander liegen."

Meine Lösung:

6 Holzwürfel, 3 verschiedene Farben.
3 Seiten jedes Würfels werden mit je einer von den anderen verschiedenen Farbe bemalt.

Da es genau $\begin{eqnarray*} \begin{pmatrix} 6 \\3 \\ \end{pmatrix} =20 \end{eqnarray*}$ Möglichkeiten gibt die 3 Farben so auf die Würfel zu platzieren, dass jeder Würfel von jedem anderen unterscheidbar ist, gilt insbesondere das es Möglich ist die 6 Würfel so zu bemalen, dass sie voneinander unterscheidbar sind.

Nun meine Frage: Habe ich hier den Hinweis berücksichtigt?
Und wenn nein, wie könnte ich dies tun?

Bis denn mathe760 Wink

30.06.2008, 20:49

Auf diesen Beitrag antworten »

Zitat:

Original von mathe760
Gut also wo kann ich bei Aufgabe a) denn sehen das n=0 nicht dazugehört? Gut es ist trivial aber wo hast du das bei a) gesehen?

Für $\begin{eqnarray*} n=0 \end{eqnarray*}$ ist $\begin{eqnarray*} (x,y,z)=(9,18,9) \end{eqnarray*}$ , da hattest du selbst doch irgendwo oben festgestellt, dass das keine Lösung für b) sein kann, weil da eben $\begin{eqnarray*} x=z \end{eqnarray*}$ ist!

Zitat:

Original von mathe760
Nun meine Frage: Habe ich hier den Hinweis berücksichtigt?

Kurz gesagt: Nein.

Allerdings ist 20 wiederum auch nicht die Anzahl für einen starr positionierten Würfel (also ohne Drehungen). Die wäre $\begin{eqnarray*} \frac{6!}{3!} = 120 \end{eqnarray*}$ .

Zitat:

Original von mathe760
Und wenn nein, wie könnte ich dies tun?

Auf wieviel Arten kann man denn einen Würfel "verdrehen" ? Oder anders gesagt: Wieviel der o.g. "starren" Färbungen gehören zu ein- und derselben Dreh-Äquivalenzklasse?

----------------

Allerdings gibt es auch noch eine banalere Abzählmöglichkeit: Die drei Farben seien rot, grün, blau.

Dreh den Würfel so, dass die rote Seitenfläche vorn ist. Für die blaue Seitenfläche gibt es jetzt zwei Fälle:

1.Sie ist der roten Seite benachbart. Dann kann man den Würfel so drehen, dass diese blaue Seite oben ist. Wieviel unterscheidbare Möglichkeiten gibt es jetzt noch für die fehlende grüne Seite? Diese Anzahl ist auch die Anzahl der Färbungen in diesem Unterfall.

2.Sie ist der roten Seite gegenüberliegend. In dem Fall kann man den Würfel so drehen, dass die dritte grüne Seite oben ist. In diesem Unterfall gibt es also nur eine Färbung.

Man darf sich auch für eine solche Tippeltappeltour nicht zu schade sein, wenn man keine anderen Ideen hat.

02.07.2008, 17:19

mathe760

Auf diesen Beitrag antworten »

Es gibt 6 möglichkeiten einen Würfel aus der starren Position heraus zu drehen daher gibt es noch $\begin{eqnarray*} \frac{120}{6} =20 \end{eqnarray*}$ voneinender unterscheidbare Würfel Bemalungen, insbesondere ist es also in jedem Fall Möglich sechs Würfel so zu bemalen, dass sie voneinander unterscheidbar sind. q.e.d.

Ist es so richtig oder habe ich einen Denkfehler?

Da ich etwas in Zeitnot geraten bin hier gleich noch die nächste Aufgabe:

"Ralf Reisegern erzählt seinem Freund Markus, einem Mathematiker, dass er in diesem Jahr schon acht Länder der Währungsunion bereist habe. Um seine fünf Kinder für die neuen Cent- und Euro- Münzen zu begeistern, hat er aus jedem der qcht Länder fünf (nicht notwendig verschiedene) Münzen mitgebracht. Weil die Kinder auch in Deutschland mit den Münzen bezahlen können, hat Ralf darauf geachtet, dass unter den 40 Münzen auch jeder der acht Werte (1,2,5,10,20 und 50 Cent, 1 und 2 Euro) genau fünfmal vorkommt. Er hofft nun, jedem Kind acht Münzen schenken zu können, aus jedem Land eine und so, dass jedes Kind Münzen im Gesamtwert von 3,88 Euro erhält. Doch Ralf hat schon einige Zeit erfolglos probiert, die Münzen aufzuteilen. "Das muss aber gehen!" behauptet Markus, ohne sich die Münzen genauer anzuschauen.
Beweisen oder widerlegen Sie diese Behauptung."

Mein Lösungsansatz:

8 Länder
40 Münzen: 5 x 1 Cent, 5 x 2 Cent, 5 x 5 Cent, 5 x 10 Cent, 5 x 20 Cent, 5 x 50 Cent, 5 x 1 Euro, 5 x 2 Euro.

Verteilung der Münzen an ein Kind:

$\begin{eqnarray*} \begin{pmatrix} 8 \\ 1 \\ \end{pmatrix}\cdot \begin{pmatrix} 7 \\ 1 \\ \end{pmatrix}\cdot \begin{pmatrix} 6 \\ 1 \\ \end{pmatrix}\cdot \begin{pmatrix} 5 \\ 1 \\ \end{pmatrix}\cdot \begin{pmatrix} 4 \\ 1 \\ \end{pmatrix}\cdot \begin{pmatrix} 3 \\ 1 \\ \end{pmatrix}\cdot \begin{pmatrix} 2 \\ 1 \\ \end{pmatrix}\cdot \begin{pmatrix} 1 \\ 1 \\ \end{pmatrix} =8! \end{eqnarray*}$

oder geht es um Wahrscheinlichkeiten? Dann komme ich auf eine Wahrscheinlichkeit von 0,064341%

Ich komme echt nicht mehr weiter, was soll ich denn jetzt berechnen?

Bis denn mathe760 Wink

02.07.2008, 17:38

Auf diesen Beitrag antworten »

Zitat:

Original von mathe760
Es gibt 6 möglichkeiten einen Würfel aus der starren Position heraus zu drehen daher gibt es noch $\begin{eqnarray*} \frac{120}{6} =20 \end{eqnarray*}$ voneinender unterscheidbare Würfel Bemalungen, insbesondere ist es also in jedem Fall Möglich sechs Würfel so zu bemalen, dass sie voneinander unterscheidbar sind. q.e.d.

Ist es so richtig oder habe ich einen Denkfehler?

Ich komme nur auf 5 drehungsinvariante Färbungen, denn es gibt 24 Möglichkeiten, den Würfel zu drehen! Besorg dir mal einen Rubik-Würfel, dann siehst du es... smile

Zur anderen Aufgabe: Es geht dort nicht um Wahrscheinlichkeiten oder Abzählen - es geht darum, ob unter den gegebenen Voraussetzungen eine so gewünschte Aufteilung der Münzen an die Kinder überhaupt möglich ist - oder nicht.

02.07.2008, 17:53

mathe760

Auf diesen Beitrag antworten »

ich sitze gerade mit einem unglücklich

Wie kommst du denn auf 5 und 24? Also ich zähle waagereche Drehungen: 3 und Horizontale Drehungen: 3 also 3+3=6 verwirrt

Bis denn mathe760 Wink

02.07.2008, 18:53

Auf diesen Beitrag antworten »

Halte den Würfel mal vor dich hin: Jede der 6 Farben kann jetzt vorn sein - ergibt 6 Möglichkeiten. Und für jede dieser 6 Möglichkeiten gibt es jetzt 4 Drehungen (0, 90, 180, 270 Grad) mit Drehachse Mittelpunkt Vorderseite - Mittelpunkt Rückseite. Macht 4*6=24 Möglichkeiten. Forum Kloppe

Aber weißt du, warum soll ich mich streiten: Zeig mir einfach mal 6 angeblich unterscheidbare Färbungen, und ich nenne dir anschließend zwei (nach Schubfachprinzip Big Laugh

) davon, die dann doch durch Drehung ineinander überführbar sind. smile

03.07.2008, 17:19

mathe760

Auf diesen Beitrag antworten »

Vielen Dank!

Nee lass mal ich finde ja doch keine 6 wenn es nur 5 gibt smile

Die andere gucke ich mir auch gleich nochmal an.

Mal nebenbei: Soll man in der 9. Klasse auch Funktionaltheorie können?

Bis denn mathe760 Wink

03.07.2008, 17:54

mathe760

Auf diesen Beitrag antworten »

Lösung zu der Münz-Aufgabe:

Die einzige Möglichkeit den Wert 3,88 Euro aus acht den vorgegebenen vierzig Münzen zusammenzustellen, ist jede der acht verschiedenen Münzen je einmal auszuwählen.
Damit ist es möglich die vierzig Münzen auf die fünf Kinder zu verteilen, sodass jedes Kind den Geldbetrag 3,88 Euro erhält. Nämlich indem Ralf Reisegern jedem der fünf Kinder je eine der acht verschiedenen Münzen zu geben.
q.e.d.

Ist das richtig aufgeschrieben oder überhaupt richtig gedacht?

Bis denn mathe760 Wink

03.07.2008, 19:50

Auf diesen Beitrag antworten »

Es gibt aber nicht nur die Bedingung, dass jedes Kind alle 8 Münzwerte je einmal bekommen soll - es soll auch Münzen aus allen 8 verschiedenen Ländern bekommen. Das ist doch gerade der Witz an der Aufgabe, und dass das möglich ist (was es tatsächlich ist!) erschließt sich mir aus deiner Begründung noch nicht so richtig. verwirrt

08.07.2008, 18:02

mathe760

Auf diesen Beitrag antworten »

So ich bin jetzt erstmal nach etwas Überlegung zu den Schluss gekommen, dass ich eíne Fallunterscheidung mit 5 Fällen machen muss.

Ist das richtig?

Bis denn mathe760 Wink

08.07.2008, 20:48

Auf diesen Beitrag antworten »

Zitat:

Original von mathe760
Ist das richtig?

Woher soll ich das wissen, wenn ich nicht weiß, worum es in den 5 Fällen geht?

Bei der Aufgabe gibt es sicher viele mögliche Lösungswege.

09.07.2008, 12:46

mathe760

Auf diesen Beitrag antworten »

Also hier sind meine 5 Fälle:

1.Fall: Mindestens ein Land hat zwei mal dieselbe Münzart. --> Schupfachprinzip(?)

2.Fall: Mindestens ein Land hat drei mal dieselbe Münzart-.

3. Fall Mindestens ein Land hat vier mal dieselbe Münzart.

4. Fall: Ein Land hat fünf mal dieselbe Münzart.

5. Fall: Alle fünf Münzen aller Länder sind von verschiedener Art.

Aber fehlt da dann nicht zum Beispiel der Fall: In Land A sind die Münzen 2€,2€1€,10Cent,10Cent.

Was mache ich da?

Bis denn mathe760 Wink

09.07.2008, 14:53

Auf diesen Beitrag antworten »

Zitat:

Original von mathe760
Aber fehlt da dann nicht zum Beispiel der Fall: In Land A sind die Münzen 2€,2€1€,10Cent,10Cent.

Das wäre ja dein 1.Fall.

Was ich nicht verstehe ist, inwieweit diese Fallunterscheidung bei der Lösung der Aufgabe hilft? Davon sehe ich bis jetzt nichts weit und breit.

----------------------------------

Nochmal von vorn, wie ich es anpacken würde:

Der Vater bringt 40 Münzen mit, und jede der Münzen kann man unter den zwei Gesichtspunkten "Münzwert" sowie "Herkunftsland" einordnen:

Und in der Hinsicht kann man der Aufgabe entnehmen, dass aus jedem der acht Länder genau fünf Münzen dabei sind. Ebenso ist jeder der acht Münzwerte (von 1ct bis 2€) mit jeweils fünf Münzen vertreten. Und nun soll so aufgeteilt werden, dass jedes Kind mit seinen zugeteilten acht Münzen sowohl jeden Münzwert aber auch jedes Land erhalten hat!

Meines Erachtens ist das nicht trivial. Es gibt verschiedene Betrachtungsweisen für das Problem (wohl auch Graphentheorie, so man da fit ist), ich würde es allgemeiner so fassen:

Zitat:

Es sei $\begin{eqnarray*} A=(a_{i,j})_{i,j=1,\ldots,n} \end{eqnarray*}$ eine quadratische $\begin{eqnarray*} n\times n \end{eqnarray*}$ -Matrix nichtnegativer ganzer Zahlen, üblicherweise kann man auch $\begin{eqnarray*} A\in \mathbb{N}_0^{n\times n} \end{eqnarray*}$ dafür schreiben. Von dieser Matrix sei bekannt, dass sämtliche Zeilen- und Spaltensummen positiv und einander gleich seien, d.h., es gibt ein $\begin{eqnarray*} m>0 \end{eqnarray*}$ mit

$\begin{eqnarray*} \sum_{i=1}^n a_{ik} = \sum_{j=1}^n a_{kj} = m \end{eqnarray*}$ für alle $\begin{eqnarray*} k=1,\ldots,n \end{eqnarray*}$ .

Man zeige, dass es unter diesen Voraussetzungen eine Permutation $\begin{eqnarray*} \pi \end{eqnarray*}$ von $\begin{eqnarray*} \{1,\ldots,n\} \end{eqnarray*}$ gibt, für die

$\begin{eqnarray*} a_{i,\pi(i)} > 0 \end{eqnarray*}$ für alle $\begin{eqnarray*} i=1,\ldots,n \end{eqnarray*}$

gilt.

Bezogen auf unsere Aufgabenstellung ist $\begin{eqnarray*} n=8 \end{eqnarray*}$ , wo z.B. die Zeilen die Länder und die Spalten die Münzwerte repräsentieren. Wenn wir erstmal gemäß Aufgabenstellung von $\begin{eqnarray*} m=5 \end{eqnarray*}$ ausgehen, dann können wir bei Anwendung dieses Satzes das erste Kind mit passenden Münzen versorgen. Ziehen wir diese 8 Münzen von den 40 Münzen ab, dann erfüllen die restlichen Münzen wiederum die Voraussetzung des Satzes, aber mit diesmal $\begin{eqnarray*} m=4 \end{eqnarray*}$ . Jetzt können wir das nächste Kind versorgen usw.

D.h., der Beweis dieses Satzes würde Aufgabe erledigen. Das wäre mein Zugang - möglicherweise zu kompliziert, aber machbar.

10.07.2008, 15:11

mathe760

Auf diesen Beitrag antworten »

Zitat:

Man zeige, dass es unter diesen Voraussetzungen eine Permutation $\begin{eqnarray*} \pi \end{eqnarray*}$ von $\begin{eqnarray*} \{1,\ldots,n\} \end{eqnarray*}$ gibt, für die

$\begin{eqnarray*} a_{i,\pi(i)} > 0 \end{eqnarray*}$ für alle $\begin{eqnarray*} i=1,\ldots,n \end{eqnarray*}$

gilt.

Was genau heißt das? Ich kann ja schlecht einen Satz beweisen, von dem ich nicht genau weiß, was er aussagt. geschockt

Ich dachte man kann die Aufgabe auch wie eine aus der 1. Stufe anpacken oder geht dies nicht?
Kannst du mir nicht doch einen einfacheren/naheliegenderen Ansatz geben?

Ich finde es echt super das du mir so bereitwillig hilfst und so viel geduld mit mir hast. Ich möchte halt gerne so gut wie nur möglich vorbereitet sein.

Das mit meinen Fällen war einfach einen Ansatz den ich irgendwann bekommen habe, und von dem ich eigentlich dachte, das er mich auf die ein oder andere Weise zur Lösung führt.

Bis denn mathe760 Wink

10.07.2008, 15:25

Auf diesen Beitrag antworten »

Zitat:

Original von mathe760

Zitat:

Was genau heißt das? Ich kann ja schlecht einen Satz beweisen, von dem ich nicht genau weiß, was er aussagt.

Ich verstehe deine Ideen nicht, und du nicht die mathematische Symbolik - schwer, eine gemeinsame Sprache zu finden. unglücklich

Da steht nichts weiter, als dass man für jede der n Zeilen einen positiven Matrixwert innerhalb dieser Zeile finden kann in der Art, dass dann auch jede Spalte belegt ist. Also ähnlich wie beim Turmproblem im Schach, wo man die 8 Türme so stellt, dass keiner den anderen schlagen kann.

Beispiel: Wenn z.B. die Matrixelemente

$\begin{eqnarray*} a_{1,2},a_{2,4},a_{3,7},,a_{4,3},a_{5,1},a_{6,8},a_{7,6},a_{8,5} \end{eqnarray*}$

positiv sind, dann erfüllt die Permutation $\begin{eqnarray*} \pi = (2,4,7,3,1,8,6,5) \end{eqnarray*}$ die Satzaussage.

10.07.2008, 15:45

mathe760

Auf diesen Beitrag antworten »

Tut mir ja Leid, aber mit Matrixen hab e ich mich noch nicht wirklich viel beschäftigt, dennoch versuche ich mal den Satz zu Beweisen. Kannst du mir dann danach einen einfacheren Weg zeigen?

Hab ich das richtig verstanden, dass ich mir die Zeilen als die acht Länder und die Spalten als die acht Münzen vorstellen kann? Wie summiert man denn bitte Länder auf, dass verstehe ich nicht. verwirrt

Ich finde es echt zum heulen, man lernt in Mathe echt gar nichts in der Schule! traurig

Bis denn mathe760 Wink

10.07.2008, 15:58

Auf diesen Beitrag antworten »

Zitat:

Original von mathe760
dennoch versuche ich mal den Satz zu Beweisen.

Nein, tu das nicht. Ich hatte gedacht, der wäre einfach, aber deine Nachfragen belehren mich, dass dem nicht so ist.

Ich hab leider das Gefühl, dir fehlt jegliches Problembewusstsein für diese Aufgabe. Mal ein Test, ganz ohne Matrix:

Angenommen, wir wissen nur, dass der Vater von jedem Münzwert und auch aus jedem Land jeweils mindestens eine Münze migebracht hat. Kann er dann stets aus dieser (nicht weiter festgelegten) Anzahl Münzen genau acht heraussuchen, dass er zumindest ein Kind in der oben beschriebenen Weise versorgen kann, d.h. dass jedes Land und jeder Münzwert in diesen acht Münzen vertreten ist?

16.07.2008, 19:12

mathe760

Auf diesen Beitrag antworten »

Entschuldigung das ich erst so spät antworte, aber ich hatte mit der Schule zu tun geschockt

.

Also ich würde mal sagen ja, aber so wirklich kann ich das nicht begründen.--> u.U. vielleicht Schupfachprinzip? (Wenn du das Gefühl hast, das ich weiter unten anfangen sollte, wenn das überhaupt möglich ist, dann kannst du mir ja mal einen Tipp geben wo z.B.. Ich habe schließlich, wie oben beschrieben, gerade erst damit begonnen mich mit Wettbewerbsaufgaben zu beschäftigen und ich weiß sehr wohl, dass ich noch einen sehr sehr langen Weg vor mir habe. Dennoch bin ich optimistisch das ich das packen werde. smile

Ab nächste Woche habe ich massenhaft Zeit--> endlich Ferien smile

Bis denn mathe760 Wink

16.07.2008, 19:32

Auf diesen Beitrag antworten »

Die Antwort ist Nein:

Wenn der Vater z.B. sämtliche 8 Münzwerte aus Frankreich mitbringt, und aus den anderen 7 Ländern jeweils die 1ct-Münze, dann kann er nicht mal ein Kind in der geforderten Weise mit 8 Münzen versorgen.

Solche oder ähnliche Beispiele solltest du mal erfassen, um überhaupt ein Gefühl für die Aufgabe zu entwickeln. Das vermisse ich nämlich bei dir.

16.07.2008, 19:38

mathe760

Auf diesen Beitrag antworten »

Kannst du mir vielleicht mal solche Aufgaben geben?

Bis denn mathe760 Wink

30.07.2008, 19:40

mathe760

Auf diesen Beitrag antworten »

Entschuldigung das ich jetzt erst antworte, aber ich war einige Tage weg.

Also habe ich das richtig verstanden, dass die aufteilung nicht für beliebig viele Münzen funktioniert, sondern nur für 40?

Ich habe mich mal mit einer anderen Art von Aufgabe auseinander gesetzt:

"Es seien x,y reele Zahlen mit $\begin{eqnarray*} y \geq 0 \end{eqnarray*}$ und $\begin{eqnarray*} y\cdot (y+1)\leq (x+1)^2. \end{eqnarray*}$ Zeigen Sie, dass dann $\begin{eqnarray*} y\cdot (y-1)\leq x^2 \end{eqnarray*}$ gilt."

Meine Lösung (Ansatz):

Es gilt $\begin{eqnarray*} y\cdot (y+1)\leq (x+1)^2 \end{eqnarray*}$ (1)
und ausserdem trivialerweise $\begin{eqnarray*} (x+1)^2=x^2+2x+1 \leq (x+1)^2 \end{eqnarray*}$ (2)
Somit folgt durch Subtraktion der unteren von der Oberen Ungleichung

$\begin{eqnarray*} y \cdot (y+1)-(x^2+2x+1) \leq 0 \end{eqnarray*}$ $\begin{eqnarray*} \Rightarrow y \cdot(y+1)-(2x+1) \leq x^2 \end{eqnarray*}$
Es ist nun zu zeigen, dass gilt $\begin{eqnarray*} y \cdot (y-1)=y \cdot (y+1)-2y \leq x^2. \end{eqnarray*}$
So und nun kommt wieder der Punkt, wo ich nicht weiß ob ich eine Fallunterscheidung durchführen soll oder nicht.
Also ob ich so untersuchen soll:

!.Fall: 2x+1=2y
2.Fall: y(y+1)-x^2=<2y=<2x+1
3.Fall: y(y+1)-x^2=<2y>=2x+1

Ich weiß die Fälle überschneiden sich gegenseitig, aber dass mache ich damit das mit der Vorraussetzung und dem zu beweisenden "passt".

Bis denn mathe760 Wink

30.07.2008, 19:55

Auf diesen Beitrag antworten »

Ich würde hier eher den simplen naheliegenden Weg wählen:

Die vorausgesetzte Ungleichung nach $\begin{eqnarray*} y \end{eqnarray*}$ auflösen und damit dann die Behauptung beweisen.

30.07.2008, 21:09

mathe760

Auf diesen Beitrag antworten »

Naja aber ich weiß nicht genau wie ich dann die Ungleichung

$\begin{eqnarray*} y\cdot (y+1)-(x+1)^2\leq 0 \end{eqnarray*}$

Ich weiß das die Nullstellen

$\begin{eqnarray*} y_{1,2}=\frac{-1\pm \sqrt{4\cdot (x+1)^2+1} }{2} \end{eqnarray*}$

Nun kann ich mir ja berechnen, dass der Scheitel die Koordinaten $\begin{eqnarray*} (\frac{-1}{2}| -\frac{4\cdot(x+1)^2+1}{4} \end{eqnarray*}$ hat.

Kann ich dann einfach schreiben, dass die Gleichung somit erfüllt ist für $\begin{eqnarray*} y\in [\frac{-1- \sqrt{4\cdot (x+1)^2+1} }{2}; \frac{-1+ \sqrt{4\cdot (x+1)^2+1} }{2}] \end{eqnarray*}$ ?

Aber hilft mir das um das geforderte zu beweisen, mir ist dieser Ansatz nämlich auch sofort eingefallen, konnte ihn aber genau aus diesen Grund nicht ausbauen.

Bis denn mathe760 Wink

30.07.2008, 21:29

Auf diesen Beitrag antworten »

Es ist aber noch mehr gegeben

Zitat:

Original von mathe760
[...] mit $\begin{eqnarray*} y \geq 0 \end{eqnarray*}$

was unbedingt genutzt werden sollte! Denn ohne das ist die Behauptung falsch, wie das Beispiel $\begin{eqnarray*} x=1,y=-2 \end{eqnarray*}$ zeigt.

02.08.2008, 15:33

mathe760

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 0 \leq(x+1)^2 \end{eqnarray*}$

Wenn ich den y_1,2 Wert größßer gleich Null setze, dann erhallte ich x\geq -1

Aber was hilft mir dass, wenn ich dass nämlich in die Ungleichung $\begin{eqnarray*} y\cdot (y+1)\leq (x+1)^2 \end{eqnarray*}$ folgt mit $\begin{eqnarray*} 0 \leq(x+1)^2 \end{eqnarray*}$

$\begin{eqnarray*} y(y+1)\leq 0 \end{eqnarray*}$

Was soll ich jetzt machen, ich weiß nicht wie ich y>=0 in den Beweis einbinden soll, kannst du mir einen kleinen Tipp geben?

Btw: Kennst du vielleicht ein gutes Buch was in olympiade Aufgaben einführt, oder eines über Ungleichungen?

Bis denn mathe760 Wink

« vorherige Seite 1234 nächste Seite »

Neue Frage »

Antworten »

Vorbereitung auf die Mathematik Olympiade - Seite 2

Verwandte Themen