möglichkeiten in einer schlange anzustehen

Neue Frage »

Lilly1990 Auf diesen Beitrag antworten »
möglichkeiten in einer schlange anzustehen
meine aufgabe lautet:
vor einem konzert (eintritt 5 euro) warten m personen mit einem zehn euro schein und n personen mit einem 5 euro schein. die kasse der veranstalter ist leer. wie viele möglk gibt es, die personen mit einem 5 euro schein und die mit einem 10 euro schein so auf die schlange zu verteilen, dass immer von der kasse gewechselt werden kann?

ich habe mir bisher überlegt, dass es sich hier um ein "ziehen ohne zurücklegen, mit reihenfolge" handelt. dafür habe ich die formel:


aber ich komme nicht weiter, weiß nicht, was hier N und n ist. kann mir jemand helfen?
zui Auf diesen Beitrag antworten »
RE: möglichkeiten in einer schlange anzustehen
ich weiss die lösung für eine ähnliche aufgabe: wenn m=n, dann Anzahl=C(2n, n) - C(2n, n-1). Dabei gilt für die P(für an kasse keine stau zu haben)=1/(n+1), aber die lösungsweg ist mir unbegreiflich. Sorry verwirrt
wisili Auf diesen Beitrag antworten »
RE: möglichkeiten in einer schlange anzustehen
[attach]16678[/attach]

ist die gesuchte Anzahl der Warteschlangen für 0 < m <= n, 1 für m=0, sonst 0.
Wenn man für die 5- bzw. 10-Euro-Scheine 1 bzw. 0 verwendet, wird die Warteschlange zu einem 1-0-Tupel. Die Bedingung heisst dann, dass beim Aufsummieren des Tupels von links nach rechts die Summe immer mindestens die Hälfte der bereits erreichten Summanden ausmacht.

Eine direkte Erklärung will mir bis jetzt nicht gelingen. Eine rekursive (induktiv nach m+n) ist dagegen einfach und benützt im wesentlichen nur die berühmte Summeneigenschaft benachbarter Binomialkoeffizienten.
Lilly1990 Auf diesen Beitrag antworten »

Danke erstmal! smile smile Mir ist klar wie man auf den ersten Binomialkoeffizienten kommt: Er gibt die Anzahl der Möglichkeiten an, m von m+n Personen anzuordnen. Mir ist auch klar, dass ja nicht alle Reihenfolgen möglich sind, sondern immer wenn eine Person m_i kommt, schon vorher eine Person n_j da gewesen sein muss. Das wird doch durch den zweiten Binomialkoeffizienten ausgedrückt?! Wie kann ich mir das anschaulich anhand der Formel vorstellen? Kannst du mir das bitte noch erklären? verwirrt
wisili Auf diesen Beitrag antworten »

Die gesuchte Anzahl A(m,n) lässt sich so bilden: A(m-1,n) + A(m,n-1). Damit wird ein Induktionsbeweis einfach.
Kärstin Auf diesen Beitrag antworten »

Hallo, ich muss die gleiche Aufgabe machen, checks aber überhaupt gar nicht! unglücklich
Ich versteh noch nicht mal, was A ist... und für n=m=2 kommt für die Formel 2 heraus.
Sollte da aber nicht 4 herauskommen?
@wisili: Es wäre voll toll, wenn du das ausführlicher erklären könntest!
 
 
wisili Auf diesen Beitrag antworten »

Wenn wir 10- bzw- 5-Euro-Warteschlangen-Leute abkürzen mit Z und F, dann gibt es für m=n=2 genau 6 Warteschlangen: FFZZ, FZFZ, FZZF, ZFFZ, ZFZF und ZZFF. Die letzten 4 fallen aber weg, weil zwischendurch in der Kasse 1 oder 2 Fünf-Euro-Scheine fehlen werden.

