n autos müssen eine Runde fahren

24.10.2011, 17:36

Äqui

n autos müssen eine Runde fahren

Meine Frage:
Hi ich hab leider ein Problem beim Beweisen dieser Aufgabe:

Auf einer runden Rennstrecke stehen n identische Autos. Zusammen haben sie genau
soviel Benzin, wie ein einziges Auto benötigt, um eine ganze Runde fahren zu können.
Ein Auto fährt los, während alle anderen stehen bleiben. Kommt es an einem stehenden
Auto vorbei, dann übernimmt es das Benzin aus dem Tank des stehenden Autos.
Zeigen Sie, dass es ein Auto gibt, das die ganze Runde fahren kann, ohne dass ihm
das Benzin ausgeht.

Meine Ideen:
Das die Ausage (das es immer ein Auto geben muss das die Runde schaft) stimmt weiß ich aber ich kann es leider nicht beweisen Ich hab es über einen Induktions beweis versucht: aber das ergab irgentwie keinen sinn da ich nur für die linkeSeite meiner Berechnung ein n einsetzten konnte
((\sum\limits_{i=1}^n n)=1) wenn einer von euch eine guten Bewis hat den er eklären kann wäre das sehr schön

25.10.2011, 00:49

Dopap

Auf diesen Beitrag antworten »

nicht n Autos fahren eine Runde, sondern 1 Auto fährt eine Runde.

n Autos stehen beliebig auf einer Strecke x_0 . Die Strecke ist ein Rundkurs derart, dass $\begin{eqnarray*} x_0+x = x \end{eqnarray*}$ gilt.
Die n Autos haben die Koordinaten $\begin{eqnarray*} a_i \end{eqnarray*}$

z,B. das Auto n=1 hat den Abstand 0 vom Ursprung x=0

etc.

Ein Auto kann die nächste Distanz $\begin{eqnarray*} a_{i+1}-a_i \end{eqnarray*}$ nur überwinden wenn sein aktuelles Tankvolumen $\begin{eqnarray*} T_i >a_{i+1}-a_i \end{eqnarray*}$ ist, wenn es den Verbrauch 1 je Längeneinheit hat.

der Verbrauch und die Aufnahme von Sprit muss immer >0 sein.

die Summe der einzelnen Tankvolumen muss x_0 sein.

Diese einfachen Überlegungen deuten doch die Problematik an.

25.10.2011, 08:41

René Gruber

Auf diesen Beitrag antworten »

Folgendes Gedankenexperiment hilft bei der Lösung des Problems:

Man startet mit einem beliebigen der Autos, wobei man - im Unterschied zur Aufgabe - schon vorab genügend Benzin für die ganze Runde im Tank hat. Dann hält man bei jedem der $\begin{eqnarray*} n \end{eqnarray*}$ Autos an der Strecke, misst den aktuellen Benzinstand im eigenen Auto und füllt danach diesen Tank auf (aus dem Tank des stehenden Autos, also genau wie in der Aufgabe). Auch am Zielpunkt (also nach genau einer Runde) misst man noch ein letztes Mal den Benzinstand.

Am Ende hat man also $\begin{eqnarray*} n \end{eqnarray*}$ Benzinstände notiert, und jetzt denk mal drüber nach, wie man diese Informationen zur Aufgabenlösung nutzen könnte...

26.10.2011, 10:13

Math-Man

Auf diesen Beitrag antworten »

Auto- Analysis
Als Induktionsanfang für n = 1 ist klar, dass ein Auto, welches genügend Benzin für
eine Runde hat, diese Runde auch ohne einsammeln von Benzin fahren kann. Sei nun die
Aussage für n Autos bewiesen und n+1 Autos auf der Strecke. Dann gibt es mindestens
ein Auto A, was sein Nachfolgeauto B erreichen kann (könnte kein Auto das nächste
erreichen, hätten alle Autos zusammen nicht genügend Benzin für eine Runde). Nun sei
A zu B gefahren und habe dessen Benzin. Wir entfernen B. Dann gibt es n Autos, von
denen nach Induktionsvoraussetzung ein Auto die Runde fahren kann. Ist dieses A, so
schafft A auch in der Ursprungssituation die Runde. Ist dieses ein anderes Auto, so schafft
dieses ebenfalls auch bei n+1 Autos die Runde, denn es hat überall gleichviel Benzin wie
im Fall mit n Autos und von A nach B noch zusätzlich das Benzin von A.

Warum seit ihr anderen Klugscheisser nicht drauf gekommen?
Das Problem zu wiederholen bringt keine Lösung.
LOL Hammer

26.10.2011, 10:26

René Gruber

Auf diesen Beitrag antworten »

Wer "seid" mit "t" schreibt, sollte erstmal einen Orthographiekurs belegen, bevor er hier rumkrakeelt. Und neben der Orthographieschwäche besteht wohl offenbar auch noch eine Sehstörung: Direkt im Beitrag drüber steht ein Tipp, der sofort auf eine Direktlösung führt, ohne jede Induktion. Nur ist es hier im Forum Prinzip, nicht gleich alles brühwarm zu verraten. smile

26.10.2011, 18:14

Math-Man

Auf diesen Beitrag antworten »

Analysis
1.Hier geht es um Analysis nicht um Orthographie.
2.Deine Lösung geht an der eigentlichen Fragestellung vorbei,man sollte beweisen das ein Auto genug Benzin hat um eine Runde zu fahren, und nicht davon ausgehen dass ein Auto von Anfang an genug Benzin hat. Was soll es uns da bitte schön bringen die einzelnen Benzinstände zu notieren.
3. Es geht hier um Hochschulmathe, ich denke mal einen kleinen Text zu schreiben reicht da nicht. Ich habe keine Lösung serviert sondern einen Denkanstoß geliefert. Zur konkreten hochschulgerechten Lösung benötigt man eine Induktionsgleichung, keine Kurzgeschichte.

Lehrer

26.10.2011, 18:31

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Math-Man
Was soll es uns da bitte schön bringen die einzelnen Benzinstände zu notieren.

Tut mir herzlich leid für dich, dass du auf den einen Schritt, der dann nur noch zur Lösung benötigt wird, nicht kommst. Dieses Unvermögen solltest du aber nicht gleich in Nutzerbeleidigung ("andere Klugscheisser") umsetzen, das ist einfach unterste Schublade. Finger2

Übrigens ist das eine konstruktive Lösung, d.h., man kann direkt den Fahrer angeben, bei dem gestartet werden sollte. Deine Induktionslösung ist lediglich ein Existenzbeweis, d.h., man muss dann schon ganz schön Aufwand treiben, um die richtige Startposition zu ermitteln. Mag sein, dass das in der Aufgabenstellung nicht gefordert wird - ist aber trotzdem schön, das direkt ablesen zu können. Big Laugh

P.S.: So ein Mist, jetzt habe ich das Grundprinzip "Don't feed the troll" missachtet. Hammer

26.10.2011, 19:02

Math-Man

Auf diesen Beitrag antworten »

So Schlaumeier du redest immer davon die Startposition zu bestimmen.
1. Das war gar nicht gefragt
2. Wenn du mir einen Beweis lieferst welches der n Autos startet und wo dieses Auto am Anfang steht auf der Strecke mit Länge m bist du echt gut.

Big Laugh

26.10.2011, 19:07

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Math-Man
1. Das war gar nicht gefragt

Habe ich das nicht gerade gesagt:

Zitat:

Original von René Gruber
Mag sein, dass das in der Aufgabenstellung nicht gefordert wird - ist aber trotzdem schön, das direkt ablesen zu können.

Liest du überhaupt andere Beiträge, oder sonnst du dich nur in deinem eigenen Genie?

Zitat:

Original von Math-Man
2. Wenn du mir einen Beweis lieferst welches der n Autos startet und wo dieses Auto am Anfang steht auf der Strecke mit Länge m bist du echt gut.

Das Auto, bei dem gestartet wird, ist genau das, wo in der oben genannten Testrunde der niedrigste Benzinstand notiert wurde. Wenn du so schlau bist, wie du hier immer tust, wirst du auch nachvollziehen können, dass dann den Forderungen der Aufgabe genüge getan wird. Kannst mir auch gern einen Datensatz liefern, wo dieses Prinzip nicht funktioniert - wenn du einen findest. Teufel

26.10.2011, 21:03

wertetabelle

Auf diesen Beitrag antworten »

???
Hey Rene, Willkommen

mag zwar sein das Math-Man sich im Ton vergreift. Aber du schießt dafür auch immer am Problem vorbei und bist sehr uneinsichtig. Du redest über Dinge die nicht gefragt sind und machst alles irgendwie komplizierter als nötig.
Und in der Aufgabe muss auch nicht zwangsweise das erste Auto das meiste Benzin haben es reicht wenn es das nächste erreicht und das klappt auch bei nicht maximaler Tankfüllung.
In der Anfangsaufgabe war ja eigentlich auch die Frage wie man Beweisen kann das es stets ein Auto gibt das eine ganze Runde fähren kann, diese Frage hast du nicht beantwortet.
Also war die Antwort von Math-Man aus rein pragmatischer Sicht sehr wohl brauchbarer als deine. Sorry!!! smile

P.S.: Mich würde mal sehr deine Rechnung für den genauen Startort interessieren von dem du immer geredet hast. Big Laugh

26.10.2011, 22:00

René Gruber

Auf diesen Beitrag antworten »

wertetabelle = Math-Man ? Sehr durchsichtiges Manöver Big Laugh

Zitat:

Original von wertetabelle
Aber du schießt dafür auch immer am Problem vorbei und bist sehr uneinsichtig.

Wo schieße ich am Problem vorbei? In meinem letzten Post habe ich eine konstruktive Lösung des Problems genannt - wenn du so "uneinsichtig" bist, dich nicht mit dieser Lösung zu befassen, dann kann ich auch nichts dafür.

Zitat:

Original von wertetabelle
Mich würde mal sehr deine Rechnung für den genauen Startort interessieren von dem du immer geredet hast.

Mach die Augen auf: Die Rechnung, wie der Startort zu finden ist, steht schon lange da. Die ausführliche mathematische Begründung folgt nun in diesem Beitrag, ganz unten.

Im übrigen achte ich die Lösung von Math-Man, das ist wohl das, was mich von diesem Egozentriker unterscheidet.

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

Also gut, das ganze Auto- und Benzinproblem auf den mathematischen Kern abstrahiert:

Zitat:

Seien $\begin{eqnarray*} a_0,\ldots,a_{n-1} \end{eqnarray*}$ reelle Zahlen mit Summe Null. Man zeige, dass es dann einen Index $\begin{eqnarray*} k \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq k\leq n-1 \end{eqnarray*}$ gibt, so dass für alle $\begin{eqnarray*} m \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq m\leq n-1 \end{eqnarray*}$ die Summen

$\begin{eqnarray*} \sum_{j=k}^{k+m} a_{j \bmod n} \end{eqnarray*}$

nichtnegativ sind. (Das $\begin{eqnarray*} j\bmod n \end{eqnarray*}$ sorgt übrigens dafür, dass nach $\begin{eqnarray*} a_{n-1} \end{eqnarray*}$ wieder $\begin{eqnarray*} a_0 \end{eqnarray*}$ folgt, d.h., der Rundencharakter symbolisch korrekt umgesetzt wird.)

Lösung: Die Folge

$\begin{eqnarray*} s_m = \sum_{j=0}^{m-1} a_{j \bmod n} \end{eqnarray*}$ für $\begin{eqnarray*} m=0,1,2,\ldots,2n-1 \end{eqnarray*}$

(dabei wird wie üblich $\begin{eqnarray*} s_0=0 \end{eqnarray*}$ gesetzt) ist periodisch mit Periode $\begin{eqnarray*} n \end{eqnarray*}$ infolge der vorausgesetzten Summenbedingung $\begin{eqnarray*} \sum_{j=0}^{n-1} a_j = 0 \end{eqnarray*}$ ,
d.h., es gilt $\begin{eqnarray*} s_{m} = s_{m-n} \end{eqnarray*}$ für alle $\begin{eqnarray*} m=n,n+1\ldots,2n-1 \end{eqnarray*}$ . Damit nimmt die Gesamtfolge ihr Minimum bereits für ein $\begin{eqnarray*} k \end{eqnarray*}$ aus der ersten Hälfte (d.h. $\begin{eqnarray*} 0\leq k\leq n-1 \end{eqnarray*}$ ) an, der zugehörige Minimalwert der Folge ist demnach $\begin{eqnarray*} s_k \end{eqnarray*}$ . Genau dieses $\begin{eqnarray*} k \end{eqnarray*}$ erfüllt nun die geforderte Bedingung, denn es ist dann ja einfach

$\begin{eqnarray*} \sum_{j=k}^{k+m} a_{j \bmod n} = s_{k+m+1}-s_k \geq 0 \end{eqnarray*}$

wegen der Minimalität von $\begin{eqnarray*} s_k \end{eqnarray*}$ - fertig.

Auf das Autoproblem bezogen ist $\begin{eqnarray*} a_i \end{eqnarray*}$ natürlich die Differenz zwischen Tankinhalt von Auto $\begin{eqnarray*} i \end{eqnarray*}$ sowie dem Verbrauch auf der Strecke von Auto $\begin{eqnarray*} i \end{eqnarray*}$ zu Auto $\begin{eqnarray*} i+1 \end{eqnarray*}$ . Augenzwinkern

Neue Frage »

Antworten »

n autos müssen eine Runde fahren

Verwandte Themen