Hallo,
auf einem Markt treffen sich n Obsthändler. Jeder bringt m Äpfel mit, die willkürlich in n Körbe geworfen werden, so daß am Ende in jedem Korb genau m Äpfel liegen. Ist es möglich, die Händler so vor die Körbe zu stellen, daß jeder Händler in „seinen“ Korb wieder einen Apfel von sich vorfindet ?
Gruss
Enno
PS: Aus einem anderen Forum klabustert - ist aber eine sehr schöne Aufgabe, die zwei wichtige Sätze/Prinzipien der Mathematik beinhaltet.
Hallo,
auf einem Markt treffen sich n Obsthändler. Jeder bringt m
Äpfel mit, die willkürlich in n Körbe geworfen werden, so daß
am Ende in jedem Korb genau m Äpfel liegen. Ist es möglich,
die Händler so vor die Körbe zu stellen, daß jeder Händler in
„seinen“ Korb wieder einen Apfel von sich vorfindet ?
Hi Enno,
gerade mit dem Abzock-Thread unten bin ich mir unsicher was die Aufgabenstellung angeht: genau einen Apfel oder mindestens einen?
-Jeder Händler schmeisst einen seiner m Äpfel in n Körbe (bei n=m)
Ja es ist möglich, bei willkürlicher Aufstellung richtig zu stehen (p=1)
Wenn er jedoch alle in einen Korb schmeisst, das jeder ander Händler auch tut, ist die Wahrscheinlichkeit, dass ein Händler vor „seinem“ Korb steht, 1/n, da es nur einen „guten“ Korb gibt.
-Da aber nicht klar ist, ob m n gilt, und sie dazu noch willkürlich verteilt werden, liegt die Wahrheit dazwischen: Ja es ist möglich, muss aber nicht.
Das Bild, dass mir durch den Kopf schoss, als ich das „Rätsel“ (was ich wohl nicht so ganz geblickt hab) war folgendes:
Die n Händler stellen sich im Kreis auf, m Äpfel auf dem Arm und stellen n Körbe vor sich. Jetzt werfe alle ihre Äpfel kunterbunt zusammen: z.B. werfen sie sich immer alle Äpfel zu, und der einen nicht fängt, muss ihn in den Korb legen. Als kein Apfel mehr in der Luft ist, werden die Äpfel blind umverteilt bis in allen Körben gleich viele Äpfel drin sind. (Wenn die Äpfel ununterscheidbar sind hätte jeder Händler auch gleich alle vor sich in den Korb legen können, ohne das doofe Spiel; sie sind aber nicht ununterscheidbar, da jeder ja vor „seinem“ Apfel landen soll. *grübel, schweif ich grad etwas ab ??
*
ich raff’s nich… und schon gar nicht, dass ich so lange Zeit gefunden habe die Tastatur zu vergewaltigen!
jartUl
Hallo,
mind. einen. Ansonsten könnte man leicht eine Lsg. für m>n ausschließen.
Die Frage zielt nicht auf Wahrscheinlichkeitsrechnung ab, sondern nur ob bei einer beliebigen Verteilung der je m Äpfel der n Händler auf die n Körbe eine Anordnung Händler/Körbe gefunden werden kann, daß jeder Händler einen Korb (mit insgesamt m Äpfeln - evtl. bunt gemixt) mit einen seiner Äpfel vor sich wieder vorfindet. Um die Äpfel erkennbar zu machen, kann man sich z.B. vorstellen, die Händler würden unterschiedliche Sorten mitbringen oder platter ihr Name ist einfach aufgeklebt. Es ist kein Verfahren gefragt, wie man so eine Anordnung berechnen könnte, nur eine Begründung warum oder warum nicht es eine solche Anordnung geben könnte.
Nehmen wir den trivialen Fall m=1 und z.B. 10 Händler. Da wir 10 Körbe haben und abschließend in jedem ein Apfel sein soll ist das Problem hier lösbar, ebenso wie bei m=1 und n beliebig. Die einzige Einschränkung, die ich oben vergaß ist m>0, da implizit natürliche Zahlen >0 vorrausgesetzt wurden (bei n=0 ist das Problem trivialerweise allerdings immer lösbar).
Gruss
Enno
Jeder bringt m
Äpfel mit, die willkürlich in n Körbe geworfen werden, so daß
am Ende in jedem Korb genau m Äpfel liegen.
Wenn es m Äpfel gibt, die auf n Körbe verteilt werden, so dass in jedem mindestens m Äpfel liegen, kann es nur ein einziger Korb sein, oder?
Grüße, Felix
Hallo,
es gibt m Äpfel pro Händler also insgesamt n*m Äpfel.
Gruss
Enno
Hi,
Die Frage zielt nicht auf Wahrscheinlichkeitsrechnung ab,
sondern nur ob bei einer beliebigen Verteilung der je m Äpfel
der n Händler auf die n Körbe eine Anordnung Händler/Körbe
gefunden werden kann, daß jeder Händler einen Korb (mit
insgesamt m Äpfeln - evtl. bunt gemixt) mit einen seiner Äpfel
vor sich wieder vorfindet.
Für nichttriviale n,m Kombinationen gibt es immer eine Lösung. Ich weiss nicht, wie ich das mathematisch begründen soll, aber das ist durch blosses scharfes Hinsehen leicht erkennbar
(sagt man dazu trivial?).
Dass die Frage nicht auf W`keitsrechnung abzielt, macht sie für mich eher uninteressant.
Gruss,
Hallo,
„trivial“ wäre es, wenn der Beweis dazu unmittelbar ersichtlich wäre - das ist aber m.M. nicht der Fall. Sicher kommt man schnell zu der Überzeugung die Aussage zu beweisen und nicht zu widerlegen aber ein „globaler“ Beweis, der über sämtliche Möglichkeiten der Verteilung der Äpfel auf die Körbe argumentiert, gestaltet sich extrem schwer. Auch scheitert hier ein simpler Induktionsbeweis oder wird druselig. Der Kern des eleganten Beweises ist ein Kompaktheitsargument. Die Aussage behält auch ihre Gültigkeit, wenn es z.B. überabzählbar viele Händler und Körbe (z.B. mit reellen Zahlen „durchnummeriert“) gäbe, die m Äpfel mitbringen (das m auch noch „unendlich zu machen“ gestaltet sich schwieriger).
Gruss
Enno
Hi Enno,
das ist genau der Grund, warum ich so häufig an „höherer“ Mathematik scheitere. Warum benötige ich ein sog. Kompaktheitsargument, wenn mir mein gesunder Menschenverstand sagt, dass es so oder so zu lösen ist. Für mich ist die Mathe kein heiliger Gral, sondern ein Mittel zum Zweck, das mir dann und wann das Leben vereinfachen soll.
Aber dennoch bin ich gespannt, was der Händler mit seinen Äpfeln in den Körben kompaktisieren möchte? Apfelmus?!
*gespannt auf (Apfel-) Kern des eleganten Beweises (oder Arguments) harrt*
jartUl
Hallo,
über Kompaktheitseigenschaften zu argumentieren ist m.M. durchaus etwas, was der Mensch in ähnlicher aber „unschärferer“ Weise alltäglich macht. Die meisten Dinge nehmen wir nur ausschnittweise bezogen auf deren Gesamtheit wahr (wobei das bereits eine Klassifikation vorraussetzt). Erkennen wir für diese Fallbsp. bestimmte uns bisher unbekannte Eigenschaften, sind wir nach einer bestimmten Anzahl solcher Bsp. dazu geneigt, diese Eigenschaften der Gesamtheit zuzuordnen. Kurz - es hilft einfach eine unüberschaubare Vielfalt zu überblicken.
*gespannt auf (Apfel-) Kern des eleganten Beweises (oder
Arguments) harrt*
Kommt nächste Woche, wenn bis dahin keiner eine Lsg. gefunden hat.
Gruss
Enno
Kommt nächste Woche, wenn bis dahin keiner eine Lsg. gefunden
hat.Gruss
Enno
Hi Enno… *auf den Kalender schielt*
HER DAMIT!
jartUl, der sich und seine grauen Zellen voll auf Ennos Schilderungen kompaktisiert
Lsg.
Hallo,
Kern des Beweises ist der Hall’sche Heiratssatz (im engl. „marriage theorem“). In der ursprünglichen Fassung geht es darum, für eine endliche Menge von Damen D und eine endliche Menge von Herren H + einer Auswahl S: D -> P(H) in Frage kommender Herren pro Dame, eine „Heirat“ zu finden, d.h. eine eindeutige Zuordnung eines Mannes zu einer Dame (ergo: keine Polygamie) oder formaler eine injektive Abbildung i: D -> H mit i(d)∈S(d). Die Heirat ist genau dann möglich, wenn für es für jede Auswahl X⊆D von Damen, „genügend“ in Frage kommender Herren gibt, d.h. nicht weniger als die Anzahl der Damen oder formal
|∪d∈X S(d)|>=|X|
gilt. Beweise des Satzes gibt es haufenweise im Netz, häufig im Bereich der Graphentheorie, wo der Satz die Existenz einer „perfekten Paarung“ in „bipartiten Graphen“ liefert. Der Satz läßt sich kanonisch auf beliebige Mengen D und H erweitern, solange die Bedingung S(d) endlich bleibt. Math. liefert er die Grundlage zum Nachweis injektiver Auswahlfunktionen. Beweisen läßt sich die Erweiterung z.B. durch den Endlichkeits-/Kompaktheitssatz der klassischen Logik oder topologisch mit dem Tychonoff’schen Produkttheorem.
Verwendet man diesen Satz, läßt sich das Rätsel simpel lösen. Wir wählen in diesem Fall die Händler als „Damen“ und die Körbe als „Herren“. Sei also H,K,A mit |H|=|K|=n und |A|=nm für n,m>=1 die Mengen der Händler, Körbe bzw. Äpfel. Wir partitionieren die Äpfel in zwei Weisen:
und wählen S(h)={ k | k∈K und A(h)∩C(k)∅ } als die Menge der Körbe, die mind. einen Apfel von Händler h enthält. Verkürzend wird A(X)=∪h∈X A(h), S(X)=∪h∈X S(h) und C(Y)=∪k∈Y C(k) für X⊆H und Y⊆K verwendet. Gesucht ist eine eindeutige Zuordnung von Händlern zu Körben (mit Äpfeln der entsprechenden Händler), also eine injektive Abbildung i: H -> K mit i(h)∈S(h). Dazu ist Z.Z., daß |S(X)|>=|X| für beliebige X⊆H oder inhaltlich: für jede beliebige Auswahl von Händlern gibt es mind. so viel Körbe mit Äpfeln dieser Händler, wie die Anzahl dieser Händler selbst. Dies ist leicht einzusehen, da falls widersprüchlich angenommen |S(X)|=|X| und damit existiert die gesuchte injektive Abbildung i: H -> K mit i(h)∈S(h).
Gruss
Enno
Anderes Bsp.
Hallo,
ein anderes Rätsel, was sich ebenfalls mit diesem Satz lösen läßt lautet wie folgt:
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 acht 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.
Hat Markus recht?
Hier ist m.M. die Richtigkeit von Markus seiner Aussage weniger deutlich „intuitiv“
ersichtlich, als im Ursprungsrätsel.
Gruss
Enno