A war nur spontan Abkürzung für «Anzahl». Es gilt also A(2,2) = 2.
Hingegen muss für m>n stets A(m,n) = 0 angenommen werden.
zui Auf diesen Beitrag antworten »

Die Lösung
Beschreiben wir die Tatsächliche Verteilung der 5/10 Euro-Schienen in der Schlange mit Hilfe eines Graphen, wie es auf Abb. oben dargestellt ist. Ein schritt nach unten bedeutet, dass die Kasse eben einen 5-E-Schein gekriegt hat, nach oben – dass ein 10-E-Schein abgegeben wurde. Alle Graphen beginnen bei (0,0) und enden an (X=n+m, Y= m-n <=0). Bis die Kurve im Bereich Y<0 verläuft – alles O.K. ist: es wurden mehr 5-E abgegeben, als 10-E-Scheinen. So was zeigen die 2 Kurven Abb.1.
Die Abb. unten zeigt einen ungünstigen Fall: Vom 7. Besucher wurde 10-E-Schein abgegeben und die Kasse hat keine 5-E Scheine mehr: Stau. Wie wollen die Anzahl der ungünstigen Kurven zu ermitteln.
Dazu zeichnen wir eine Hilfskurve, die bis zum Staupunkt läuft wie Originalkurve, ab Staupunkt bildet die eine Spiegelung an (Y=1) der Originalkurve. Jede Hilfskurve beginnt an (0,0) und endet an (n+m, n-m+2).
Wozu brauchen wie die Hilfskurven überhaupt? Was ist dadurch besser geworden? Schau an:
1. Jede ungünstige Kurve hat eine einzige eindeutige Hilfskurve, die zwischen (0,0) und (n+m, n-m+2) verläuft.
2. Jede Hilfskurve, die zwischen (0,0) und (n+m, n-m+2) verläuft, entspricht eindeutig einer einzigen ungünstigen Originalkurve.
3. Die Anzahl der Hilfskurven = Anzahl der ungünstigen Kurven.
4. Für die Hilfskurven die Bedingung (Y mindestens einmal >0) ist weg -> Kombinatorik pur ist gefragt.

Jede Hilfskurve hat A Stufen nach oben, B Stufen nach unten, dabei:
A+B = m+n - Stufenanzahl; A-B=n-m+2; Das heißt, A=n+1, B=m-1;
Wie viele Möglichkeiten gibt es eine solche Kurve zu bilden ? Klar: C(n+m, n+1)=C(n+m, m-1) – so groß ist die Anzahl der ungünstigen Kurven und wir kommen zur Lösung, die WISILI vorhergesagt hat:
N=C(n+m, m) – C(n+m,m-1)
wisili Auf diesen Beitrag antworten »

@zui
Danke für das (kunstvolle und trickige) Schliessen meiner Lücke für den direkten Beweis. Ich bin auf rekursivem Weg auf die Formel gekommen. Es ist an den Fragestellern allenfalls weitere Klärungen zu verlangen, entweder für ein rekursives oder aber für ein direktes Verstehen der Formel.
Lilly1990 Auf diesen Beitrag antworten »

vielen lieben dank euch beiden für die hilfe, da habt ihr euch ja riesen mühe gemacht smile smile
ich habe zu der methode von zui noch eine frage, danach habe ich es hoffentlich verstanden: mir ist noch nicht klar, woran ich erkennen kann, dass der y-wert der hilfsfunktion im ungünstigen fall bei x=n+m stets bei "n-m+2" ist. wie kann ich das erkennen/ erahnen?
würde mich sehr freuen über eine antwort.
liebe grüße von lilly
René Gruber Auf diesen Beitrag antworten »

Von bis hinab zu sind es genau Stufen nach unten. Nach dem Umklappen geht es diese Stufen (in der Summe) nicht hinab, sondern hinauf, dann also bis zu . D.h., nichts weiter als einfache (in der Skizze vertikale) Abstandsbetrachtungen vor und nach dem Umklappen an der Linie .
Heike Auf diesen Beitrag antworten »

Ich sitze gerade auch an der gleichen Aufgabe und möchte sie über Induktion lösen. Was wäre denn der Induktionsanfang?

?

Und wenn ja, warum? Wenn m die Personen mit 10 € sind, dann ist doch m < n, und der Binominalkoeffizient ergibt keinen Sinn?!

Hat es was mit dem Aufsummieren von links zu tun? Ich habe nämlich nicht verstanden, wie wisili diese Aussage benützt, um weiterzukommen...

Vielen Dank für eure Hilfe!
wisili Auf diesen Beitrag antworten »

Die oben beschriebene Anzahl sei also A(m,n).

Behauptung: A(m,n) = für und A(m,n) = 0 für m>n.

Induktionsbeweis nach Länge k der Warteschlange:

Induktionsanfang: k = m+n = 1:

A(1,0) = 0 weil m>n: Es gibt keine zulässige Warteschlange der Länge 1 mit m=1 mal 10 Euro, und

A(0,1) = = 1 + 0 = 1: Es gibt genau eine Warteschlange der Länge 1 mit n=1 mal 5 Euro.

Induktionsschritt: Die Behauptung sei für alle A(m,n) mit m+n = k richtig.

Zu zeigen ist: Die Behauptung ist dann für alle A(m,n) mit m+n=k+1 auch richtig.

@Heike
Das Aufsummieren der binären Tupel diente nur der Andeutung, in welchem Modell ich die Formel gefunden habe. Es ist aber für den Induktionsbeweis unwichtig.

[attach]16732[/attach]
Heike Auf diesen Beitrag antworten »

Vielen Dank an wisili für den Induktionsanfang!

Jetzt habe ich noch eine Frage, nämlich, wie die Konstruktion der Formel funktioniert. Das mit den Tupeln habe ich verstanden, aber ich bin mir nicht so sicher, wie ich von den Tupeln zum Binominalkoeffizient komme...

steht für alle Möglichkeiten, die ich habe, um die Personen anzuordnen. Von denen werden die Möglichkeiten abgezogen, bei denen eine Person m mit 10€ kommt, ohne dass 5€ zum wechseln vorhanden sind:



Durch die Umformung bin ich jetzt ja im "Schritt" eins vorher. Aber leider weiß ich nicht, was jetzt m-1 bzw. m-2 bedeuten soll. verwirrt Wie komme ich jetzt drauf, dass das die Möglichkeiten zum anstellen sind, die nicht realisiert werden können?
wisili Auf diesen Beitrag antworten »

Wenn man die von dir bereits vorgeführte Formel zweimal anwendet, geht es so:

A(m,n) =



= A(m,n-1) + A(m-1,n).

Das ist alles rein formales Argumentieren. Du brauchst nicht inhaltlich einzusehen, dass der «Abzug» genau die richtige Grösse hat, sondern das wird (typisch für den Induktionsschritt) vererbt. Wenn dich diese Inhalte interessieren, musst du den Lösungsweg von zui studieren.
Heike Auf diesen Beitrag antworten »

Vielen Dank an wisili für die Erklärung!

Ich habe mir den Weg von zui angesehen, und verstehe leider trotz der Erklärung von Rene Gruber nicht, wie ich auf n-m+2 für den y-Wert komme...
wisili Auf diesen Beitrag antworten »

Wenn man den Punkt (a, b) an der x-Achse spiegelt, erhält man (a, -b).
Wenn man den Punkt (a, b) an der Geraden y=1 spiegelt, erhält man (a, -b+2).
Wenn man den Punkt (a, m-n) an der Geraden y=1 spiegelt, erhält man (a, n-m+2).

(Das arithmetische Mittel von (m-n) und (n-m+2) ist nämlich 1.)
Heike Auf diesen Beitrag antworten »

Hammer

Vielen Dank! Jetzt hab ich's verstanden. Ich hab viel zu kompliziert gedacht...
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »